Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack

Introduction

Many approximation algorithms work in two phases: first, solve a linear programming (LP) or semi-definite programming (SDP) relaxation; then, round the fractional solution to obtain a feasible integer solution to the original problem. This paradigm is amazingly powerful; in particular, under the unique game conjecture, it yields the best possible ratio for ${\mathsf{MaxCut}}$ and a wide variety of other problems, see e.g. .

However, these algorithms have a limitation. Since they are usually analyzed by comparing the value of the output to that of the fractional solution, we cannot generally hope to get a better approximation ratio than the integrality gap of the relaxation. Furthermore, for any given combinatorial optimization problem, there are many possible LP/SDP relaxations, and it is difficult to determine which relaxations have the best integrality gaps.

This has lead to efforts to provide systematic procedures for constructing a sequence of increasingly tight mathematical programming relaxations for 0-1 optimization problems. A number of different procedures of this type have been proposed: by Lovász and Schrijver , Sherali and Adams , Balas, Ceria and Cornuejols , Lasserre and others. While they differ in the details, they all operate in a series of rounds starting from an LP or SDP relaxation, eventually ending with an exact integer formulation. The strengthened relaxation after $t$ rounds can typically be solved in $n^{O(t)}$ time and, roughly, satisfies the property that the values of any $t$ variables in the original relaxation can be expressed as the projection of a convex combination of integer solutions.

A major line of research in this area has focused on understanding the strengths and limitations of these procedures. Of particular interest to our community is the question of how the integrality gaps for interesting combinatorial optimization problems evolve through a series of rounds of one of these procedures. On the one hand, if the integrality gaps of successive relaxations drop sufficiently fast, there is the potential for an improved approximation algorithm (see for example). On the other hand, a large integrality gap persisting for a large, say logarithmic, number of rounds rules out (unconditionally) a very wide class of efficient approximation algorithms, namely those whose output is analyzed by comparing it to the value of a class of LP/SDP relaxations. This implicitly contains most known sophisticated approximation algorithms for many problems including ${\mathsf{SparsestCut}}$ and ${\mathsf{MaximumSatisifiability}}$. Indeed, serveral very strong negative results of this type have been obtained (see and others). These are also viewed as lower bounds of approximability in certain restricted models of computation.

How strong are these restricted models of computation? In other words, how much do lower bounds in these models tell us about the intrinsic hardness of the problems studied? To explore this question, we focus on one problem that is well-known to be “easy” from the viewpoint of approximability: ${\mathsf{Knapsack}}$. We obtain the following results:

We show that an integrality gap close to 2 persists up to a linear number of rounds of Sherali-Adams. (The integrality gap of the natural LP is 2.)

This is interesting since ${\mathsf{Knapsack}}$ has a fully polynomial time approximation scheme . This confirms and amplifies what has already been observed in other contexts (e.g ): the Sherali-Adams restricted model of computation has serious weaknesses: a lower bound in this model does not necessarily imply that it is difficult to get a good approximation algorithm.

We show that Lasserre’s hierarchy closes the gap quickly. Specifically, after $t$ rounds of Laserre, the integrality gap decreases to $t/(t-1)$.

It is known that a few rounds of Lasserre can yield better relaxations. For example, two rounds of Lasserre applied to the ${\mathsf{MaxCut}}$ LP yields an SDP that is at least as strong as that used by Goemans and Williamson to get the best known approximation algorithm, and the SDP in which leads to the best known approximation algorithm for ${\mathsf{SparsestCut}}$ can be obtained by three rounds of Lasserre. However, to the best of our knowledge, this is the first positive result that utilizes more than a small constant number of rounds in the Lasserre hierarchy.

Many known approximation algorithms can be recognized in hindsight as starting from a natural relaxation and strengthening it using a couple of levels of lift-and-project. The original hope had been to use lift and project systems as a systematic approach to designing novel algorithms with better approximation ratios. Instead, the last few years have mostly seen the emergence of a multitude of lower bounds. Indeed, lift and project systems have been studied mostly for well known difficult problems: ${\mathsf{MaxCut}}$ , ${\mathsf{SparsestCut}}$, ${\mathsf{VertexCover}}$ , ${\mathsf{HypergraphVertexCover}}$, ${\mathsf{TSP}}$ , ${\mathsf{MaximumAcyclicSubgraph}}$ , ${\mathsf{CSP}}$ , and more.

