TY - JOUR
T1 - Breaking symmetries to rescue sum of squares in the case of makespan scheduling
AU - Verdugo, Victor
AU - Verschae, José
AU - Wiese, Andreas
N1 - Publisher Copyright:
© 2020, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.
PY - 2020/9/1
Y1 - 2020/9/1
N2 - 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 Ω(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 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 2O~(1/ε2) rounds of the SA hierarchy to this stronger linear program reduces the integrality gap to 1 + ε, 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 SoS / SA hierarchies to give relaxations of polynomial complexity with an integrality gap of 1 + ε. We leave as an open question whether this phenomenon occurs for other symmetric problems.
AB - 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 Ω(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 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 2O~(1/ε2) rounds of the SA hierarchy to this stronger linear program reduces the integrality gap to 1 + ε, 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 SoS / SA hierarchies to give relaxations of polynomial complexity with an integrality gap of 1 + ε. We leave as an open question whether this phenomenon occurs for other symmetric problems.
KW - Approximation algorithms
KW - Makespan scheduling
KW - Polynomial optimization
KW - Symmetry breaking
UR - http://www.scopus.com/inward/record.url?scp=85085020467&partnerID=8YFLogxK
U2 - 10.1007/s10107-020-01511-3
DO - 10.1007/s10107-020-01511-3
M3 - Article
AN - SCOPUS:85085020467
SN - 0025-5610
VL - 183
SP - 583
EP - 618
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1-2
ER -