arXiv:math/0006036

When Does the Positive Semidefiniteness Constraint Help In Lifting Procedures

Levent Tunçel, Michel X. Goemans

Published Jun 5, 2000• 2 citations

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.48550/arxiv.math/0006036

Related papers

When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?

Michel X. Goemans, Levent Tunçel

Mathematics of Operations ResearchNov 1, 200171 citations

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.2263Aug 10, 20120 citations

On Integrality in Semidefinite Programming for Discrete Optimization

Frank de Meijer, Renata Sotirov

arXiv:2306.09865SIAM Journal on OptimizationMar 15, 20243 citations

Beyond binarity: Semidefinite programming for ternary quadratic problems

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

arXiv:2603.28979Mar 30, 20260 citations

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

Adam Kurpisz, Lucas Slot, Mikhail S. Zaytsev

arXiv:2605.00594May 1, 20260 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.

International Symposium on Symbolic and Algebraic ComputationJul 9, 20260 citations

arXiv:math/0006036

When Does the Positive Semidefiniteness Constraint Help In Lifting Procedures

Levent Tunçel, Michel X. Goemans

Published Jun 5, 2000• 2 citations

arXiv HTML PDF

Abstract

DOI: 10.48550/arxiv.math/0006036

Related papers

When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?

Michel X. Goemans, Levent Tunçel

Mathematics of Operations ResearchNov 1, 200171 citations

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

Pietro Paparella

arXiv:1208.2263Aug 10, 20120 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.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.09865SIAM Journal on OptimizationMar 15, 20243 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.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.28979Mar 30, 20260 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 \geq 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 \emph{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 ($0We 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 \geq 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 \emph{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

arXiv:2605.00594May 1, 20260 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.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.

International Symposium on Symbolic and Algebraic ComputationJul 9, 20260 citations

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.

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 \geq 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 \emph{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

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.