Rank bounds for a hierarchy of Lovász and Schrijver

Lovász and Schrijver introduced several lift and project methods for 0–1 integer programs, now collectively known as Lovász–Schrijver (LS) hierarchies. Several lower bounds have since been proven for the rank of various linear programming relaxations in the LS and \(\hbox {LS}_+\) hierarchies. We investigate rank bounds in the more general \(\hbox {LS}_*\) hierarchy, which allows lifts by any derived inequality as opposed to just \(x\ge 0\) and \(1-x\ge 0\) in the LS hierarchy. Rank lower bounds for \(\hbox {LS}_*\) were obtained for the symmetric knapsack polytope by Grigoriev et al. We reinitiate further investigation into such general lifts. We prove simple upper bounds on rank which show that under such general lifts one can potentially converge to the integer solution much faster than \(\hbox {LS}_+\) or Sherali–Adams (SA) hierarchy. This motivates our investigation of rank lower bounds and integrality gaps for \(\hbox {LS}_*\) and the \(\hbox {SA}_*\) hierarchy, the latter is a generalization of the SA hierarchy in the same vein as \(\hbox {LS}_*\). In particular, we show that the \(\hbox {LS}_*\) rank of \(PHP_n^{n+1}\) is \(\sim \log _2n\). We also extend the rank lower bounds and integrality gaps for SA hierarchy to the \(\hbox {LS}_*\) and \(\hbox {SA}_*\) hierarchies as long as the maximum number of variables in any constraint of the initial linear program is bounded by a constant.

1. For example, the one in Benabbas et al. (2012).

2. In this paper, we will be mainly concerned with the characterization of LS and SA which is based on lifted constraints. Hence, we do not give a moment matrix definition of the SA hierarchy but it can be found in Laurent (2003).

3. Recall that, we assume that our polytopes have polynomially many facets i.e., \(m=\mathrm{poly}(n)\).

4. Note that the subpolytope still subsumes the corresponding integer polytope.

5. Already, Sherali et al. (1998) provides a more general claim than Theorem 4, but without formal details.

The author thanks Yury Makarychev for reading several drafts of this paper and also for his help with proofs in Sect. 7. The author thanks Alexander Razborov for introducing him to the problem and the subject, and for comments on an earlier draft. The author thanks Madhur Tulsiani for comments and helpful discussions regarding the presentation of the final draft and Janos Simon for his encouragement.

Authors and Affiliations

1. Courant Institute of Mathematical Sciences, New York, NY, 10012, USA

   Pratik Worah

Corresponding author

Correspondence to Pratik Worah.

Work done while the author was at the University of Chicago.

A matching polytope

A proof of Lemma 5, is repeated from Mathieu and Sinclair (2009) for convenience.

Proof

Given an optimal solution \(y\) of the lifted maximum matching linear program permute the vertices of \(K_{2n+1}\) to obtain, by symmetry, another optimal solution \(\sigma (y)\). Define \(y^s\) to be the solution obtained after component-wise averaging over all \((2n+1)!\) solutions over permuted instances and we observe that \(y^s\) is still optimal and feasible.

B \(\hbox {LS}_+\) rank lower bound for \(K_\alpha ^n\)

The following defintions are required for the \(\hbox {LS}_+\) rank lower bound from Sect. 5. Let \(e_i\) denote the \(i\)th standard unit vector (where the dimension will be clear from the context) and in particular, \(e_0\) stands for the unit vector in \(\mathbb {R}^{n+1}\) with a \(1\) in the \(0^{th}\) coordinate. Let \(e\) denote the all \(1\)s vector. For \(a\in \mathbb {R}^{n+1}\) define \(\bar{a}\in \mathbb {R}^n\) as \(a=(1,\bar{a})\). Let \(F_i^0\) denote the face of \(Q\) with \(i\)th coordinate set to \(0\).

Definition 16

(Cook and Dash 2001) Define embedding \(emb_I:\mathbb {R}^n\rightarrow \mathbb {R}^{n+k}\) such that if \(y=emb_I(x)\) then \(y_{i_j}=x_j\) for \(I:=\{i_j\in [n+k]| j\in [n]\}\), and \(y_i\in \{0,1\}\) for \(i\not \in I\).

For a face \(F\) of \(Q_n\) let \(emb_F\) denote the embedding where \(Q_{dim(F)}\mapsto F\) (i.e. \(emb_F\) is short for \(emb_I\), \(I=[n]\setminus \{i\}\) where \(i\) is the coordinate fixed to \(\{0,1\}\) in \(F\)). Lemma 2.1 in Cook and Dash (2001) is restated below

Lemma 10

(Cook and Dash 2001) Given polytope \(P\subseteq Q\) and embedding \(emb:\mathbb {R}^n\rightarrow \mathbb {R}^m\), \(N_+(emb(P))=emb(N_+(P))\).

Theorem 10

The \(\hbox {LS}_+\) rank of \(K_\alpha ^n\) is \(n\).

Proof

It suffices to show \(y^{k,n}e_0\in N_+^k(K_\alpha ^n)\) for \(k<n\) and some \(y^{k,n}\in \mathbb {R}^{(n+1)\times (n+1)}\) defined below. Let

and \(y^{k,n}\) is \(0\) elsewhere. Hence \(y^{k,n}\) is a symmetric, positive semidefinite (diagonally dominant) matrix for all \(k<n\). Note that \(\sum _{i\in [n]} y_{\{i\}}^{k,n}< 1\) as required.

The proof proceeds by induction on \(k,n\). In the base case \(n=1\) and \(k=0\) the hypothesis holds. Suppose the induction hypothesis (i.e. \(y^{k,n}e_0\in N_+^k(K_\alpha ^n)\) for \(k<n\)) holds for \(K_\alpha ^{n-1}\) with \(n\ge 2\) and \(k<n\).

For brevity let \(y^{k,n}\) defined above be denoted by \(y\). Observe that \(\overline{ye_i}\) is a positive multiple of \(e_i\in (K_\alpha ^n)_I\) therefore \(\overline{ye_i}\in N_+^{k-1}(K_\alpha ^n)\) for \(k<n\).

Let \(z_i = y(e_0-e_i)\). Then

So \(\bar{z_i}\in F_i^0\). Also \(\frac{\alpha }{n-(1-\alpha )k-\alpha }e = \frac{\alpha }{n-1-(1-\alpha )(k-1)}e\) hence by induction hypothesis

The equality on the RHS of the implication above follows from Lemma 10 and the observation \(K_\alpha ^n\cap F_i^0=emb_{F_i^0}(K_\alpha ^{n-1})\). Hence \(y\in M_+(N^{k-1}_+(K_\alpha ^n))\) for \(k<n\) and so \((y_{\{i\}})\in N^k_+(K_\alpha ^n)\). Hence the proof follows.

Reprints and permissions