The ${\mathsf{Knapsack}}$ problem has a fully polynomial time approximation scheme . The natural LP relaxation (to be stated in full detail in the next section) has an integrality gap of $2-\epsilon$ . Although we are not aware of previous work on using the lift and project systems for ${\mathsf{Knapsack}}$, the problem of strengthening the LP relaxation via addition of well-chosen inequalities has been much the object of much interest in the past in the mathematical programming community, as stronger LP relaxations are extremely useful to speed up branch-and-bound heuristics. The knapsack polytope was studied in detail by Weismantel . Valid inequalities were studied in . In particular, whenever $S$ is a minimal set (w.r.to inclusion) that does not fit in the knapsack, then $\sum_{S\cup\{j:\forall i\in S,w_{j}\geq w_{i}\}}x_{j}\leq|S|-1$ is a valid inequality. Generalizations and variations were also studied in . Thus, in spite of the existence of a dynamic program to solve the problem, ${\mathsf{Knapsack}}$ is fundamental enough that understanding the polytope (and its lifted tightenings) is of intrinsic interest. In , Bienstock formulated LP with arbitrary small integrality gaps for ${\mathsf{Knapsack}}$ using “structural disjunctions”, and asked if the popular hierarchies reduce the gap of the ${\mathsf{Knapsack}}$ linear program. Our results give a negative answer for Sherali-Adams and a strong affirmative one for Lasserre.

Our results confirm the indication from for example that the Sherali-Adams lift and project is not powerful enough to be an indicator of the hardness of problems. However, it should be noted that if the problem was phrased as a decision problem and the objective function was replaced by an additional constraint of the constraint polytope, then Sherali-Adams would succeed in reducing the integrality gap; thus the choice of the initial LP formulation is critical. On the other hand, little is know about the Lasserre hierarchy, as the first negative results were about $k$-CSP . Our positive result leaves open the possibility that the Lasserre hierarchy may have promise as a tool to capture the intrinsic difficulty of problems.

Preliminaries

Our focus in this paper is on the ${{\mathsf{Knapsack}}}$ problem. In the ${{\mathsf{Knapsack}}}$ problem, we are given a set of $n$ objects $V=[n]$ with sizes $c_{1},c_{2},\ldots c_{n}$, values $v_{1},v_{2},\ldots v_{n}$, and a capacity $C$. We assume that for every $i$, $c_{i}\leq C$. The objective is to select a subset of objects of maximum total value such that the total size of the objects selected does not exceed $C$.

The standard linear programming (LP) relaxation for ${{\mathsf{Knapsack}}}$ is given by:

The intended intepretation of an integral solution of this LP is obvious: $x_{i}=1$ means the object $i$ is selected, and $x_{i}=0$ means it is not. The constraint can be written as $g(x)=C-\sum_{i}c_{i}x_{i}\geq 0$.

Let Greedy denote the algorithm that puts objects in the knapsack by order of decreasing ratio $v_{i}/c_{i}$, stopping as soon as the next object would exceed the capacity. The following lemma is folklore.

Consider an instance $(C,V)$ of ${{\mathsf{Knapsack}}}$ and its LP relaxation $K$ given by (1). Then

2 The Sherali-Adams and Lasserre hierarchies

We next review the lift-and-project hierarchies that we will use in this paper. The descriptions we give here assume that the base program is linear and mostly use the notation given in the survey paper by Laurent . To see that these hierarchies apply at a much greater level of generality we refer the reader to Laurent’s paper .

Let $K$ be a polytope defined by a set of linear constraints $g_{1},g_{2},\ldots g_{m}$:

