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

Cutting Planes for Mixed Integer Programming

Andrea Qualizza

Published Jan 1, 2011• 2 citations
Publisher

Abstract

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.

DOI
10.1184/r1/6715511

Related papers

Solving Quadratic Programming by Cutting Planes

Pierre Bonami, Andrea Lodi, Jonas Schweiger +1 more

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.

SIAM Journal on Optimization•Jan 1, 2019•22 citations

Enhancements of discretization approaches for non-convex mixed-integer quadratically constrained quadratic programming: part II

Benjamin Beach, Robert Burlacu, Andreas Bärmann +2 more

Abstract This is Part II of a study on mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We set the focus on MIP relaxation methods for non-convex continuous variable products where both variables are bounded and extend the well-known MIP relaxation normalized multiparametric disaggregation technique(NMDT), applying a sophisticated discretization to both variables. We refer to this approach as doubly discretized normalized multiparametric disaggregation technique (D-NMDT). In a comprehensive theoretical analysis, we underline the theoretical advantages of the enhanced method D-NMDT compared to NMDT. Furthermore, we perform a broad computational study to demonstrate its effectiveness in terms of producing tight dual bounds for MIQCQPs. Finally, we compare D-NMDT to the separable MIP relaxations from Part I and a state-of-the-art MIQCQP solver.

arXiv:2302.01164•Computational Optimization and Applications•Mar 18, 2024•1 citation

Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2

Ruth Misener, James B. Smadbeck, Christodoulos A. Floudas

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.

Optimization methods & software•Apr 22, 2014•51 citations

Enhancements of discretization approaches for non-convex mixed-integer quadratically constrained quadratic programming: Part I

Benjamin Beach, Robert Burlacu, Andreas Bärmann +2 more

Abstract We study mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We present MIP relaxation methods for non-convex continuous variable products. In this paper, we consider MIP relaxations based on separable reformulation. The main focus is the introduction of the enhanced separable MIP relaxation for non-convex quadratic products of the form $$z=xy$$ z = x y , called hybrid separable (HybS). Additionally, we introduce a logarithmic MIP relaxation for univariate quadratic terms, called sawtooth relaxation , based on Beach (Beach in J Glob Optim 84:869–912, 2022). We combine the latter with HybS and existing separable reformulations to derive MIP relaxations of MIQCQPs. We provide a comprehensive theoretical analysis of these techniques, underlining the theoretical advantages of HybS compared to its predecessors. We perform a broad computational study to demonstrate the effectiveness of the enhanced MIP relaxation in terms of producing tight dual bounds for MIQCQPs. In Part II, we study MIP relaxations that extend the MIP relaxation normalized multiparametric disaggregation technique (NMDT) (Castro in J Glob Optim 64:765–784, 2015) and present a computational study which also includes the MIP relaxations from this work and compares them with a state-of-the-art of MIQCQP solvers.

arXiv:2211.00876•Computational Optimization and Applications•Jan 30, 2024•7 citations

Two useful computational tricks for Quadratic Programming: hybrid SDP bounding procedures and a new linearisation technique

Fabio Furini, Emiliano Traversi

Quadratic programming problems have received an increasing amount of attention in the recent years, both from the theoretical and practical point of views. For this class of problems, we studied two different useful computational tricks.The first one is the exploitation of Semidefinite Programming (SDP) relaxation within the framework provided by Mixed Integer Nonlinear Programming (MINLP) solvers. We included the SDP relaxation in a state-of-the-art MINLP solver as an additional bounding technique and demonstrated that this idea could be computationally useful. The Quadratic Stable Set Problem is adopted as the case study. The tests indicate that the Hybrid SDP Bounding Procedure allows an average 50% cut of the overall computing time and a cut of more than one order of magnitude for the branching nodes.The second one is a new linearisation technique. We computationally prove that the new formulation, called Extended Linear Formulation, can be effective for different classes of problems in practice. Our tests are based on two sets of classical BQPs from the literature, i.e., the Unconstrained BQP and the Maximum Cut of edge-weighted graphs. Finally we discuss the relations between the Linear Programming relaxations of the different linearisation techniques presented and we discuss the elimination of constraint redundancy which is effective at speeding up the computational convergence.

•Jan 1, 2014•0 citations

Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization

Michael Jünger, Sven Mallach

The exact solution of the NP-hard (nondeterministic polynomial-time hard) maximum cut problem is important in many applications across, for example, physics, chemistry, neuroscience, and circuit layout—which is also due to its equivalence to the unconstrained binary quadratic optimization problem. Leading solution methods are based on linear or semidefinite programming and require the separation of the so-called odd-cycle inequalities. In their groundbreaking research, F. Barahona and A. R. Mahjoub have given an informal description of a polynomial-time algorithm for this problem. As pointed out recently, however, additional effort is necessary to guarantee that the inequalities obtained correspond to facets of the cut polytope. In this paper, we shed more light on a so enhanced separation procedure and investigate experimentally how it performs in comparison with an ideal setting where one could even employ the sparsest, most violated, or geometrically most promising facet-defining odd-cycle inequalities. Summary of Contribution: This paper aims at a better capability to solve binary quadratic optimization or maximum cut problems and their various applications using integer programming techniques. To this end, the paper describes enhancements to a well-known algorithm for the central separation problem arising in this context; it is demonstrated experimentally that these enhancements are worthwhile from a computational point of view. The linear relaxations of the aforementioned problems are typically solved using fewer iterations and cutting planes than with a nonenhanced approach. It is also shown that the enhanced procedure is only slightly inferior to an ideal, enumerative, and, in practice, intractable global cutting-plane selection.

