Breaking symmetries to rescue sum of squares: the case of makespan scheduling. (English) Zbl 1436.90080
Lodi, Andrea (ed.) et al., Integer programming and combinatorial optimization. 20th international conference, IPCO 2019, Ann Arbor, MI, USA, May 22–24, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11480, 427-441 (2019).
Summary: The sum of squares (SoS) hierarchy gives an automatized technique to create a family of increasingly tighter convex relaxations for binary programs. There are several problems for which a constant number of rounds give integrality gaps matching the best known approximation algorithm. In many other, however, ad-hoc techniques give significantly better approximation factors. The lower bounds instances, in many cases, are invariant under the action of a large permutation group. The main purpose of this paper is to study how the presence of symmetries on a formulation degrades the performance of the relaxation obtained by the SoS hierarchy. We do so for the special case of the minimum makespan problem on identical machines. Our first result is to show that a linear number of rounds of SoS applied over the configuration linear program yields an integrality gap of at least 1.0009. This improves on the recent work by A. Kurpisz et al. [Math. Program. 172, No. 1–2 (B), 231–248 (2018; Zbl 1402.90055)] that shows an analogous result for the weaker \(LS_+\) and SA hierarchies. 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 the SoS hierarchy for \(O_\varepsilon(1)\) rounds to this linear program reduces the integrality gap to \((1+\varepsilon)\). Our results suggest that the presence of symmetries were the main barrier preventing the SoS hierarchy to give tight relaxations.
For the entire collection see [Zbl 1418.90011].
For the entire collection see [Zbl 1418.90011].
Citations:
Zbl 1402.90055References:
| [1] | Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling. In: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp. 493-500, ACM-SIAM (1997) · Zbl 1321.90051 |
| [2] | Alon, N.; Azar, Y.; Woeginger, GJ; Yadid, T., Approximation schemes for scheduling on parallel machines, J. Sched., 1, 1, 55-66, 1998 · Zbl 0909.90168 · doi:10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J |
| [3] | Barak, B., Chan, S.O., Kothari, P.K.: Sum of squares lower bounds from pair wise independence. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2015, pp. 97-106. ACM (2015) · Zbl 1321.68295 |
| [4] | Barak, B., Hopkins, S.B., Kelner, J., Kothari, P., Moitra, A., Potechin, A.: A nearly tight sum-of-squares lower bound for the planted clique problem. In: Proceedings of Foundations of Computer Science, FOCS 2016, pp. 428-437. IEEE (2016) |
| [5] | Barak, B., Moitra, A.: Noisy tensor completion via the sum-of-squares hierarchy. In: Proceedings of the 29th Conference on Learning Theory, COLT 2016, pp. 417-445 (2016) |
| [6] | Blekherman, G.; Gouveia, J.; Pfeiffer, J., Sums of squares on the hypercube, Mathematische Zeitschrift, 284, 1-2, 41-54, 2016 · Zbl 1375.14187 · doi:10.1007/s00209-016-1644-7 |
| [7] | Eisenbrand, Friedrich; Weismantel, Robert, Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 808-816, 2018, Philadelphia, PA: Society for Industrial and Applied Mathematics, Philadelphia, PA · Zbl 1410.90128 · doi:10.1137/1.9781611975031.52 |
| [8] | Garg, S.: Quasi-PTAS for scheduling with precedences using LP hierarchies. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, pp. 59:1-59:13 (2018) · Zbl 1499.68404 |
| [9] | Gatermann, K.; Parrilo, PA, Symmetry groups, semidefinite programs, and sums of squares, J. Pure Appl. Algebra, 192, 1-3, 95-128, 2004 · Zbl 1108.13021 · doi:10.1016/j.jpaa.2003.12.011 |
| [10] | Goemans, M., Rothvoß, T.: Polynomiality for bin packing with a constant number of item types. In: Proceedings of the Twenty-Fifth annual ACM-SIAM Symposium on Discrete Algorithms, pp. 830-839. SIAM (2014) · Zbl 1421.68080 |
| [11] | Goemans, M.; Williamson, D., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 1115-1145, 1995 · Zbl 0885.68088 · doi:10.1145/227683.227684 |
| [12] | Graham, RL, Bounds for certain multiprocessing anomalies, Bell Syst. Tech. J., 45, 9, 1563-1581, 1966 · Zbl 0168.40703 · doi:10.1002/j.1538-7305.1966.tb01709.x |
| [13] | Grigoriev, D., Complexity of positivstellensatz proofs for the knapsack, Comput. Complex., 10, 2, 139-154, 2001 · Zbl 0992.68077 · doi:10.1007/s00037-001-8192-0 |
| [14] | Grigoriev, D., Linear lower bound on degrees of positivstellensatz calculus proofs for the parity, Theoret. Comput. Sci., 259, 1-2, 613-622, 2001 · Zbl 0974.68192 · doi:10.1016/S0304-3975(00)00157-2 |
| [15] | Hochbaum, D., Approximation Algorithms for NP-Hard Problems, 1996, Boston: PWS Publishing Co., Boston · Zbl 1368.68010 |
| [16] | Hochbaum, D.; Shmoys, D., Using dual approximation algorithms for scheduling problems theoretical and practical results, J. ACM, 34, 144-162, 1987 · doi:10.1145/7531.7535 |
| [17] | Hopkins, S.B., Kothari, P.K., Potechin, A., Raghavendra, P., Schramm, T., Steurer, D.: The power of sum-of-squares for detecting hidden structures. In: Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pp. 720-731. IEEE (2017) |
| [18] | Jans, R., Solving lot-sizing problems on parallel identical machines using symmetry-breaking constraints, INFORMS J. Comput., 21, 1, 123-136, 2009 · Zbl 1243.90147 · doi:10.1287/ijoc.1080.0283 |
| [19] | Jansen, K., An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables, SIAM J. Discrete Math., 24, 2, 457-485, 2010 · Zbl 1253.90111 · doi:10.1137/090749451 |
| [20] | Jansen, K., Klein, K., Verschae, J.: Closing the gap for makespan scheduling via sparsification techniques. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, pp. 72:1-72:13 (2016) · Zbl 1388.68123 |
| [21] | Kaibel, V.; Peinhardt, M.; Pfetsch, ME, Orbitopal fixing, Discrete Optim., 8, 595-610, 2011 · Zbl 1235.90091 · doi:10.1016/j.disopt.2011.07.001 |
| [22] | Kaibel, V.; Pfetsch, M., Packing and partitioning orbitopes, Math. Program., 114, 1, 1-36, 2008 · Zbl 1171.90004 · doi:10.1007/s10107-006-0081-5 |
| [23] | Karlin, AR; Mathieu, C.; Nguyen, CT; Günlük, O.; Woeginger, GJ, Integrality gaps of linear and semi-definite programming relaxations for knapsack, Integer Programming and Combinatoral Optimization, 301-314, 2011, Heidelberg: Springer, Heidelberg · Zbl 1341.90112 · doi:10.1007/978-3-642-20807-2_24 |
| [24] | Kothari, P., O’Donnell, R., Schramm, T.: SOS lower bounds with hard constraints: think global, act local. arXiv preprint arXiv:1809.01207 (2018) |
| [25] | Kothari, P.K., Mori, R., O’Donnell, R., Witmer, D.: Sum of squares lower bounds for refuting any CSP. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 132-145. ACM (2017) · Zbl 1370.68134 |
| [26] | Kothari, P.K., Steinhardt, J., Steurer, D.: Robust moment estimation and improved clustering via sum of squares. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 1035-1046. ACM (2018) · Zbl 1434.62125 |
| [27] | Kurpisz, A.; Leppänen, S.; Mastrolilli, M., On the hardest problem formulations for the 0/1 Lasserre hierarchy, Math. Oper. Res., 42, 1, 135-143, 2016 · Zbl 1359.90088 · doi:10.1287/moor.2016.0797 |
| [28] | Kurpisz, A.; Leppänen, S.; Mastrolilli, M.; Louveaux, Q.; Skutella, M., Sum-of-squares hierarchy lower bounds for symmetric formulations, Integer Programming and Combinatorial Optimization, 362-374, 2016, Cham: Springer, Cham · Zbl 1419.90070 · doi:10.1007/978-3-319-33461-5_30 |
| [29] | Kurpisz, A.; Leppänen, S.; Mastrolilli, M., An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem, Math. Program., 166, 1-2, 1-17, 2017 · Zbl 1386.90077 · doi:10.1007/s10107-016-1102-7 |
| [30] | Kurpisz, A.; Mastrolilli, M.; Mathieu, C.; Mömke, T.; Verdugo, V.; Wiese, A., Semidefinite and linear programming integrality gaps for scheduling identical machines, Math. Program., 172, 1-2, 231-248, 2018 · Zbl 1402.90055 · doi:10.1007/s10107-017-1152-5 |
| [31] | Laurent, M., Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope, Math. Oper. Res., 28, 4, 871-883, 2003 · Zbl 1082.90085 · doi:10.1287/moor.28.4.871.20508 |
| [32] | Laurent, M., Semidefinite representations for finite varieties, Math. Program., 109, 1, 1-26, 2007 · Zbl 1152.90007 · doi:10.1007/s10107-004-0561-4 |
| [33] | Laurent, M.; Putinar, M.; Sullivant, S., Sums of squares, moment matrices and optimization over polynomials, Emerging Applications of Algebraic Geometry, 157-270, 2009, New York: Springer, New York · Zbl 1163.13021 · doi:10.1007/978-0-387-09686-5_7 |
| [34] | Levey, E., Rothvoss, T.: A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. In:Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pp. 168-177. ACM (2016) · Zbl 1373.68454 |
| [35] | Liberti, L.; Yang, B.; Du, D-Z; Wang, CA, Automatic generation of symmetry-breaking constraints, Combinatorial Optimization and Applications, 328-338, 2008, Heidelberg: Springer, Heidelberg · Zbl 1168.90566 · doi:10.1007/978-3-540-85097-7_31 |
| [36] | Liberti, L.; Lee, J.; Leyffer, S., Symmetry in mathematical programming, Mixed Integer Nonlinear Programming, 263-283, 2012, New York: Springer, New York · Zbl 1242.90236 · doi:10.1007/978-1-4614-1927-3_9 |
| [37] | Ma, T., Shi, J., Steurer, D.: Polynomial-time tensor decompositions with sum-of squares. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pp. 438-446. IEEE (2016) |
| [38] | Margot, F., Pruning by isomorphism in branch-and-cut, Math. Program., 94, 71-90, 2002 · Zbl 1023.90088 · doi:10.1007/s10107-002-0358-2 |
| [39] | Margot, F.; Jünger, M., Symmetry in integer linear programming, 50 Years of Integer Programming 1958-2008, 647-686, 2010, Heidelberg: Springer, Heidelberg · Zbl 1187.90200 · doi:10.1007/978-3-540-68279-0_17 |
| [40] | O’Donnell, R.: SOS is not obviously automatizable, even approximately. In: Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), vol. 67, pp. 59:1-59:10. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017) · Zbl 1402.90116 |
| [41] | Ostrowski, J., Using symmetry to optimize over the Sherali-Adams relaxation, Math. Program. Comput., 6, 405-428, 2014 · Zbl 1302.90134 · doi:10.1007/s12532-014-0072-0 |
| [42] | Ostrowski, J.; Linderoth, J.; Rossi, F.; Smriglio, S., Orbital branching, Math. Program., 126, 147-178, 2011 · Zbl 1206.90101 · doi:10.1007/s10107-009-0273-x |
| [43] | Parrilo, P., Semidefinite programming relaxations for semialgebraic problems, Math. program., 96, 293-320, 2003 · Zbl 1043.14018 · doi:10.1007/s10107-003-0387-5 |
| [44] | Potechin, A.: Sum of squares lower bounds from symmetry and a good story. arXiv preprint arXiv:1711.11469 (2017) |
| [45] | Potechin, A., Steurer, D.: Exact tensor completion with sum-of-squares. arXiv preprint arXiv:1702.06237 (2017) |
| [46] | Raghavendra, P., Schramm, T., Steurer, D.: High-dimensional estimation via sum-of-squares proofs. arXiv preprint arXiv:1807.11419 (2018) |
| [47] | Raymond, A.; Saunderson, J.; Singh, M.; Thomas, RR, Symmetric sums of squares over k-subset hypercubes, Math. Program., 167, 2, 315-354, 2018 · Zbl 1383.05306 · doi:10.1007/s10107-017-1127-6 |
| [48] | Razborov, AA, Flag algebras, J. Symbol. Logic, 72, 4, 1239-1282, 2007 · Zbl 1146.03013 · doi:10.2178/jsl/1203350785 |
| [49] | Razborov, AA, On 3-hypergraphs with forbidden 4-vertex configurations, SIAM J. Discrete Math., 24, 3, 946-963, 2010 · Zbl 1223.05204 · doi:10.1137/090747476 |
| [50] | Rothvoß, T.: The Lasserre hierarchy in approximation algorithms. Lecture notes for MAPSP (2013) |
| [51] | Sagan, BE, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, 2001, New York: Springer, New York · Zbl 0964.05070 · doi:10.1007/978-1-4757-6804-6 |
| [52] | Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-CSPs. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pp. 593-602. IEEE (2008) |
| [53] | Svensson, O., Santa claus schedules jobs on unrelated machines, SIAM J. Comput., 41, 5, 1318-1341, 2012 · Zbl 1257.68083 · doi:10.1137/110851201 |
| [54] | Verdugo, V., Verschae, J.: Breaking symmetries to rescue sum of squares: the case of makespan scheduling. arXiv preprint arXiv:abs/1811.08539 (2018) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
