Binary programs with a quadratic objective function are NP-hard in general, even if the linear optimization problem over the same feasible set is tractable. In this paper, we address such problems by computing quadratic global underestimators of the objective function that are separable but not necessarily convex. Exploiting the binary constraint on the variables, a minimizer of the separable underestimator over the feasible set can be computed by solving an appropriate linear minimization problem over the same feasible set. Embedding the resulting lower bounds into a branch-and-bound framework, we obtain an exact algorithm for the original quadratic binary program. The main practical challenge is the fast computation of an appropriate underestimator, which in our approach reduces to solving a series of semidefinite programs. We exploit the special structure of the resulting problems to obtain a tailored coordinate-descent method for their solution. Our extensive experimental results on various quadratic combinatorial optimization problems show that our approach outperforms both CPLEX and the related QCR method as well as the SDP-based software BiqCrunch on instances of the quadratic shortest path problem and the quadratic assignment problem.
Binary programs with a quadratic objective function are NP-hard in general, even if the linear optimization problem over the same feasible set is tractable. In this paper, we address such problems by computing quadratic global underestimators of the objective function that are separable but not necessarily convex. Exploiting the binary constraint on the variables, a minimizer of the separable underestimator over the feasible set can be computed by solving an appropriate linear minimization problem over the same feasible set. Embedding the resulting lower bounds into a branch-and-bound framework, we obtain an exact algorithm for the original quadratic binary program. The main practical challenge is the fast computation of an appropriate underestimator, which in our approach reduces to solving a series of semidefinite programs. We exploit the special structure of the resulting problems to obtain a tailored coordinate-descent method for their solution. Our extensive experimental results on various quadratic combinatorial optimization problems show that our approach outperforms both CPLEX and the related QCR method as well as the SDP-based software BiqCrunch on instances of the quadratic shortest path problem and the quadratic assignment problem.
Quadratic programming (QP) is a well-studied fundamental NP-hard optimization problem which optimizes a quadratic objective over a set of linear constraints. In this paper, we reformulate QPs as a mixed-integer linear problem (MILP). This is done via the reformulation of QP as a linear complementary problem, and the use of binary variables and big-M constraints, to model the complementary constraints. To obtain such reformulation, we show how to impose bounds on the dual variables without eliminating all the (globally) optimal primal solutions; using some fundamental results on the solution of perturbed linear systems. Reformulating non-convex QPs as MILPs provides an advantageous way to obtain global solutions as it allows the use of current state-of-the-art MILP solvers. To illustrate this, we compare the performance of our solution approach, labeled quadprogIP, with the current benchmark global QP solver quadprogBB, as well as with BARON, one of the leading non-linear programming (NLP) solvers, and CPLEX's non-convex QP solver, on a large variety of QP test instances. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. For general QPs, quadprogIP outperforms quadprogBB, outperforms BARON in most instances, while CPLEX performs the best on these instances. For box-constrained QPs, quadprogIP has a comparable performance to quadprogBB and BARON in small- to medium-scale instances, but is outperformed by these solvers on large-scale instances; while CPLEX performs the best on box-constrained QP instances. Also, unlike quadprogBB, the solution approach proposed here is able to solve QP instances whose dual feasible set is unbounded. The MATLAB code, called quadprogIP, and the instances used to perform these numerical experiments are publicly available at https://github.com/xiawei918/quadprogIP.
We consider problem (QP) of minimizing a quadratic function subject to linear or quadratic constraints. Variables are integer and bounded. This very general problem can model many classical problems in Combinatorial Optimization.A major difference between (QP) and integer linear programs lies in the fact that, in general, its continuous relaxation is an NP-hard optimization problem. To overcome this difficulty, the Convex Quadratic Reformulation approach transforms (QP) into a problem (QP'), equivalent to (QP), but whose continuous relaxation is a convex problem. To compute a global optimal solution to (QP) it becomes possible to solve (QP') by an implicit enumeration algorithm based on continuous convex optimization.We make an overview of recent developments in this approach. We show in particular how positive semidefinite relaxations can be used to build the most interesting equivalent problems (QP'). In the case of binary variables, we give a vision of classical linearization as a special case of Convex Quadratic Reformulation.Finally, we illustrate the generality and the computational efficiency of the Quadratic Convex Reformulation approach for several combinatorial optimization problems.
The multi-linearly constrained separable binary quadratic programming problem (MLSBQP) is a direct extension of the classical singly-linearly constrained separable binary quadratic programming problem (SLSBQP). In the literature, several algorithms have been proposed for SLSBQP which can solve problem instances with millions of variables globally. However, for the case of MLSBQP, the current state-of-the-art solver can only solve problems with up to 40000 binary variables within a reasonable computational time. In this paper, we propose an extremely efficient branch-and-bound algorithm for solving MLSBQP. The main feature of the proposed algorithm is that an efficient dual coordinate ascent algorithm is applied to obtain lower bounds, and the complexity of each inner loop of the dual coordinate ascent algorithm is $ \mathcal{O}(n\log n) $. Our numerical experiments show that the proposed branch-and-bound algorithm can solve MLSBQP with up to millions of variables within only several minutes, and performs much faster than Gurobi when the number of linear constraints is small.
The class of mixed-integer quadratically constrained quadratic programs (QCQP) consists of minimizing a quadratic function under quadratic constraints where the variables could be integer or continuous. On a previous paper we introduced a method called MIQCR for solving QCQPs with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. In this paper, we propose an extension of MIQCR which applies to any QCQP. Let (P) be a QCQP. Our approach to solve (P) is first to build an equivalent mixed-integer quadratic problem (P∗). This equivalent problem (P∗) has a quadratic convex objective function, linear constraints, and additional variables y that are meant to satisfy the additional quadratic constraints y=xxT, where x are the initial variables of problem (P). We then propose to solve (P∗) by a branch-and-bound algorithm based on the relaxation of the additional quadratic constraints and of the integrality constraints. This type of branching is known as spatial branch-and-bound. Computational experiences are carried out on a total of 325 instances. The results show that the solution time of most of the considered instances is improved by our method in comparison with the recent implementation of QuadProgBB, and with the solvers Cplex, Couenne, Scip, BARON and GloMIQO.
We study the ternary quadratic problem (TQP), a quadratic optimization problem with linear constraints where the variables take values in {0,±1}. While semidefinite programming (SDP) techniques are well established for {0,1}- and {±1}-valued quadratic problems, no dedicated integer semidefinite programming framework exists for the ternary case. In this paper, we introduce a ternary SDP formulation for the TQP that forms the basis of an exact solution approach. We derive new theoretical insights in rank-one ternary positive semidefinite matrices, which lead to a basic SDP relaxation that is further strengthened by valid triangle, RLT, split and k-gonal inequalities. These are embedded in a tailored branch-and-bound algorithm that iteratively solves strengthened SDPs, separates violated inequalities, applies a ternary branching strategy and computes high-quality feasible solutions. We test our algorithm on TQP variations motivated by practice, including unconstrained, linearly constrained and quadratic ratio problems. Computational results on these instances demonstrate the effectiveness of the proposed algorithm.
In this paper, we present a new method to solve a certain type of Semidefinite Programming (SDP) problems. These types of SDPs naturally arise in the Quadratic Convex Reformulation (QCR) method and can be used to obtain dual bounds of Quadratic Unconstrained Binary Optimization (QUBO) problems. QUBO problems have recently become the focus of attention in the quantum computing and optimization communities as they are well suited to both gate-based and annealing-based quantum computers on one side, and can encompass an exceptional variety of combinatorial optimization problems on the other. Our new method can be easily warm-started, making it very effective when embedded into a branch-and-bound scheme and used to solve the QUBO problem to global optimality. We test our method in this setting and present computational results showing the effectiveness of our approach.