We are interested in optimizing a linear objective function $f$ over the convex hull $P={{\mathsf{conv}}\left(K{\cap}{\left\{0,1\right\}}^{n}\right)}$ of integral points in $K$. Here, $P$ is the set of convex combinations of all integral solutions of the given combinatorial problem and $K$ is the set of solutions to its linear relaxation. For example, if $K$ is defined by (1), then $P$ is the set of convex combinations of valid integer solutions to ${{\mathsf{Knapsack}}}$.

If all vertices of $K$ are integral then $P=K$ and we are done. Otherwise, we would like to strengthen the relaxation $K$ by adding additional valid constraints. The Sherali-Adams (SA) and Lasserre hierarchies are two different systematic ways to construct these additional constraints. In the SA hierarchy, all the constraints added are linear, whereas Lasserre’s hierarchy is stronger and introduces a set of positive semi-definite constraints. However, for consistency, we will describe both hierarchies as requiring certain submatrices to be positive semi-definite (readers who are not familiar with the following formulation of SA are referred to Appendix B for a linear formulation of the hierarchy.)

To this end, we first state some notation. Throughout this paper we will use ${{\mathcal{P}\left(V\right)}}$ to denote the power set of $V$, and ${{\mathcal{P}_{t}\left(V\right)}}$ to denote the collection of all subsets of $V$ whose sizes are at most $t$. Also, given two sets of coordinates $T$ and $S$, $T\subseteq S$ and $y\in R^{S}$, by ${y|_{T}}$ we denote the projection of $y$ onto $T$.

Next, we review the definition of the shift operator between two vectors $x,y\in R^{{{\mathcal{P}\left(V\right)}}}$: $x*y$ is a vector in $R^{{{\mathcal{P}\left(V\right)}}}$ such that

The shift operator is commutative: for any vectors $x,y,z\in R^{{{\mathcal{P}\left(V\right)}}}$, we have $x*(y*z)=y*(x*z)$.

A polynomial $P(x)=\sum_{I\subseteq V}a_{I}\prod_{i\in I}x_{i}$ can also be viewed as a vector indexed by subsets of $V$. We define the vector $P*y$ accordingly: $(P*y)_{I}=\sum_{J\subseteq V}a_{J}y_{I{\cup}J}.$

Finally, let $\cal T$ be a collection of subsets of $V$ and $y$ be a vector in $R^{\cal T}$. We denote by $M_{\cal T}(y)$ the matrix whose rows and colums are indexed by elements of $\cal T$ such that

We say that a point $x\in^{n}$ belongs to the $t$-th Sherali-Adams polytope ${{{\mathsf{sa}}^{t}\left(K\right)}}$ iff there exists a $y\in{{{\mathsf{SA}}^{t}\left(K\right)}}$ such that $y_{\left\{i\right\}}=x_{i}$ for all $i\in[n]$.

We say that a point $x\in^{n}$ belongs to the $t$-th Lasserre polytope ${{{\mathsf{la}}^{t}\left(K\right)}}$ if there exists a $y\in{{{\mathsf{La}}^{t}\left(K\right)}}$ such that $y_{\left\{i\right\}}=x_{i}$ for all $i\in V$.

Note that $M_{{{\mathcal{P}\left(U\right)}}}(y)$ has at most $2^{t}$ rows and columns, which is constant for $t$ constant, whereas $M_{{{\mathcal{P}_{t}\left(V\right)}}}(y)$ has ${n+1\choose t+1}$ rows and columns.

It is immediate from the definitions that ${{{\mathsf{sa}}^{t+1}\left(K\right)}}\subseteq{{{\mathsf{sa}}^{t}\left(K\right)}}$, and ${{{\mathsf{la}}^{t+1}\left(K\right)}}\subseteq{{{\mathsf{la}}^{t}\left(K\right)}}$ for all $1\leq t\leq n-1$. Sherali and Adams show that ${{{\mathsf{sa}}^{n}\left(K\right)}}=P$, and Lasserre show that ${{{\mathsf{la}}^{n}\left(K\right)}}=P$. Thus, the sequences

define hierarchies of polytopes that converge to $P$. Furthermore, the Lasserre hierarchy is stronger than the Sherali-Adams hierarchy: ${{{\mathsf{la}}^{n}\left(K\right)}}\subseteq{{{\mathsf{sa}}^{n}\left(K\right)}}$. In this paper, we show that for the ${{\mathsf{Knapsack}}}$ problem, the Lasserre hierarchy is strictly stronger.

