We propose new cutting planes for strengthening the linear relaxations that appear in the solution of nonconvex quadratic problems with linear constraints. By a famous result of Motzkin and Straus, these problems are connected to the clique number of a graph. Our cuts are derived in the context of a spatial branch-and-bound algorithm where linearization variables are introduced to represent products. Their validity is based on the result of Motzkin and Straus, in that it depends on the clique number of certain graphs. For convenience, we derive our cuts for the special case of the so-called standard quadratic programs, where the only (linear) constraint imposes that variables must belong to a simplex. We specifically consider cuts that correspond to carefully constructed complete bipartite graphs. We study the relation between these cuts and the classical ones obtained at the first level of the reformulation-linearization technique. By studying this relation, we derive a new type of valid inequalities that generalizes both types of cuts, and thus leading to a large family of cutting planes to strengthen the linear relaxation. We present extensive computational results using the different cutting planes we propose within the spatial branch and bound implemented by the commercial solver CPLEX. We show that our cuts allow us to obtain a significantly better bound than reformulation-linearization cuts and reduce computing times for global optimality. Finally, we formally establish the scaling necessary for using the proposed cuts to solve nonconvex quadratic problems with linear constraints, e.g., quadratic knapsack problems.
We propose new cutting planes for strengthening the linear relaxations that appear in the solution of nonconvex quadratic problems with linear constraints. By a famous result of Motzkin and Straus, these problems are connected to the clique number of a graph. Our cuts are derived in the context of a spatial branch-and-bound algorithm where linearization variables are introduced to represent products. Their validity is based on the result of Motzkin and Straus, in that it depends on the clique number of certain graphs. For convenience, we derive our cuts for the special case of the so-called standard quadratic programs, where the only (linear) constraint imposes that variables must belong to a simplex. We specifically consider cuts that correspond to carefully constructed complete bipartite graphs. We study the relation between these cuts and the classical ones obtained at the first level of the reformulation-linearization technique. By studying this relation, we derive a new type of valid inequalities that generalizes both types of cuts, and thus leading to a large family of cutting planes to strengthen the linear relaxation. We present extensive computational results using the different cutting planes we propose within the spatial branch and bound implemented by the commercial solver CPLEX. We show that our cuts allow us to obtain a significantly better bound than reformulation-linearization cuts and reduce computing times for global optimality. Finally, we formally establish the scaling necessary for using the proposed cuts to solve nonconvex quadratic problems with linear constraints, e.g., quadratic knapsack problems.
We introduce a cutting-plane framework for nonconvex quadratic programs (QPs) that progressively tightens convex relaxations. Our approach leverages the doubly nonnegative (DNN) relaxation to compute strong lower bounds and generate separating cuts, which are iteratively added to improve the relaxation. We establish that, at any Karush-Kuhn-Tucker (KKT) point satisfying a second-order sufficient condition, a valid cut can be obtained by solving a linear semidefinite program (SDP), and we devise a finite-termination local search procedure to identify such points. Extensive computational experiments on both benchmark and synthetic instances demonstrate that our approach yields tighter bounds and consistently outperforms leading commercial and academic solvers in terms of efficiency, robustness, and scalability. Notably, on a standard desktop, our algorithm reduces the relative optimality gap to 0.01% on 138 out of 140 instances of dimension 100 within one hour, without resorting to branch-and-bound.
My work focuses on cutting planes technology in Mixed Integer Programming. I explore novel classes of valid linear inequalities to strengthen linear relaxations of both Linear and Nonlinear Mixed Integer problems. My dissertation consists of three chapters that investigate theoretically and computationally the families of cuts considered. The first chapter is based on joint work with Prof. Pietro Belotti and Prof. Francois Margot. We study linear relaxations of Quadratically Constrained Quadratic Programs. The proposed relaxations are models with both semi-definite constraints (PSD) and linear constraints given by the Reformulation Linearization Technique (RLT). It is known from the literature (Anstreicher, 2007) that PSD and RLT used together yield better bounds than each technique used separately. We adopt a linear outer-approximation of the PSD cone, and we use exclusively linear programming tools to enforce the PSD condition via a cutting plane approach in the lifted space containing the Yij = xixj variables. We study new classes of valid linear inequalities and we test their effectiveness empirically. These include sparse PSD cuts and cuts derived from principal minors. Computational results based on instances from the GLOBALLib and Boxed Constrained Quadratic Programs show that this approach yields better bounds than using solely the standard PSD cuts on top of the RLT inequalities. The C++ code developed for this study has been included in Coin-OR as part of the Couenne project (exact solver for MINLPs). In the second chapter I present a work closely related to the recent developments in the area of \cuts from multiple rows of the simplex tableau" (Andersen et al., 2007). This chapter is based on joint work with Prof. Egon Balas. We generate intersection cuts from lattice-free convex sets as lift-and-project cuts from multiple-term disjunctions. We use the concept of \Disjunctive Hull" defined for a Mixed Integer Program at a fractional vertex v of its linear relaxation P as the convex hull of points in P satisfying all basic disjunctions that cut o v but no integer point. We examine the relationship between the Disjunctive Hull and the Integer Hull and we give procedures to generate inequalities for the Integer Hull derived from the Cut Generating Linear Program associated to the Disjunctive Hull. Strengthening techniques based on coefficient modularization and monoidal strengthening are also discussed. In this chapter we also analyze the case of 0-1 programming which has not been covered in the literature. Our framework applies to this setting with minor changes and produces valid families of cuts for the 0-1 case but invalid for general integer programs. These cuts include the triangle, quadrilateral, split cuts for the MIP case, and cuts from cones and truncated cones for the 0-1 setting. Moreover we run an experiment in which we separate two families of non facet defining cuts: we consider cuts from fixed shape triangles of type 1 and conic disjunctions having the apex at one vertex of the unit cube and two extreme rays, each containing an additional vertex of the cube. In practice, in order to match the strength of the non facet defining inequalities, a large number of facet defining inequalities is typically needed. Triangles of type 1 produce a consistent improvement over the Gomory cuts, as shown in experiments on the MIPLIB 3 0-1 instances. In the third chapter I present a theoretical result on strengthening valid inequalities for Mixed Integer Linear Programs. This chapter is also based on joint work with Prof. Egon Balas. There are two distinct strengthening methods for disjunctive cuts; they differ in the way they modularize the coefficients associated to integer constrained variables. We introduce a new variant of one of these methods, the monoidal cut strengthening procedure (Balas and Jeroslow, 1980), based on the paradox that sometimes weakening a disjunction helps the strengthening procedure and results in sharper cuts. We first derive a general result that applies to cuts from disjunctions with any number of terms. It defines the coefficients of the cut in a way that takes advantage of the option of adding new terms to the disjunction. We then specialize this result to the case of split cuts, in particular Gomory Mixed Integer cuts, and to intersection cuts from multiple rows of a simplex tableau. In both instances we give conditions for the new cuts to have stronger coefficients than the cuts obtained by either of the two currently known strengthening procedures.
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.
Solving nonconvex quadratic optimization problems to global optimality is a challenging task. For this problem class Gurobi takes a branch-and-bound approach, so the building blocks for the solver are: A relaxation of the problem to solve at the nodes, cutting planes to reduce the feasible region of the relaxation, and heuristics to compute primal feasible solutions. Here we discuss the latter two building blocks in more detail, focussing on so-called PSD cuts, and a heuristic based on an interior point method.
Binary Quadratic Program with Variable Partitioning Constraints The binary quadratic program with variable partitioning constraints is a very general class of optimization problems that is very difficult to solve because of the nonconvexity and integrality of the variables and is ubiquitous, among others, in network design, computer vision, and transportation and logistics. In their article, “A convex reformulation and an outer approximation for a large class of binary quadratic programs,” Rostami et al. show how to transform such a nonconvex challenging problem into a convex bilinear program with decomposable structure. The authors develop a branch-and-cut algorithm based on outer approximation cuts, in which the cuts are generated on the fly by efficiently solving separation subproblems. The results of their computational experiments on different problems confirm the efficacy of the solution methods in solving large-scale problem instances.
The global mixed-integer quadratic optimizer, GloMIQO, addresses mixed-integer quadratically constrained quadratic programs (MIQCQP) to ε-global optimality. This paper documents the branch-and-cut framework integrated into GloMIQO 2. Cutting planes are derived from reformulation–linearization technique equations, convex multivariable terms, αBB convexifications, and low- and high-dimensional edge-concave aggregations. Cuts are based on both individual equations and collections of nonlinear terms in MIQCQP. Novel contributions of this paper include: development of a corollary to Crama's [Concave extensions for nonlinear 0-1 maximization problems, Math. Program. 61 (1993), pp. 53–60] necessary and sufficient condition for the existence of a cut dominating the termwise relaxation of a bilinear expression; algorithmic descriptions for deriving each class of cut; presentation of a branch-and-cut framework integrating the cuts. Computational results are presented along with comparison of the GloMIQO 2 performance to several state-of-the-art solvers.