Sparktope: linear programs from algorithms

Abstract

In a recent paper, Avis, Bremner, Tiwary and Watanabe gave a method for constructing linear programs (LPs) based on algorithms written in a simple programming language called Sparks. If an algorithm produces the solution x to a problem in polynomial time and space then the LP constructed is also of polynomial size and its optimum solution contains x as well as a complete execution trace of the algorithm. Their method led us to the construction of a compiler called sparktope which we describe in this paper. This compiler allows one to generate polynomial sized LPs for problems in $\mathrm{P}$ that have exponential extension complexity, such as matching problems in non-bipartite graphs.

In this paper, we describe sparktope, the language Sparks, and the assembler instructions and LP constraints it produces. This is followed by two concrete examples, the makespan problem and the problem of testing if a matching in a graph is maximum, both of which are known to have exponential extension complexity. Computational results are given. In discussing these examples, we make use of visualization techniques included in sparktope that may be of independent interest. The extremely large linear programs produced by the compiler appear to be quite challenging to solve using currently available software. Since the optimum LP solutions can be computed independently they may be useful as benchmarks. Further enhancements of the compiler and its application are also discussed.

Keywords:

• Linear programming
• polytopes
• extension complexity
• makespan
• maximum matching

Acknowledgements

We would like to thank Bill Cook and Hans Tiwary for helpful discussions. In particular the former suggested we consider the Held–Karp algorithm and the latter the makespan problem. Two referees provided valuable comments which helped us improve the manuscript. This research is supported by the JSPS and NSERC.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 We learned [12] while the paper was under revision that with small changes the LP files can be read directly by Gurobi. Unfortunately this does not improve the results.

2 All runs on mai20: 2x Xeon E5-2690 (10-core 3.0GHz), 20 cores, 128GB memory, 3TB hard drive

3 All runs on mai32ef: 4x Opteron 6376 (16-core 2.3GHz), 64 cores, 256GB memory, 4TB hard drive

Additional information

Notes on contributors

David Avis

David Avis is a Professor Emeritus at the School of Computer Science of McGill University and a researcher at the Department of Communications and Computer Engineering of Kyoto University. He received his PhD in 1977 from Stanford University in Operations Research. His research interests include discrete optimization, polyhedral computation and parallel computation.

David Bremner

David Bremner received a PhD in in Computer Science from McGill University in 1997. David spent two years as an NSERC postdoctoral fellow in the Department of Mathematics at the University of Washington from 1997 to 1999. Since 2000 David has been a faculty member at the University of New Brunswick, and is currently a Professor of Computer Science with a Cross Appointment to the Department of Mathematics and Statistics. David's research interests include Mathematical Optimization, Computational Geometry, and Programming Languages.