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

arXiv:math/0006036 · Mathematics of Operations Research

When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?

Michel X. Goemans, Levent Tunçel

Published Nov 1, 2001• 73 citations
arXivHTMLPDF

Abstract

We study the lift-and-project procedures of Lovász and Schrijver for 0-1 integer programming problems. We prove that the procedure using the positive semidefiniteness constraint is not better than the one without it, in the worst case. Various examples are considered. We also provide geometric conditions characterizing when the positive semidefiniteness constraint does not help.

DOI
10.1287/moor.26.4.796.10012

Related papers

A note on the Lovasz-Schrijver Semidefinite Programming Relaxation for Binary Integer Programs

Pietro Paparella

Binary Integer Programming (BIP) problems are of interest due in part to the difficulty they pose and because of their various applications, including those in graph theory, combinatorial optimization and network optimization. In this note, we explicitly state the Lovasz-Schrijver Semidefinite Programming (SDP) relaxation (in primal-standard form) for a BIP problem, a relaxation that yields a tighter upper-bound than the canonical Linear Programming relaxation.

arXiv:1208.2263•Aug 10, 2012•0 citations

On Integrality in Semidefinite Programming for Discrete Optimization

Frank de Meijer, Renata Sotirov

Abstract. 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.

arXiv:2306.09865•SIAM Journal on Optimization•Mar 15, 2024•7 citations

Beyond binarity: Semidefinite programming for ternary quadratic problems

Frank de Meijer, Veronica Piccialli, Renata Sotirov +1 more

We study the ternary quadratic problem (TQP), a quadratic optimization problem with linear constraints where the variables take values in $\{0, \pm 1\}$. While semidefinite programming (SDP) techniques are well established for $\{0,1\}$- and $\{\pm 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.

arXiv:2603.28979•Mar 30, 2026•1 citation

An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs

Jean Bernard Lasserre

We consider the general nonlinear optimization problem in 0-1 variables and provide an explicit equivalent positive semidefinite program in 2 n -1 variables. The optimal values of both problems are identical. From every optimal solution of the former, one easily finds an optimal solution of the latter, and conversely, from every solution of the latter, one may construct an optimal solution of the former. For illustration, the equivalent positive semidefinite program is explicated for quadratic 0-1 programs and MAX-CUT in $\mathbb{R}^3$. For unconstrained 0-1 programs, a special representation in terms of a weighted sum of squares is provided.

SIAM Journal on Optimization•Jan 1, 2002•175 citations

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank

Adam Kurpisz, Lucas Slot, Mikhail S. Zaytsev

We analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of \(\sum _{i=1}^n x_i\) for 0/1 variables under the constraint \(\sum _{i=1}^n x_i \ge q\), with \(q \in \mathbb {R}\). Such instances have long served as a testbed for understanding the limitations of lift-and-project methods in Boolean optimization. For example, both the Lovász–Schrijver and Sherali–Adams hierarchies require (maximal) rank n to solve them, already when q = 1/2 is constant. The SOS hierarchy requires only sublinear rank \(O(\sqrt {n})\) to solve unweighted MK when q = 1/2. On the other hand, when q is allowed to vary with n, the SOS rank of the problem may become linear. Interestingly, this is known to happen both when q is large, and when q is very small (0 < q ≤ 2− n). This raises the question of whether we should think of hard instances of unweighted MK as being typical for the SOS hierarchy, or as a consequence of very specific choices of the threshold parameter q.

arXiv:2605.00594•International Symposium on Symbolic and Algebraic Computation•Jul 9, 2026•0 citations

Cutting Planes for Mixed Integer Programming

Andrea Qualizza

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.

•Jan 1, 2011•2 citations
We study the lift-and-project procedures of Lovász and Schrijver for 0-1 integer programming problems. We prove that the procedure using the positive semidefiniteness constraint is not better than the one without it, in the worst case. Various examples are considered. We also provide geometric conditions characterizing when the positive semidefiniteness constraint does not help.
Abstract. 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.
We study the ternary quadratic problem (TQP), a quadratic optimization problem with linear constraints where the variables take values in {0,±1}\{0, \pm 1\}{0,±1}. While semidefinite programming (SDP) techniques are well established for {0,1}\{0,1\}{0,1}- and {±1}\{\pm 1\}{±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 kkk-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.
We consider the general nonlinear optimization problem in 0-1 variables and provide an explicit equivalent positive semidefinite program in 2 n -1 variables. The optimal values of both problems are identical. From every optimal solution of the former, one easily finds an optimal solution of the latter, and conversely, from every solution of the latter, one may construct an optimal solution of the former. For illustration, the equivalent positive semidefinite program is explicated for quadratic 0-1 programs and MAX-CUT in R3\mathbb{R}^3R3. For unconstrained 0-1 programs, a special representation in terms of a weighted sum of squares is provided.
We analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of ∑i=1nxi\sum _{i=1}^n x_i∑i=1n​xi​ for 0/1 variables under the constraint ∑i=1nxi≥q\sum _{i=1}^n x_i \ge q∑i=1n​xi​≥q, with q∈Rq \in \mathbb {R}q∈R. Such instances have long served as a testbed for understanding the limitations of lift-and-project methods in Boolean optimization. For example, both the Lovász–Schrijver and Sherali–Adams hierarchies require (maximal) rank n to solve them, already when q = 1/2 is constant. The SOS hierarchy requires only sublinear rank O(n)O(\sqrt {n})O(n​) to solve unweighted MK when q = 1/2. On the other hand, when q is allowed to vary with n, the SOS rank of the problem may become linear. Interestingly, this is known to happen both when q is large, and when q is very small (0 < q ≤ 2− n). This raises the question of whether we should think of hard instances of unweighted MK as being typical for the SOS hierarchy, or as a consequence of very specific choices of the threshold parameter q.
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.