Search

A primal quadratic simplex algorithm tailored to the optimization over the vertices of a polytope is presented. Starting from a feasible vertex, it performs either strictly improving or admissible non-deteriorating steps in order to determine a locally optimum basic feasible solution in terms of the quadratic objective function. The algorithm so generalizes over local improvement methods for according applications, including in particular quadratic optimization problems whose feasible solutions correspond to vertices of a 0-1 polytope. Computational experiments for unconstrained binary quadratic programs, maximum cut, and the quadratic assignment problem serve as a proof of concept and underline the importance of a pivoting rule that is able to accept at least a restricted class of degenerate steps. [ABSTRACT FROM AUTHOR]

The computational utility of inductive linearizations for binary quadratic programs when combined with a mixed-integer programming solver is investigated for several combinatorial optimization problems and established benchmark instances. [ABSTRACT FROM AUTHOR]

It is well known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a comprehensive study on discrete positive semidefinite matrices, we introduce a generic approach to derive mixed-integer SDP (MISDP) formulations of binary quadratically constrained quadratic programs and binary quadratic matrix programs. Applying a problem-specific approach, we derive more compact MISDP formulations of several problems, such as the quadratic assignment problem, the graph partition problem, and the integer matrix completion problem. We also show that several structured problems allow for novel compact MISDP formulations through the notion of association schemes. Complementary to the recent advances on algorithmic aspects related to MISDP, this work opens new perspectives on solution approaches for the here considered problems. [ABSTRACT FROM AUTHOR]

We propose an entropy regularized splitting model using low-rank factorization for solving binary quadratic programming with linear inequality constraints. Different from the semidefinite programming relaxation model, our model preserves the rank-one constraint and aims to find high quality rank-one solutions directly. The factorization transforms the variables into low-rank matrices, while the entropy term enforces the low-rank property of the splitting variable. A customized alternating direction method of multipliers is utilized to solve the proposed model. Specifically, our method uses the augmented Lagrangian function to deal with inequality constraints, and solves one subproblem on the oblique manifold by a regularized Newton method. Numerical results on the multiple-input multiple-output detection problem, the maxcut problem and the quadratic 0 - 1 problem indicate that our proposed algorithm has advantage over the SDP methods. [ABSTRACT FROM AUTHOR]

The purpose of this paper is the approach of a mathematical model dedicated to planning the consecutive days off of a company’s employees. Companies must find a flexible work schedule between employees, always considering the satisfaction of work tasks as well as guaranteeing consecutive days off. The analysis is based on solving a quadratic programming problem with binary variables. The proposed method uses the properties of the circulant symmetric matrix in the researched model, which allows the transformation of the considered problems into an equivalent separable non-convex optimization problem. A practical continuous convex relaxation approach is proposed. DC Algorithm is used to solve relaxed problems. A solved numerical example is presented.

We present and compare novel binary programs for linear ordering problems that involve the notion of asymmetric betweenness and expose relations to the quadratic linear ordering problem and its linearization. While two of the binary programs prove particularly superior from a computational point of view when many or all betweenness relations shall be modeled, the others arise as natural formulations that resemble important theoretical correspondences and provide a compact alternative for sparse problem instances. A reasoning for the strengths and weaknesses of the different formulations is derived by means of polyhedral considerations with respect to their continuous relaxations.

The goal of this paper is to investigate the curves intersected by a vertical plane with the surfaces based on certain NCP functions. The convexity and differentiability of these curves are studied as well. In most cases, the inflection points of the curves cannot be expressed exactly. Therefore, we instead estimate the interval where the curves are convex under this situation. Then, with the help of differentiability and convexity, we obtain the local minimum or maximum of the curves accordingly. The study of these curves is very useful to binary quadratic programming. [ABSTRACT FROM AUTHOR]