INFORMS journal on computing•Feb 11, 2021•8 citations
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.
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.
Abstract This is Part II of a study on mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We set the focus on MIP relaxation methods for non-convex continuous variable products where both variables are bounded and extend the well-known MIP relaxation normalized multiparametric disaggregation technique(NMDT), applying a sophisticated discretization to both variables. We refer to this approach as doubly discretized normalized multiparametric disaggregation technique (D-NMDT). In a comprehensive theoretical analysis, we underline the theoretical advantages of the enhanced method D-NMDT compared to NMDT. Furthermore, we perform a broad computational study to demonstrate its effectiveness in terms of producing tight dual bounds for MIQCQPs. Finally, we compare D-NMDT to the separable MIP relaxations from Part I and a state-of-the-art MIQCQP solver.
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.
Abstract We study mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We present MIP relaxation methods for non-convex continuous variable products. In this paper, we consider MIP relaxations based on separable reformulation. The main focus is the introduction of the enhanced separable MIP relaxation for non-convex quadratic products of the form z=xyz=xyz=xy z = x y , called hybrid separable (HybS). Additionally, we introduce a logarithmic MIP relaxation for univariate quadratic terms, called sawtooth relaxation , based on Beach (Beach in J Glob Optim 84:869–912, 2022). We combine the latter with HybS and existing separable reformulations to derive MIP relaxations of MIQCQPs. We provide a comprehensive theoretical analysis of these techniques, underlining the theoretical advantages of HybS compared to its predecessors. We perform a broad computational study to demonstrate the effectiveness of the enhanced MIP relaxation in terms of producing tight dual bounds for MIQCQPs. In Part II, we study MIP relaxations that extend the MIP relaxation normalized multiparametric disaggregation technique (NMDT) (Castro in J Glob Optim 64:765–784, 2015) and present a computational study which also includes the MIP relaxations from this work and compares them with a state-of-the-art of MIQCQP solvers.
Quadratic programming problems have received an increasing amount of attention in the recent years, both from the theoretical and practical point of views. For this class of problems, we studied two different useful computational tricks.The first one is the exploitation of Semidefinite Programming (SDP) relaxation within the framework provided by Mixed Integer Nonlinear Programming (MINLP) solvers. We included the SDP relaxation in a state-of-the-art MINLP solver as an additional bounding technique and demonstrated that this idea could be computationally useful. The Quadratic Stable Set Problem is adopted as the case study. The tests indicate that the Hybrid SDP Bounding Procedure allows an average 50% cut of the overall computing time and a cut of more than one order of magnitude for the branching nodes.The second one is a new linearisation technique. We computationally prove that the new formulation, called Extended Linear Formulation, can be effective for different classes of problems in practice. Our tests are based on two sets of classical BQPs from the literature, i.e., the Unconstrained BQP and the Maximum Cut of edge-weighted graphs. Finally we discuss the relations between the Linear Programming relaxations of the different linearisation techniques presented and we discuss the elimination of constraint redundancy which is effective at speeding up the computational convergence.
The exact solution of the NP-hard (nondeterministic polynomial-time hard) maximum cut problem is important in many applications across, for example, physics, chemistry, neuroscience, and circuit layout—which is also due to its equivalence to the unconstrained binary quadratic optimization problem. Leading solution methods are based on linear or semidefinite programming and require the separation of the so-called odd-cycle inequalities. In their groundbreaking research, F. Barahona and A. R. Mahjoub have given an informal description of a polynomial-time algorithm for this problem. As pointed out recently, however, additional effort is necessary to guarantee that the inequalities obtained correspond to facets of the cut polytope. In this paper, we shed more light on a so enhanced separation procedure and investigate experimentally how it performs in comparison with an ideal setting where one could even employ the sparsest, most violated, or geometrically most promising facet-defining odd-cycle inequalities. Summary of Contribution: This paper aims at a better capability to solve binary quadratic optimization or maximum cut problems and their various applications using integer programming techniques. To this end, the paper describes enhancements to a well-known algorithm for the central separation problem arising in this context; it is demonstrated experimentally that these enhancements are worthwhile from a computational point of view. The linear relaxations of the aforementioned problems are typically solved using fewer iterations and cutting planes than with a nonenhanced approach. It is also shown that the enhanced procedure is only slightly inferior to an ideal, enumerative, and, in practice, intractable global cutting-plane selection.