Breaking symmetries to rescue sum of squares in the case of makespan scheduling

Abstract

The sum of squares (SoS) hierarchy gives an automatized technique to create a family of increasingly tight convex relaxations for binary programs. There are several problems for which a constant number of rounds of this hierarchy give integrality gaps matching the best known approximation algorithms. For many other problems, however, ad-hoc techniques give better approximation ratios than SoS in the worst case, as shown by corresponding lower bound instances. Notably, in many cases these instances are invariant under the action of a large permutation group. This yields the question how symmetries in a formulation degrade the performance of the relaxation obtained by the SoS hierarchy. In this paper, we study this for the case of the minimum makespan problem on identical machines. Our first result is to show that $\varOmega (n)$ rounds of SoS applied over the configuration linear program yields an integrality gap of at least 1.0009, where n is the number of jobs. This improves on the recent work by Kurpisz et al. (Math Program 172(1–2):231–248, 2018) that shows an analogous result for the weaker $\hbox {LS}_{+}$ and SA hierarchies. Our result is based on tools from representation theory of symmetric groups. Then, we consider the weaker assignment linear program and add a well chosen set of symmetry breaking inequalities that removes a subset of the machine permutation symmetries. We show that applying $2^{\tilde{O}(1/\varepsilon ^2)}$ rounds of the $\text {SA}$ hierarchy to this stronger linear program reduces the integrality gap to $1+\varepsilon$, which yields a linear programming based polynomial time approximation scheme. Our results suggest that for this classical problem, symmetries were the main barrier preventing the $\text {SoS}/\text {SA}$ hierarchies to give relaxations of polynomial complexity with an integrality gap of $1+\varepsilon$. We leave as an open question whether this phenomenon occurs for other symmetric problems.

Appendices

Appendix A: Proof of Theorem 4

We show how to prove Theorem 4 following the lines in the work of Raymond et al. [45]. We need a few intermediate results, and the symmetry reduction theorem from Gaterman and Parrilo [13], stated in our setting.

Theorem 10

([13]) Suppose that $g\in {\mathbb {R}}[y]/\mathbf{sched}$ is a degree-$\ell \ \text {SoS}$ and $S_m$-invariant polynomial. For each partition $\lambda \vdash m$, let $\tau _{\lambda }$ be a tableau of shape $\lambda$ and let $\{b_1^{\lambda },\ldots ,b_{m_{\lambda }}^{\lambda }\}$ be a basis $\mathbf{W }_{\tau _{\lambda }}$. Then, for each partition $\lambda \vdash m$ there exists a $m_{\lambda }\times m_{\lambda }$ positive semidefinite matrix $Q_{\lambda }$ such that $g=\sum _{\lambda \vdash m}\langle Q_{\lambda },Y^{\lambda }\rangle$, where $Y^{\lambda }_{ij}=\text {sym}(b_i^{\lambda }b_j^{\lambda })$.

Given two partitions $\lambda ,\mu$, we say that $\lambda \unrhd \mu$ if $\lambda \ge _{\text {lex}} \mu$ and the number of parts of $\mu$ is at least the number of parts of $\lambda$. The following lemma is a variant of [45, Theorem 2] for the action of the symmetric group in our setting. Together with the theorem of Gatermann and Parrilo this yields Theorem 4.

Lemma 18

The dimension $m_{\lambda }$ of ${\mathbf{Q}}^{\ell }_{\lambda }$ in the isotypic decomposition of $\mathbf{Q}^{\ell }$ is zero unless $\lambda \ge _{\text {lex}} (m-\ell ,1,\ldots ,1)$.

Proof

Let $y_S$ be a monomial of degree at most $\ell$ with $S=\{(i_k,C_k):k\in [\ell ]\}$. In particular, $|\{i_k:k\in [\ell ]\}|\le \ell$. Let $\tau$ be any tableau with shape $(m-\ell ,1,\ldots ,1)$, where the tail of $\tau$ contains every elements of $\{i_k:k\in [\ell ]\}$. The subgroup ${{\mathcal {R}}}_{\tau }$ fixes S, therefore $y_S\in {\mathbf{W}}^{\ell }_{\tau }$, and we have then

