Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

SIAM Journal on Optimization

Ellipsoid Bounds for Convex Quadratic Integer Programming

Christoph Buchheim, Ruth Hübner, Anita Schöbel

Published Jan 1, 2015• 14 citations
Publisher

Abstract

Solving convex quadratic integer minimization problems by a branch-and-bound algorithm requires tight lower bounds on the optimal objective value. To obtain such dual bounds, we follow the approach of [C. Buchheim, A. Caprara, and A. Lodi, Math. Program., 135 (2012), pp. 369--395] and underestimate the objective function by another convex quadratic function that can be minimized over the integers by simply rounding its continuous minimizer. In geometric terms, we approximate the sublevel sets of the original objective function by auxiliary ellipsoids having the strong rounding property, introduced by [R. Hübner and A. Schöbel, European J. Oper. Res., 237 (2014), pp. 404--410]. We first consider axisparallel ellipsoids (corresponding to separable convex quadratic functions) and show how to efficiently compute an axisparallel ellipsoid yielding the tightest lower bound, both in the situation where the location of the continuous minimizer is given and in the situation where it varies, as it happens in a branch-and-bound approach. In the latter case, we compute both worst-case and average-case optimal ellipsoids. Moreover, we consider the class of quasi-round ellipsoids (from Hübner and Schöbel). In this case, we do not know whether optimal auxiliary ellipsoids can be computed efficiently. However, we present a heuristic for computing an appropriate quasi-round ellipsoid that still yields valid dual bounds; it turns out that using this approach within a branch-and-bound scheme outperforms the approaches based on axisparallel ellipsoid in terms of running times. We finally combine both approaches by introducing the concept of quasi-axisparallel ellipsoids and present a corresponding extension of the heuristic bound computation.

DOI
10.1137/130929187

Related papers

A Feasible Active Set Method with Reoptimization for Convex Quadratic Mixed-Integer Programming

Christoph Buchheim, Marianna De Santis, Stefano Lucidi +2 more

We propose a feasible active set method for convex quadratic programming problems with nonnegativity constraints. This method is specifically designed to be embedded into a branch-and-bound algorithm for convex quadratic mixed- integer programming problems. The branch-and-bound algorithm generalizes the approach for unconstrained convex quadratic integer programming proposed by Buchheim, Caprara, and Lodi [Math. Program., 135 (2012), pp. 369--395] to the presence of linear constraints. The main feature of the latter approach consists of a sophisticated preprocessing phase, leading to a fast enumeration of the branch-and-bound nodes. Moreover, the feasible active set method takes advantage of this preprocessing phase and is well suited for reoptimization. Experimental results for randomly generated instances show that the new approach significantly outperforms the MIQP solver of \tt CPLEX 12.6 for instances with a small number of constraints.

arXiv:1512.02369•SIAM Journal on Optimization•Jan 1, 2016•21 citations

Global solution of non-convex quadratically constrained quadratic programs

Sourour Elloumi, Amélie Lambert

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.

Optimization methods & software•Jul 28, 2017•26 citations

Quadratic Convex Reformulation for discrete quadratic optimization : Basic results and recent extensions

Sourour Elloumi

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.

•Oct 28, 2014•0 citations

Quadratic Combinatorial Optimization Using Separable Underestimators

Christoph Buchheim, Emiliano Traversi

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.

INFORMS journal on computing•Aug 1, 2018•19 citations

A new Branch and Bound algorithm for MIQPs

Alain Billionnet, Sourour Elloumi, Amélie Lambert

Let (MQP) be a MIQP that consists in minimizing a quadratic function subject to linear constraints. Our approach to solve (MQP) is first to consider (MQP'), an equivalent MIQP that has a convex objective function, additional variables and constraints, and additionnal quadratic constraints. Then, we propose a new Branch and Bound based on the relaxation of the quadratic constraints to solve (MQP'). We perform experiments on pure-and mixed-integer instances of medium size, and show that their solution times are improved by our Branch and Bound in comparison with two existing approaches.

•Jul 9, 2012•0 citations

Enhancing convexification techniques for solving nonconvex quadratic programming problems

Xiaofei Qi