We present BiqBin, an exact solver for linearly constrained binary quadratic problems. Our approach is based on an exact penalty method to first efficiently transform the original problem into an instance of Max-Cut, and then to solve the Max-Cut problem by a branch-and-bound algorithm. All the main ingredients are carefully developed using new semidefinite programming relaxations obtained by strengthening the existing relaxations with a set of hypermetric inequalities, applying the bundle method as the bounding routine and using new strategies for exploring the branch-and-bound tree. Furthermore, an efficient C implementation of a sequential and a parallel branch-and-bound algorithm is presented. The latter is based on a load coordinator-worker scheme using MPI for multi-node parallelization and is evaluated on a high-performance computer. The new solver is benchmarked against BiqCrunch, GUROBI, and SCIP on four families of (linearly constrained) binary quadratic problems. Numerical results demonstrate that BiqBin is a highly competitive solver. The serial version outperforms the other three solvers on the majority of the benchmark instances. We also evaluate the parallel solver and show that it has good scaling properties. The general audience can use it as an on-line service available at http://www.biqbin.eu. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to provide strong reformulations for binary quadratic problems. We propose a first methodological analysis on a family of reformulations combining Dantzig–Wolfe and Quadratic Convex optimization principles. We show that a few reformulations of our family yield continuous relaxations that are strong in terms of dual bounds and computationally efficient to optimize. As a representative case study, we apply them to a cardinality constrained quadratic knapsack problem, providing extensive experimental insights. We report and analyze in depth a particular reformulation providing continuous relaxations whose solutions turn out to be integer optima in all our tests. [ABSTRACT FROM AUTHOR]

Many image processing and pattern recognition problems can be formulated as binary quadratic programming (BQP) problems. However, solving a large BQP problem with a good quality solution and low computational time is still a challenging unsolved problem. Current methodologies either adopt an independent random search in a semi-definite space or perform search in a relaxed biconvex space. However, the independent search has great computation cost as many different trials are needed to get a good solution. The biconvex search only searches the solution in a local convex ball, which can be a local optimal solution. In this paper, we propose a BQP solver that alternatingly applies a deterministic search and a stochastic neighborhood search. The deterministic search iteratively improves the solution quality until it satisfies the KKT optimality conditions. The stochastic search performs bootstrapping sampling to the objective function constructed from the potential solution to find a stochastic neighborhood vector. These two steps are repeated until the obtained solution is better than many of its stochastic neighborhood vectors. We compare the proposed solver with several state-of-the-art methods for a range of image processing and pattern recognition problems. Experimental results showed that the proposed solver not only outperformed them in solution quality but also with the lowest computational complexity. [ABSTRACT FROM AUTHOR]

A linearization technique for binary quadratic programs (BQPs) that comprise linear constraints is presented. The technique, called "inductive linearization", extends concepts for BQPs with particular equation constraints, that have been referred to as "compact linearization" before, to the general case. Quadratic terms may occur in the objective function, in the set of constraints, or in both. For several relevant applications, the linear programming relaxations obtained from applying the technique are proven to be at least as strong as the one obtained with a well-known classical linearization. It is also shown how to obtain an inductive linearization automatically. This might be used, e.g., by general-purpose mixed-integer programming solvers. [ABSTRACT FROM AUTHOR]

The goal of this paper is to investigate the curves intersected by a vertical plane with the surfaces based on certain NCP functions. The convexity and differentiability of these curves are studied as well. In most cases, the inflection points of the curves cannot be expressed exactly. Therefore, we instead estimate the interval where the curves are convex under this situation. Then, with the help of differentiability and convexity, we obtain the local minimum or maximum of the curves accordingly. The study of these curves is very useful to binary quadratic programming.

The global optimization of binary quadratic programming (BQP) has very important theory and wide application in various fields. Since BQP is a classic NP-hard problem, traditional algorithms will be very time-consuming when the dimension is very large. The neural network based algorithms have significant advantages in solving large scale optimization problems. However, directly applying neural network based algorithm cannot guarantee finding the global optimal solution of BQP. In this paper, we propose a neural network based algorithm for BQP by analyzing and utilizing geometric characteristics of the objective function isosurface and combining the advantages and properties of neural network as well as branch-and-bound method. Furthermore, the neural network algorithm is implemented with field-programmable gate array (FPGA) to take advantage of the parallel structure. System Generator which can be used to convert the design into HDL code automatically is adopted so that the calculation of upper and lower bounds can be deployed to FPGA. The numerical simulation illustrates the effectiveness and efficiency of the algorithm. Meanwhile, simulation results show the feasibility of applying the proposed algorithm to FPGA hardware. [ABSTRACT FROM AUTHOR]