$$\begin{aligned} {\mathbf{Q}}^{\ell }\subseteq \bigoplus _{\tau :\text {shape}(\tau ) =(m-\ell ,1,\ldots ,1)}{\mathbf{W}}^{\ell }_{\tau }\subseteq \bigoplus _{\lambda \unrhd (m-\ell ,1,\ldots ,1)}{\mathbf{Q}}^{\ell }_{\lambda }, \end{aligned}$$

where the second containment holds by [45, Lemma 1]. To conclude, observe that if $\lambda \unrhd (m-\ell ,1,\ldots ,1)$ then $\lambda _1\ge m-\ell$. Since $\lambda \vdash m$, the maximum number of parts for $\lambda$ is $m-\lambda _1\le \ell$, that is, $\lambda$ has at most $\ell +1$ parts. Therefore, $\lambda \unrhd (m-\ell ,1,\ldots ,1)$ if and only if $\lambda \ge _{\text {lex}} (m-\ell ,1,\ldots ,1)$. $\square$

Proof of Theorem 4

Let $g\in {\mathbb {R}}[y]/\mathbf{sched}$ be a degree-$\ell \ \text {SoS}$ and $S_m$-invariant polynomial. By Theorem 10 and Lemma 18, for each $\lambda \in \varLambda _{\ell }$ there exists a positive semidefinite matrix $Y^{\lambda }$ such that $g=\sum _{\lambda \in \varLambda _{\ell }}\langle Q_{\lambda },Y^{\lambda }\rangle$. Since $\{b_1^{\lambda },\ldots ,b_{m_{\lambda }}^{\lambda }\}\subseteq \text {span}({{\mathcal {P}}}^{\lambda })$, there exists a real matrix ${{\mathcal {T}}}_{\lambda }$ such that ${{\mathcal {T}}}_{\lambda }(p_1^{\lambda }, \ldots ,p_{\ell _{\lambda }}^{\lambda })=(b_1^{\lambda },\ldots ,b_{m_{\lambda }}^{\lambda })$. Consider the congruent transformation $M_{\lambda } ={{\mathcal {T}}}_{\lambda }^{\top }Q_{\lambda }{{\mathcal {T}}}_{\lambda }$. In particular, $M_{\lambda }$ is also positive semidefinite. Furthermore, $\mathbf{b}^{\top }Q_{\lambda }\mathbf{b}=({{\mathcal {T}}}_{\lambda }\mathbf{p})^{\top }Q_{\lambda }({{\mathcal {T}}}_{\lambda }{} \mathbf{p})=\mathbf{p}^{\top }M_{\lambda }{} \mathbf{p},$ where $\mathbf{b}=(b_1^{\lambda },\ldots ,b_{m_{\lambda }}^{\lambda })$ and $\mathbf{p}=(p_1^{\lambda },\ldots ,p_{\ell _{\lambda }}^{\lambda })$. That is, $g=\sum _{\lambda \in \varLambda _{\ell }}\langle Q_{\lambda },Y^{\lambda }\rangle =\sum _{\lambda \in \varLambda _{\ell }}\langle M_{\lambda },Z^{\lambda }\rangle$. $\square$

Appendix B: SoS Lower Bound for the Assignment Linear Program

We now show that the lower bound of Theorem 1 translates to the assignment linear program. Recall that the r-th level of the SoS hierarchy corresponds to a semidefinite program with variables $y_S$ for any subset $S\subseteq E$ with $|S|\le r$. The inequalities defining this program can be obtained by considering properties (SoS.1)–(SoS.4) in the definition of degree-r SoS pseudoexpectations and identifying $\widetilde{{\mathbb {E}}}(x_S)=y_S$; see for example [40] for details. For any polytope $P\subseteq [0,1]^E$, we denote by $\text {SoS}{}_r(P)$ the projection of the r-th level of the SoS hierarchy over $y_i=y_{\{i\}}$ for each $i\in E$. Au and Tunçel [4, Proposition 1] showed that for any polytope $P\subseteq [0,1]^E$, if $L:{\mathbb {R}}^E\rightarrow {\mathbb {R}}^E$ is an affine transformation such that $L(x)\in [0,1]^E$ for all elements in the unit hypercube $x\in [0,1]^E$, then $\text {SoS}{}_r(L(P))= L(\text {SoS}{}_r(P))$. In our case, we consider the configuration linear program and the assignment linear program within the same space. Let T be a target makespan and consider

