New method solves large combinatorial programs with less memory
Solving Large SDPs from Flag Algebra Problems
Discrete Mathematics
Summary
Certain math problems involving large networks or groups of objects are hard to solve because they need too much computer memory. The authors found a way to solve bigger problems by using a step-by-step approach that requires less memory. This lets them get better answers for questions about complex structures like 3D networks and helps with problems previously out of reach. Their method improves bounds on specific patterns, like the tetrahedron shape, which was difficult to analyze before.
What this means in practice
- •For combinatorial optimization teams: Solve larger semidefinite programs related to combinatorial problems with reduced memory requirements.
- •For software engineers for mathematical software: Incorporate cutting-plane linear programming methods to handle previously unsolvable large-scale combinatorial optimization instances.
Authors
Bernard Lidický, Jan Volec
Abstract
The flag algebra method is a general tool in extremal combinatorics, which has been useful in tackling open problems concerning graphs, hypergraphs, permutations, point sets, and other structures. The method establishes combinatorial inequalities via sums of squares, which are usually obtained by a semidefinite relaxation of the original combinatorial problem. A typical application of the method in graph theory starts with fixing a parameter $n$ followed by constructing a semidefinite program based on the (subgraph) structure of all $n$-vertex graphs. In the standard formulation before symmetry reductions, there is a coefficient constraint for every admissible $n$-vertex graph up to isomorphism. For 3-uniform hypergraphs, there are 2,136 of them on 6 vertices and 7,013,320 on 7 vertices. While solving the resulting program for $n=6$ is an easy task on any modern computer, the programs for $n = 7$ seems out of reach, mainly because the SDP solvers need too much RAM. Yet solving such programs for as large $n$ as possible is desirable because they typically yield better bounds for the original combinatorial problems. We bypass the aforementioned memory requirements by linear programming with cutting planes. Although we do not guarantee that this cutting-plane procedure reaches an optimum in finitely many iterations, in many flag algebra instances it uses much less memory and yields improved bounds for well-known hypergraph Turán problems. We use this method to obtain numerical bounds for Turán densities and codegree squared densities of several 3-uniform hypergraphs including the tetrahedron, where we obtained the upper bound 0.55753 and tetrahedron without one edge with a new upper bound 0.2865. It also allows to tackle bounds on Turán densities of 7-vertex 3-graphs using flag algebras, which was not possible before.