Daily fantasy sports (DFS) is a multibillion-dollar industry with millions of annual users and widespread appeal among sports fans across a broad range of popular sports. Building on recent work, we provide a coherent framework for constructing DFS portfolios where we explicitly model the behavior of other DFS players. We formulate an optimization problem that accurately describes the DFS problem for a risk-neutral decision maker in both double-up and top-heavy payoff settings. Our formulation maximizes the expected reward subject to feasibility constraints, and we relate this formulation to mean-variance optimization and the outperformance of stochastic benchmarks. Using this connection, we show how the problem can be reduced to the problem of solving a series of binary quadratic programs. We also propose an algorithm for solving the problem where the decision maker can submit multiple entries to the DFS contest. This algorithm is motivated by submodularity properties of the objective function and by some new results on parimutuel betting. One of the contributions of our work is the introduction of a Dirichlet-multinomial data-generating process for modeling opponents' team selections, and we estimate the parameters of this model via Dirichlet regressions. A further benefit to modeling opponents' team selections is that it enables us to estimate the value, in a DFS setting, of both insider trading and collusion. We demonstrate the value of our framework by applying it to DFS contests during the 2017 National Football League season. This paper was accepted by Baris Ata, stochastic models and simulation. [ABSTRACT FROM AUTHOR]

In this study, we deal with the problem of scheduling charging periods of electrical vehicles (EVs) to satisfy the users’ demands for energy consumption as well as to optimally utilize the available power. We assume three-phase EV charging stations, each equipped with two charging ports (links) that can serve up to two EVs in the scheduling period but not simultaneously. Considering such a specification, we propose an on–off scheduling scheme wherein control over an energy flow is achieved by flexibly switching the ports in each station on and off in a manner such as to satisfy the energy demand of each EV, flatten the high energy-consuming load on the whole farm, and to minimize the number of switching operations. To satisfy these needs, the on–off scheduling scheme is formulated in terms of a binary linear programming problem, which is then extended to a quadratic version to incorporate the smoothness constraints. Various algorithmic approaches are used for solving a binary quadratic programming problem, including the Frank–Wolfe algorithm and successive linear approximations. The numerical simulations demonstrate that the latter is scalable, efficient, and flexible in a charging procedure, and it shaves the load peak while maintaining smooth charging profiles.

This paper describes a new instance library for quadratic programming (QP), i.e., the family of continuous and (mixed)-integer optimization problems where the objective function and/or the constraints are quadratic. QP is a very diverse class of problems, comprising sub-classes ranging from trivial to undecidable. This diversity is reflected in the variety of QP solution methods, ranging from entirely combinatorial approaches to completely continuous algorithms, including many methods for which both aspects are fundamental. Selecting a set of instances of QP that is at the same time not overwhelmingly onerous but sufficiently challenging for the different, interested communities is therefore important. We propose a simple taxonomy for QP instances leading to a systematic problem selection mechanism. We then briefly survey the field of QP, giving an overview of theory, methods and solvers. Finally, we describe how the library was put together, and detail its final contents. [ABSTRACT FROM AUTHOR]

Abstract Testing a given matrix for membership in the family of Bernoulli matrices is a long-standing problem; the many applications of Bernoulli vectors in computer science, finance, medicine, and operations research emphasize its practical relevance. After the three-variate case was covered by Chaganty and Joe (2006) by means of partial correlations, a novel approach towards this problem was taken by Fiebig et al. (2017) for low-dimensional settings, i.e., d ≤ 6. The latter authors were the first to exploit the close relationship between the probabilistic world of Bernoulli matrices and the well-studied correlation and cut polytopes. Inspired by this approach, we use results from Deza and Laurent (1997), Embrechts et al. (2016), and Fiebig et al. (2017) in a pre-phase of a novel algorithm to check necessary as well as sufficient conditions, before actually testing a matrix for Bernoulli compatibility. In our main approach, however, we build upon an early attempt by Lee (1993) based on the vertex representation of the correlation polytope and directly solve the corresponding linear program. To deal appropriately with the issue of exponentially many primal variables, we propose a specifically tailored column generation method. A straightforward, yet novel, analysis of the arising subproblem of determining the most violated dual constraint in the column generation process leads to an exact algorithm for membership testing. Although the membership problem is known to be NP-complete, we observe very promising performance up to dimension d = 40 on a broad variety of test problems. An important byproduct of the numerical solution is a representation for Bernoulli matrices with (only) d 2 many vertices that gives rise to an efficient simulation routine. [ABSTRACT FROM AUTHOR]

We introduce and prove new necessary and sufficient conditions to carry out a compact linearization approach for a general class of binary quadratic problems subject to assignment constraints that has been proposed by Liberti (4OR 5(3):231-245, 2007, 10.1007/s10288-006-0015-3). The new conditions resolve inconsistencies that can occur when the original method is used. We also present a mixed-integer linear program to compute a minimally sized linearization. When all the assignment constraints have non-overlapping variable support, this program is shown to have a totally unimodular constraint matrix. Finally, we give a polynomial-time combinatorial algorithm that is exact in this case and can be used as a heuristic otherwise. [ABSTRACT FROM AUTHOR]