$$\begin{aligned} P = {\mathbb {R}}^{[m]\times J}\times \text {clp}{}(T)= \{(x,y)\in {\mathbb {R}}^{[m] \times J}\times {\mathbb {R}}^{[m]\times {{\mathcal {C}}}}: y \in \text {clp}{}(T)\}. \end{aligned}$$

We define the projection $L(x,y)=(x',0)$ where $x'$ is defined as

$$\begin{aligned} x'_{ij} = \frac{1}{n_{p_j}}\sum _{C\in {{\mathcal {C}}}} m(C,p_j) \cdot y_{iC} \quad \text {for all } i\in [m]\text { and for all }j\in J. \end{aligned}$$

Notice that $x'$ belongs to the assignment linear program, and hence $L(P)\subseteq \text {assign}(T)\times [0,1]^{[m]\times {{\mathcal {C}}}}$ is within the unit hypercube and the result by Au and Tunçel can be applied. Therefore,

$$\begin{aligned} L(\text {SoS}{}_{r+1}(P))= \text {SoS}{}_{r+1}(L(P))\subseteq \text {SoS}{}_r(\text {assign}(T)\times [0,1]^{[m]\times {{\mathcal {C}}}}), \end{aligned}$$

where the last inclusion follows since $L(P)\subseteq \text {assign}(T)\times [0,1]^{[m]\times {{\mathcal {C}}}}$ and the general property of the next lemma. We remark that this is enough to get an integrality gap of 1.0009 for $\varOmega (n)$ rounds of the SoS hierarchy applied to the assignment linear program.

Lemma 19

If P and Q are two polytopes with $P\subseteq Q$, then $\text {SoS}_{r+1}{}(P)\subseteq \text {SoS}_r{}(Q)$.

Proof

Let us assume that $P =\{x\in {\mathbb {R}}^n:Ax\le b\}$ and $Q=\{x\in {\mathbb {R}}^n:Cx\le d\}$ for some $A\in {\mathbb {R}}^{m\times n},b\in {\mathbb {R}}^m$, $C\in {\mathbb {R}}^{p\times n}$ and $d\in {\mathbb {R}}^{p}$. Let $a_i^{\top }$ be the i-th row of A and $c_i^{\top }$ the i-th row of C. We will show that a degree-$(r+1)$ SoS pseudoexpectation for P is also a degree-r SoS pseudoexpectation for Q. Indeed, recall that if $P\subseteq Q$, then every inequality $c_i^{\top } x\le d_i$, where $c_i$ is the i-th row of C, is a valid inequality for P. Hence, by Farkas lemma, for each row $i\in [p]$ there exists a non-negative vector $\gamma \in {\mathbb {R}}^m$ such that $c_i=\gamma ^{\top } A$ and $\gamma ^{\top } b \le d_i$. Let $\widetilde{{\mathbb {E}}}$ be a degree-$(r+1)$ SoS pseudoexpectation for P. We need to show that property (SoS.3) is satisfied for every inequality $(d_i-c_i^{\top }x)\ge 0$, with $i\in [p]$. Let $f\in {\mathbb {R}}[x]/{{\mathbf{I}}}_n$ with $\deg \left( \overline{f^2(d_i-c_i^{\top }x)}\right) \le r$. By basic algebraic manipulation it holds that

$$\begin{aligned} \widetilde{{\mathbb {E}}}(f^2(d_i-c_i^{\top }x)) = (d_i - \gamma ^{\top }b)\widetilde{{\mathbb {E}}}(f^2) +\sum _{j=1}^m\gamma _j \widetilde{{\mathbb {E}}}(f^2(b_j-a_j^{\top }x)) \ge 0, \end{aligned}$$

where the last inequality follows from the construction of $\gamma$, the fact that for each $j\in [m]$ we have $\deg \left( \overline{f^2(b_j-a_j^{\top }x)}\right) \le r+1$, and hence $\widetilde{{\mathbb {E}}}(f^2(b_j-a_j^{\top }x))\ge 0$ and $\widetilde{{\mathbb {E}}}(f^2)\ge 0$. $\square$