Lower bound for the Sherali-Adams hierarchy for 𝖪𝗇𝖺𝗉𝗌𝖺𝖼𝗄𝖪𝗇𝖺𝗉𝗌𝖺𝖼𝗄{\mathsf{Knapsack}}

In this section, we show that the integrality gap of the $t$-th level of the Sherali-Adams hierarchy for ${{\mathsf{Knapsack}}}$ is close to $2$. This lower bound even holds for the uniform ${{\mathsf{Knapsack}}}$ problem, in which $v_{i}=c_{i}=1$ for all $i$ Some people call this problem Unweighted Knapsack or Subset Sum..

For every $\epsilon,\delta>0$, the integrality gap at the $t$-th level of the Sherali-Adams hierarchy for ${{\mathsf{Knapsack}}}$ where $t\leq\delta n$ is at least $(2-\epsilon)(1/(1+\delta))$.

Proof. (Sketch - for full proof see Appendix A.) Consider the instance $K$ of ${{\mathsf{Knapsack}}}$ with $n$ objects where $c_{i}=v_{i}=1$ for all $i\in V$ and capacity $C=2(1-\epsilon)$. Then the optimal integer value is 1. On the other hand, we claim that the vector $y$ where $y_{\emptyset}=1$, $y_{\left\{i\right\}}=C/(n+(t-1)(1-\epsilon))$ and $y_{I}=0$ for all $|I|>1$ is in ${{{\mathsf{SA}}^{t}\left(K\right)}}$. Thus, the integrality gap of the $t$th round of Sherali-Adams is at least $Cn/(n+(t-1)(1-\epsilon))$, which is at least $(2-\epsilon)(1/(1+\delta))$ when $t\leq\delta n.$ qed

A decomposition theorem for the Lasserre hierarchy

In this section, we develop the machinery we will need for our Lasserre upper bounds. It turns out that it is more convenient to work with families $(z^{X})$ of characteristic vectors rather than directly with $y$. We begin with some definitions and basic properties.

Let ${\cal T}$ be a collection of subsets of $V$ and let $y$ be a vector indexed by sets of $\cal T$. We define the extension of $y$ to be the vector $y^{\prime}$, indexed by all subsets of $V$, such that $y^{\prime}_{I}$ equals $y_{I}$ if $I\in\cal T$ and equals otherwise.

Let $S$ be a subset of $V$ and $X$ a subset of $S$. We define the characteristic polynomial $P^{X}$ of $X$ with respect to $S$ as

Let $y^{\prime}$ be a vector indexed by all subsets of $V$. Let $S$ be a subset of $V$ and, for each $X$ subset of $S$, let $z^{X}=P^{X}*y^{\prime}$:

Then $y^{\prime}=\sum_{X\subseteq S}z^{X}$.

Proof. Fix a subset $I$ of $V$. Substituting the definition of $z^{X}_{I}$ in $\sum_{X\subseteq S}z^{X}_{I}$, and changing the index of summation, we get

For $A\neq\emptyset$ the inner sum is 0, so only the term for $A=\emptyset$, which equals $y^{\prime}_{I}$, remains. qed

Let $y^{\prime}$ be a vector indexed by all subsets of $V$, $S$ be a subset of $V$ and $X$ be a subset of $S$. Then

Proof. Let $I^{\prime}=I\setminus X$ and $I^{\prime\prime}=I{\cap}X$. Using the definition of $z^{X}_{I}$ and noticing that $X\cup I^{\prime\prime}=X$ yields $z^{X}_{I}=z^{X}_{I^{\prime}}$. This immediately implies that for $I\subseteq X$, $z^{X}_{I}=z^{X}_{\emptyset}$.

Finally, consider a set $I$ that intersects $S\setminus X$ and let $i\in I{\cap}(S\backslash X)$. In the definition of $z^{X}_{I}$, we group the terms of the sum into pairs consisting of $J$ such that $i\notin J$ and of $J\cup\{i\}$. Since $I=I\cup\{i\}$, we obtain:

Let $y^{\prime}$ be a vector indexed by all subsets of $V$, $S$ be a subset of $V$ and $X$ be a subset of $S$. Let $w^{X}$ be defined as $z^{X}/z^{X}_{\emptyset}$ if $z^{X}_{\emptyset}\neq 0$ and defined as 0 otherwise. Then, if $z^{X}_{\emptyset}\neq 0$, then $w^{X}_{\{i\}}$ equals 1 for elements of $X$ and 0 for elements of $S\setminus X$.

Let $S$ be an arbitrary subset of $V$ and $\cal T$ be a collection of subsets of $V$. We say that $\cal T$ is closed under shifting by S if

The following lemma generalizes Lemma 5 in . It proves that the positive-semidefinite property carries over from $y$ to $(z^{X})$.

Let $S$ be an arbitrary subset of $V$ and $\cal T$ be a collection of subsets of $V$ that is closed under shifting by $S$. Let $y$ be a vector indexed by sets of $\cal T$. Then

Proof. Since $M_{\cal T}(y){\succeq 0}$, there exist vectors $v_{I}$, $I\in{\cal T}$, such that ${\langle v_{I},v_{J}\rangle}=y_{I{\cup}J}$. Fix a subset $X$ of $S$. For each $I\in{\cal T}$, let

which is well-defined since $\cal T$ is closed under shifting by $S$.

Let $I,J\in\cal T$. It is easy to check that ${\langle w_{I},w_{J}\rangle}=(z^{X})_{I{\cup}J}$. Indeed,

by definition of $v_{I},v_{J}$ and since $\cal T$ is closed under shifting by $S$ (so that this is well-defined). Consider a non-empty subset $H$ of $S\setminus X$ and let $i\in H$. We group the terms of the inner sum into pairs consisting of $L$ such that $i\notin L$ and of $L\cup\{i\}$. Since $H=H\cup\{i\}$, we obtain:

This implies that $M_{\cal T}(z^{X}){\succeq 0}$. qed

In the rest of the section, we prove a decomposition theorem for the Lasserre hierarchy, which allows us to “divide” the action of the hierarchy and think of it as using the first few rounds on some subset of variables, and the other rounds on the rest. We will use this theorem to prove that the Lasserre hierarchy closes the gap for the ${{\mathsf{Knapsack}}}$ problem in the next section.

Let $t>1$ and $y\in{{{\mathsf{La}}^{t}\left(K\right)}}$. Let $k<t$ and $S$ be a subset of $V$ and such that

Consider the projection ${y|_{{{\mathcal{P}_{2t-2k}\left(V\right)}}}}$ of $y$ to the coordinates corresponding to subsets of size at most $2t-2k$ of $V$. Then there exist subsets $X_{1},X_{2},\ldots,X_{m}$ of $S$ such that ${y|_{{{\mathcal{P}_{2t-2k}\left(V\right)}}}}$ is a convex combination of vectors $w^{X_{i}}$ with the following properties:

