Some high-degree integrality gap results for the Sum of Squares hierarchy

You are cordially invited to attend the PhD Dissertation Defense of Samuli LEPPÄNEN on Wednesday, March 14th 2018 at 15h30 in room A34 (Red building)

Abstract:

The Sum of Squares (SoS)/Lasserre hierarchy can be seen as an automatizable procedure for producing convex relaxations of nonconvex integer programming problems. The hierarchy takes as input an integer linear programming formulation of a combinatorial optimization problem and outputs a semidefinite program that can be solved up to arbitrary accuracy. The tightness of the relaxation can be controlled by selecting an integer parameter called degree of the hierarchy, and larger degree corresponds to tighter relaxation but also increases running time by increasing the size of the associated semidefinite program. The SoS hierarchy connects to many topics in theoretical computer science and has found several applications, among others matching the approximation guarantees of the best known algorithms for several important problems.

In this thesis we study some limitations of the hierarchy in situations where the degree of the hierarchy is allowed to be large relative to the number of decision variables of the original integer programming problem. We give a brief introduction to the hierarchy and motivate its use in theoretical computer science.

The core of the thesis is devoted to presenting our work. It is known that when the degree of the hierarchy is high enough, it can solve any integer linear program exactly. We study what happens when the degree is just below this maximum degree and completely characterize the problems that are not exactly solved. Consequently, we show that the SoS relaxation of this degree of the Min Knapsack problem admits an unbounded integrality gap, and is in some sense the hardest problem for the hierarchy to solve.

Next, we study the SoS relaxations of a scheduling problem that is known to be solvable in polynomial time. We develop a method for analysing the matrices emerging from the application of the hierarchy to this problem, and show that the integrality gap of the SoS relaxation is unbounded even when the degree is proportional to the square root of the number of decision variables. This is one of the few known results where the hierarchy requires a large degree for solving a problem that is solvable in polynomial time, and to the best of our knowledge the only one with an unbounded integrality gap.

Finally, we consider the application of the SoS hierarchy in situations where the problem formulation is symmetric under permutations of the symmetric group. We are able to significantly simplify the feasibility conditions of the SoS hierarchy. As an application we obtain a simplified proof for the Knapsack lower bound originally presented by Grigoriev. We also generalize the proof and show a lower bound for polynomial optimization of arbitrary degree over the hypercube. As a further application we disprove a hypothesis by Laurent concerning the performance of the SoS hierarchy on a particular set of inequalities that has no solution. Finally, we revisit the Min Knapsack problem, this time strengthening the problem formulation with covering inequalities. We show that even with this formulation the SoS hierarchy relaxation requires a super constant degree to outperform the linear programming formulation.

Dissertation Committee:

• Prof. Monaldo Mastrolilli, Università della Svizzera italiana, Switzerland (Research Advisor)
• Prof. Luca Gambardella, Università della Svizzera italiana, Switzerland (Co-Advisor)
• Prof. Rolf Krause, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Stefan Wolf, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Samuel Fiorini, Université libre de Bruxelles, Belgium (External Member)
• Prof. Stanislav Zivný, University of Oxford, UK (External Member)