This article presents BiqCrunch, an exact solver for binary quadratic optimization problems. BiqCrunch is a branch-and-bound method that uses an original, efficient semidefinite-optimization-based bounding procedure. It has been successfully tested on a variety of well-known combinatorial optimization problems, such as Max-Cut, Max-k-Cluster, and Max-Independent-Set. The code is publicly available online; a web interface and many conversion tools are also provided. [ABSTRACT FROM AUTHOR]

In recent years, the general binary quadratic programming (BQP) model has been widely applied to solve a number of combinatorial optimization problems. In this paper, we recast the maximum vertex weight clique problem (MVWCP) into this model which is then solved by a probabilistic tabu search algorithm designed for the BQP. Experimental results on 80 challenging DIMACS-W and 40 BHOSLIB-W benchmark instances demonstrate that this general approach is viable for solving the MVWCP problem. [ABSTRACT FROM AUTHOR]

Binary quadratic programming ( BQP ) is a typical integer programming problem widely applied in the field of signal processing, economy, management and engineering. However, it is NP-hard and lacks efficient algorithms. Due to this reason, in this paper, some novel polynomial algorithms are proposed to solve a class of unconstrained and linearly constrained binary quadratic programming problems. We first deduce the polynomial time solvable algorithms to the unconstrained binary quadratic programming problems with Q being a seven-diagonal matrix ( UBQP 7 ) and a five-diagonal matrix ( UBQP 5 ) respectively with two different approaches. Then, the algorithm to unconstrained problem is combined with the dynamic programming method to solve the linearly constrained binary quadratic programming problem with Q being a five-diagonal matrix ( LCBQP 5 ) . In addition, the polynomial solvable feature of these algorithms is analyzed and some specific examples are presented to illustrate these new algorithms. Lastly, we demonstrate their polynomial feature as well as their high efficiency. [ABSTRACT FROM AUTHOR]

Unconstrained binary quadratic programming (UBQP) provides a unifying modeling and solution framework for solving a remarkable range of binary optimization problems, including many accompanied by constraints. Current methods for solving UBQP problems customarily rely on neighborhoods consisting of flip moves that select one or more binary variables and 'flip' their values to the complementary value (from 1 to 0 or from 0 to 1). We introduce a class of approaches called f-flip strategies that include a fractional value f as one of those available to the binary variables during intermediate stages of solution. A variety of different f-flip strategies, particularly within the context of multi-start algorithms, are proposed for pursuing intensification and diversification goals in metaheuristic algorithms, accompanied by special rules for evaluating and executing f-flips efficiently. [ABSTRACT FROM AUTHOR]

In this paper, an augmented Lagrangian method is proposed for binary quadratic programming (BQP) problems based on a class of continuous functions. The binary constraints are converted into a class of continuous functions. The approach reformulates the BQP problem as an equivalent augmented Lagrangian function, and then seeks its minimizer via an augmented Lagrangian method, in which the subproblem is solved by Barzilai-Borwein type method. Numerical results are reported for max-cut problem. The results indicate that the augmented Lagrangian approach is promising for large scale binary quadratic programming by the quality of the near optimal values and the low computational time. [ABSTRACT FROM AUTHOR]

Quadratic convex reformulation is an important method for improving the performance of a branch-and-bound based binary quadratic programming solver. In this paper, we study a new convex reformulation method. By this reformulation, the efficiency of a branch-and-bound algorithm can be improved significantly. We also compare this new reformulation method with other proposed methods, whose effectiveness has been proven. Numerical experimental results show that our reformulation method performs better than the compared methods for certain types of binary quadratic programming problems. [ABSTRACT FROM AUTHOR]

The standard linearization of a binary quadratic program yields an equivalent reformulation as an integer linear program, but the resulting LP-bounds are very weak in general. We concentrate on applications where the underlying linear problem is tractable and exploit the fact that, in this case, the optimization problem is still tractable in the presence of a single quadratic term in the objective function. We propose to strengthen the standard linearization by the use of cutting planes that are derived from jointly considering each single quadratic term with the underlying combinatorial structure. We apply this idea to the quadratic minimum spanning tree and spanning forest problems and present complete polyhedral descriptions of the corresponding problems with one quadratic term, as well as efficient separation algorithms for the resulting polytopes. Computationally, we observe that the new inequalities significantly improve dual bounds with respect to the standard linearization, particularly for sparse graphs. [ABSTRACT FROM AUTHOR]