At the intersection of combinatorial and nonlinear optimization, quadratic programming (QP) plays an important role in practice and optimization theory.With wide-spread real-world applications including, but not limited to, engineering design, game theory, and economics, quadratic programming has many valuable contributions and has attracted considerable interest over the past few decades.As a more general formulation, quadratically constrained quadratic programming (QCQP) problems arise naturally from a lot of applications such as facility location, production planning, economic equilibria and Euclidean distance geometry, etc.Most global optimization approaches for nonconvex QCQPs are based on constructing a convex or linear relaxation of the problem, and embedding it within an exhaustive search mechanism, where a lower bound is calculated as the value of the objective function of this relaxation (for a minimization problem) at each iteration of the search tree.The two principle elements affecting the overall effectiveness of such exhaustive search methods are the tightness of the underlying relaxation and the efficiency of calculating the lower bound.Besides, the performance of a branch-and-bound algorithm also relies on the procedure used to select a branching node and branching variable, which leads to good quality feasible solutions or equivalently an upper bound.vii LIST OF TABLES 5.5 Computational results of 0-1 QPs with n = 40 . . . . . . . . . . . .110 5.6 Computational results of 0-1 QPs with n = 50 . . . . . . . . . . . .

•Jan 1, 2017•0 citations
Solving convex quadratic integer minimization problems by a branch-and-bound algorithm requires tight lower bounds on the optimal objective value. To obtain such dual bounds, we follow the approach of [C. Buchheim, A. Caprara, and A. Lodi, Math. Program., 135 (2012), pp. 369--395] and underestimate the objective function by another convex quadratic function that can be minimized over the integers by simply rounding its continuous minimizer. In geometric terms, we approximate the sublevel sets of the original objective function by auxiliary ellipsoids having the strong rounding property, introduced by [R. Hübner and A. Schöbel, European J. Oper. Res., 237 (2014), pp. 404--410]. We first consider axisparallel ellipsoids (corresponding to separable convex quadratic functions) and show how to efficiently compute an axisparallel ellipsoid yielding the tightest lower bound, both in the situation where the location of the continuous minimizer is given and in the situation where it varies, as it happens in a branch-and-bound approach. In the latter case, we compute both worst-case and average-case optimal ellipsoids. Moreover, we consider the class of quasi-round ellipsoids (from Hübner and Schöbel). In this case, we do not know whether optimal auxiliary ellipsoids can be computed efficiently. However, we present a heuristic for computing an appropriate quasi-round ellipsoid that still yields valid dual bounds; it turns out that using this approach within a branch-and-bound scheme outperforms the approaches based on axisparallel ellipsoid in terms of running times. We finally combine both approaches by introducing the concept of quasi-axisparallel ellipsoids and present a corresponding extension of the heuristic bound computation.
We propose a feasible active set method for convex quadratic programming problems with nonnegativity constraints. This method is specifically designed to be embedded into a branch-and-bound algorithm for convex quadratic mixed- integer programming problems. The branch-and-bound algorithm generalizes the approach for unconstrained convex quadratic integer programming proposed by Buchheim, Caprara, and Lodi [Math. Program., 135 (2012), pp. 369--395] to the presence of linear constraints. The main feature of the latter approach consists of a sophisticated preprocessing phase, leading to a fast enumeration of the branch-and-bound nodes. Moreover, the feasible active set method takes advantage of this preprocessing phase and is well suited for reoptimization. Experimental results for randomly generated instances show that the new approach significantly outperforms the MIQP solver of \tt CPLEX 12.6 for instances with a small number of constraints.
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 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.
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.
Let (MQP) be a MIQP that consists in minimizing a quadratic function subject to linear constraints. Our approach to solve (MQP) is first to consider (MQP'), an equivalent MIQP that has a convex objective function, additional variables and constraints, and additionnal quadratic constraints. Then, we propose a new Branch and Bound based on the relaxation of the quadratic constraints to solve (MQP'). We perform experiments on pure-and mixed-integer instances of medium size, and show that their solution times are improved by our Branch and Bound in comparison with two existing approaches.
At the intersection of combinatorial and nonlinear optimization, quadratic programming (QP) plays an important role in practice and optimization theory.With wide-spread real-world applications including, but not limited to, engineering design, game theory, and economics, quadratic programming has many valuable contributions and has attracted considerable interest over the past few decades.As a more general formulation, quadratically constrained quadratic programming (QCQP) problems arise naturally from a lot of applications such as facility location, production planning, economic equilibria and Euclidean distance geometry, etc.Most global optimization approaches for nonconvex QCQPs are based on constructing a convex or linear relaxation of the problem, and embedding it within an exhaustive search mechanism, where a lower bound is calculated as the value of the objective function of this relaxation (for a minimization problem) at each iteration of the search tree.The two principle elements affecting the overall effectiveness of such exhaustive search methods are the tightness of the underlying relaxation and the efficiency of calculating the lower bound.Besides, the performance of a branch-and-bound algorithm also relies on the procedure used to select a branching node and branching variable, which leads to good quality feasible solutions or equivalently an upper bound.vii LIST OF TABLES 5.5 Computational results of 0-1 QPs with n = 40 . . . . . . . . . . . .110 5.6 Computational results of 0-1 QPs with n = 50 . . . . . . . . . . . .