w^{X_{i}}_{\{j\}}=\left\{\begin{array}[]{ll}1&\text{ if }j\in X_{i}\\ 0&\text{ if }j\in S\setminus X_{i};\end{array}\right.

$w^{X_{i}}\in{{{\mathsf{La}}^{t-k}\left(K\right)}}$; and

if $K_{i}$ is obtained from $K$ by setting $x_{j}=w^{X_{i}}_{\{j\}}$ for $j\in S$, then ${w^{X_{i}}|_{{{\mathcal{P}_{2t-2k}\left(V\backslash S\right)}}}}\in{{{\mathsf{La}}^{t-k}\left(K_{i}\right)}}$.

To prove Theorem 13, we will need a couple more lemmas. In the first one, using assumption (5), we extend the positive semi-definite properties from $y$ to $y^{\prime}$, and then, using Lemma 12, from $y^{\prime}$ to $z^{X}$.

where $M$ is a principal submatrix of $M_{{{\mathcal{P}_{t}\left(V\right)}}}(y)$.Thus $M{\succeq 0}$, and so $M_{{\cal T}_{1}}(y^{\prime}){\succeq 0}$.

Observe that ${\cal T}_{1}$ is closed under shifting by $S$. By definition of $z^{X}$ and Lemma 12, we thus get $M_{{\cal T}_{1}}(z^{X}){\succeq 0}$.

Let $t,y,S,k$ be defined as in Theorem 13, and $y^{\prime}$ be the extension of $y$. Then for any $X\subseteq S$:

If $z^{X}_{\emptyset}=0$ then $z^{X}_{I}=0$ for all $|I|\leq 2t-2k$.

Proof. Let ${\cal T}_{1}$ be defined as in Lemma 14. By Lemma 14 $M_{{\cal T}_{1}}(z^{X}){\succeq 0}$ and $z^{X}_{\emptyset}$ is a diagonal element of this matrix, hence $z^{X}_{\emptyset}\geq 0$.

For the second part, start by considering $J\subseteq V$ of size at most $t-k$. Then $J\in{\cal T}_{1}$, and so the matrix $M_{\left\{\emptyset,J\right\}}(z^{X})$ is a principal submatrix of $M_{{\cal T}_{1}}(z^{X})$, hence is also positive semidefinite. Since $z^{X}_{\emptyset}=0$,

Now consider any $I\subseteq V$ such that $|I|\leq 2t-2k$, and write $I=I_{1}{\cup}I_{2}$ where $|I_{1}|\leq t-k$ and $|I_{2}|\leq t-k$. $M_{\left\{I_{1},I_{2}\right\}}(z^{X})$ is a principal submatrix of $M_{{\cal T}_{1}}(z^{X})$, hence is also positive semidefinite. Since $z^{X}_{I_{1}}=z^{X}_{I_{2}}=0$, Since

We now have what we need to prove Theorem 13.

Proof of Theorem 13. By definition, Lemma 8 and the second part of Lemma 15, we have

By Lemma 8 and by definition of $y$, we have $\sum_{X\subseteq S}{z^{X}_{\emptyset}}=y_{\emptyset}=1$, and the terms are non-negative by the first part of Lemma 15, so ${y|_{{{\mathcal{P}_{2t-2k}\left(V\right)}}}}$ is a convex combination of $w^{X}$’s, as desired.

By Lemma 9, $w^{X_{i}}_{I{\cup}{\left\{j\right\}}}=w^{X_{i}}_{I}$ for $j\in X_{i}$ and $w^{X_{i}}_{I{\cup}{\left\{j\right\}}}=0$ for $j\in S\backslash X_{i}$. The claim follows. qed

Upper bound for the Lasserre hierarchy for 𝖪𝗇𝖺𝗉𝗌𝖺𝖼𝗄𝖪𝗇𝖺𝗉𝗌𝖺𝖼𝗄{\mathsf{Knapsack}}

In this section, we use Theorem 13 to prove that for the ${{\mathsf{Knapsack}}}$ problem the gap of ${{{\mathsf{La}}^{t}\left(K\right)}}$ approaches $1$ quickly as $t$ grows, where $K$ is the LP relaxation of (1). First, we show that there is a set $S$ such that every feasible solution in ${{{\mathsf{La}}^{t}\left(K\right)}}$ satisfies the condition of the Theorem.

Given an instance $(C,V)$ of ${{\mathsf{Knapsack}}}$, Let $OPT(C,V)$ denote the value of the optimal integral solution.

Consider an instance $(C,V)$ of ${{\mathsf{Knapsack}}}$ and its linear programming relaxation $K$ given by (1). Let $t>1$ and $y\in{{{\mathsf{La}}^{t}\left(K\right)}}$. Let $k<t$ and $S={\left\{i\in V{\left|v_{i}>{OPT(C,V)}/{k}\right.}\right\}}$. Then:

Proof. There are three cases depending on the size of $I$:

$|I|\leq t-1$. Recall the capacity constraint $g(x)=C-\sum_{i\in V}c_{i}x_{i}\geq 0$. On the one hand, since $M_{{{\mathcal{P}_{t-1}\left(V\right)}}}(g*y){\succeq 0}$, the diagonal entry $(g*y)_{I}$ must be non-negative. On the other hand, writing out the definition of $(g*y)_{I}$ and noting that the coefficients $c_{i}$ are all non-negative, we infer $(g*y)_{I}\leq Cy_{I}-\left(\sum_{i\in I}c_{i}\right)y_{I}$. But by assumption, $\sum_{i\in I}c_{i}>C$. Thus we must have $y_{I}=0$.

$t\leq|I|\leq 2t-2$. Write $I=I_{1}{\cup}I_{2}=I$ with $|I_{1}|,|I_{2}|\leq t-1$ and $|I_{1}{\cap}S|\geq k$. Then $y_{I_{1}}=0$. Since $M_{{{\mathcal{P}_{t}\left(y\right)}}}{\succeq 0}$, its 2-by-2 principal submatrix $M_{\left\{I_{1},I_{2}\right\}}(y)$ must also be positive semi-definite.

and it is easy to check that we must then have $y_{I}=0$.

$2t-1\leq|I|\leq 2t$. Write $I=I_{1}{\cup}I_{2}=I$ with $|I_{1}|,|I_{2}|\leq t$ and $|I_{1}{\cap}S|\geq k$. Then $y_{I_{1}}=0$ since $t\leq 2t-2$ for all $t\geq 2$. By the same argument as in the previous case, we must then have $y_{I}=0$.

The following theorem shows that the integrality gap of the $t^{th}$ level of the Lasserre hierarchy for ${{\mathsf{Knapsack}}}$ reduces quickly when $t$ increases.

Consider an instance $(C,V)$ of ${{\mathsf{Knapsack}}}$ and its LP relaxation $K$ given by (1). Let $t\geq 2$. Then

and so the integrality gap at the $t$-th level of the Lasserre hierarchy is at most $1+1/(t-1)$.

Proof. Let $S={\left\{i\in V{\left|v_{i}>{OPT(C,V)}/{(t-1)}\right.}\right\}}$. Let $y\in{{{\mathsf{La}}^{t}\left(K\right)}}$. If $|I{\cap}S|\geq t-1$, then the elements of $I\cap S$ have total value greater than $OPT(C,V)$, so they must not be able to fit in the knapsack: their total capacity exceeds $C$, and so by Lemma 16 we have $y_{I}=0$. Thus the condition of Theorem 13 holds for $k=t-1$.

Therefore, ${y|_{{{\mathcal{P}_{2}\left(V\right)}}}}$ is a convex combination of $w^{X_{i}}$ with $X_{i}\subseteq S$, thus $\text{Value}(y)\leq\max_{i}\text{Value}(w^{X_{i}})$. By the first and third properties of the Theorem, we have:

By the nesting property of the Lasserre hierarchy, Lemma 1, and definition of $S$,

By the second property of the Theorem, $w^{X_{i}}$ is in ${{{\mathsf{La}}^{t-k}\left(K\right)}}\subseteq K$, so it must satisfy the capacity constraint, so $\sum_{i\in X_{i}}c_{i}\leq\sum_{i\in I}c_{i}\leq C$, so $X_{i}$ is feasible. Thus:

The first expression in the right hand side is equal to $OPT(C,V)$, hence the Theorem. qed

Conclusion

We have shown that for ${{\mathsf{Knapsack}}}$, an integrality gap of $2-\epsilon$ persists up to a linear number of rounds in the Sherali-Adams hierarchy. This broadens the class of problems for which Sherali-Adams is not strong enough to capture the instrinsic difficulity of problems.

On the other hand, our positive result for Lasserre opens the posibility that lower bounds in the Lasserre hierarchy good indicators of the intrinsic dificulty of the problem, thus encourages more investigation on the effect of the hierarchy on “easy” problems (${\mathsf{SpanningTree}}$, ${\mathsf{BinPacking}}$, etc.)

Acknowledgement

Clare Mathieu would like to thank Eden Chlamtac for stimulating discussions.

References

Appendix

Appendix A Full proof of Theorem 5

Proof. Let $t\geq 2$. Consider the instance $K$ of ${{\mathsf{Knapsack}}}$ with $n$ objects where $c_{i}=v_{i}=1$ for all $i\in V$ and capacity $C=2(1-\epsilon)$. Let $\alpha={C}/({n+(t-1)(1-\epsilon)})$ and consider the vector $y\in^{{{\mathcal{P}_{t}\left(V\right)}}}$ defined by

We claim that $y\in{{{\mathsf{SA}}^{t}\left(K\right)}}$. Consider any subset $U\subseteq V$ such that $|U|\leq t$. We have

Since $|U|\leq t<n$, $|U|\alpha\leq 1$, and it is easy to see that this implies $M_{{{\mathcal{P}_{1}\left(U\right)}}}(y){\succeq 0}$, and so $M_{{{\mathcal{P}\left(U\right)}}}(y){\succeq 0}$.

Next, let $g(x)=C-\sum_{i\in V}c_{i}x_{i}$ and consider any subset $W\subseteq V$ such that $|W|\leq t-1$. Again, we have

Since $|W|\leq t-1$, by definition of $\alpha$ we have $|W|(C-1)\alpha\leq C-n\alpha$, and it is easy to see that this implies $M_{{{\mathcal{P}_{1}\left(W\right)}}}(g*y){\succeq 0}$, and so $M_{{{\mathcal{P}\left(W\right)}}}(g*y){\succeq 0}$. Thus $y\in{{{\mathsf{SA}}^{t}\left(K\right)}}$.

The integer optimum has value 1, so the integrality gap is at least the value of $y$, which is $n\alpha=2(1-\epsilon)/(1+(t-1)(1-2\epsilon)/n)$. The supremum over all $\epsilon$ is $2/(1+(t-1)/n)$, and the supremum of that over all $n$ is 2, so the integrality gap is at least 2.

On the other hand, it is well-known that the base linear program $K$ has value at most $2OPT$ (that is an immediate consequence of Lemma 1), hence, by the nesting property, every linear program in the hierarchy has integrality gap exactly equal to 2. qed

Appendix B A linear formulation of the Sherali-Adams hierarchy

If $x$ is indeed integral, then $x_{i}^{k}=x_{i}$ for any $k\geq 1$. Thus, the constraint obtained by expanding (6) and replacing $x_{i}^{k}$ by $x_{i}$ holds in $P$ and can be added to strengthen the relaxation. However, this constraint is not linear. To preserve the linearity of the system, each product $\prod_{i\in I}x_{i}$ is replaced by a variable $y_{I}$.

In addition, to keep the number of variables from growing exponentially, we restrict ourselves to only variables $y_{I}$ such that $|I|\leq t$. By this, we “lift” the polytope $K$ to a polytope ${{{\mathsf{SA}}^{t}\left(K\right)}}\subseteq^{{{\mathcal{P}_{t}\left(V\right)}}}$.

Let $K$ be a polytope defined as in equation 2. For any $1\leq t\leq n$, the $t$-th Sherali-Adams lifted polytope ${{{\mathsf{SA}}^{t}\left(K\right)}}$ is defined by

expanding the result and replacing each $x_{i}^{k}$ by $x_{i}$; and

replacing each $\prod_{i\in S}x_{i}$ by $y_{S}$.

We say that a point $x\in^{V}$ belongs to the $t$-th Sherali-Adams polytope ${{{\mathsf{sa}}^{t}\left(K\right)}}$ iff there exists a $y\in{{{\mathsf{SA}}^{t}\left(K\right)}}$ such that $y_{\left\{i\right\}}=x_{i}$ for all $i\in V$.

In particular, in the case of ${{\mathsf{Knapsack}}}$, ${{{\mathsf{SA}}^{t}\left(K\right)}}$ is the set of all points in $^{{{\mathcal{P}_{t}\left(V\right)}}}$ that satisfy the following constraints for any $I,J\subseteq V$ such that $I{\cap}J=\emptyset$ and $|I|+|J|\leq t-1$:

For a proof that this definition is equivalent to Definition 3, we refer the reader to Laurent’s paper .