Local binary pattern (LBP) and its variants have shown promising results in visual recognition applications. However, most existing approaches rely on a pre-defined structure to extract LBP features. We argue that the optimal LBP structure should be task-dependent and propose a new method to learn discriminative LBP structures. We formulate it as a point selection problem: Given a set of point candidates, the goal is to select an optimal subset to compose the LBP structure. In view of the problems of current feature selection algorithms, we propose a novel Maximal Joint Mutual Information criterion. Then, the point selection is converted into a binary quadratic programming problem and solved efficiently via the branch and bound algorithm. The proposed LBP structures demonstrate superior performance to the state-of-the-art approaches on classifying both spatial patterns in scene recognition and spatial-temporal patterns in dynamic texture recognition. [ABSTRACT FROM AUTHOR]

We present two recent integer programming models in molecular biology and study practical reformulations to compute solutions to some of these problems. In extension of previously tested linearization techniques, we formulate corresponding semidefinite relaxations and discuss practical rounding strategies to find good feasible approximate solutions. Our computational results highlight the possible advantages and remaining challenges of this approach especially on large-scale problems. [ABSTRACT FROM AUTHOR]

Near-duplicate retrieval (NDR) in merchandize images is of great importance to a lot of online applications on e-Commerce websites. In those applications where the requirement of response time is critical, however, the conventional techniques developed for a general purpose NDR are limited, because expensive post-processing like spatial verification or hashing is usually employed to compromise the quantization errors among the visual words used for the images. In this paper, we argue that most of the errors are introduced because of the quantization process where the visual words are considered individually, which has ignored the contextual relations among words. We propose a “spelling or phrase correction” like process for NDR, which extends the concept of collocations to visual domain for modeling the contextual relations. Binary quadratic programming is used to enforce the contextual consistency of words selected for an image, so that the errors (typos) are eliminated and the quality of the quantization process is improved. The experimental results show that the proposed method can improve the efficiency of NDR by reducing vocabulary size by 1000% times, and under the scenario of merchandize image NDR, the expensive local interest point feature used in conventional approaches can be replaced by color-moment feature, which reduces the time cost by 9202% while maintaining comparable performance to the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

As virtualization is becoming a promising way to support various emerging application, provisioning survivability to requested virtual networks (VN) in a resource efficient way is important. In this paper, we investigate the survivable VN embedding (SVNE) problem from a new perspective. First, we consider the failure dependent protection (FDP) in which each primary facility node would have a different backup facility node, as opposed to the Failure Independent Protection (FIP) which has been studied before, in order to provide the same degree of protection against a single node failure with less substrate resources. Secondly, we enhance the VN with additional computing and communication resources and design the Enhanced VN (or EVN) before embedding it to the substrate in order to further reduce the amount of substrate resources needed to survive a single facility node failure. The work is the first that combines the FDP with EVN design (FD-EVN) to explore a resource efficient solution to the SVNE problem. After presenting a binary quadratic programming (BQP) formulation of the FD-EVN design problem and a Mixed Integer Linear Programming (MILP) formulation of the EVN embedding (EVNE) problem, we propose two heuristic algorithms for FD-EVN design, as well as an EVNE algorithm that explores primary and backup substrate resources sharing. Simulations are conducted to evaluate the performance of the solutions to the BQP/MILP formulation when possible, and the heuristics. The proposed FD-EVN approach has shown to be resource efficient and in particular, outperform other approaches in terms of request acceptance ratio and embedding cost, although as a tradeoff, requiring more service migration after failures. [ABSTRACT FROM PUBLISHER]

Abstract: Routing and wavelength assignment (RWA) is the most concern in wavelength routed optical networks. This paper proposes a novel binary quadratic programming (BQP) formulation for the static RWA problem in order to balance traffic load among a network links more fairly. Subsequently, a greedy heuristic algorithm namely variable-weight routing and wavelength assignment (VW-RWA) is proposed to solve the developed BQP problem. In this method, the weight of a link is proportional to the link congestion. Performance evaluation results for different practical network topologies show that our proposed algorithm can decrease the number of required wavelengths in the network, blocking rate and variance of used wavelengths in each link. Besides, it is shown that the number of required wavelengths to establish call requests for a given network topology can be reduced at lower cost compared to other heuristics. [Copyright &y& Elsevier]