Faster Integer Programming

Many important practical computations, such as scheduling, combinatorial, and optimization problems, use techniques known as integer programming to find the best combination of many variables. In these problems, some or all of the variables are restricted to integer values, which requires exponentially greater resources to solve than if the variables could take any value.

Last year, Victor Reis, now at the Institute for Advanced Study in Princeton, NJ, and his Ph.D. advisor Thomas Rothvoss of the University of Washington, proved a new upper bound on the time required to solve for any integer program. They analyzed an algorithm described more than a decade ago in the influential Ph.D. thesis of Daniel Dadush, now in the Netherlands at CWI (the Center for Mathematics and Informatics) and Utrecht University. “In some sense the algorithm is his, but we have proven that it works,” Rothvoss said.

“The proof basically says that you can solve an integer linear program, in theory, almost as well as you can solve one where the integer variable is only zero or one,” he added. Such either/or problems include many important integer-programming challenges, such as the classic NP-hard (non-polynomial) traveling-salesperson problem. (In this case, each variable indicates whether or not a leg between a particular pair of cities is on the chosen route.) Even with only two choices per variable, the number of possibilities grows exponentially with the number of variables, “So you need something smarter than just trying them all out,” Rothvoss said.

For variables that can take any integer value, the new result is the first proven speed advance in decades. “I was super-duper excited and really surprised,” said Noah Stephens-Davidowitz of Cornell University, who published an important predecessor for the work. “I was so impressed by how they managed to find a proof of this incredibly deep, important result.”

“It is a very important theoretical advancement,” agreed Amitabh Basu of Johns Hopkins University. However, algorithms based on this strategy are too cumbersome for everyday use, he added. “From a practical perspective, none of these algorithms are actually implemented in practice.”

Instead, integer programming problems are analyzed with rules tuned to specific cases. “Most of them are heuristics,” Basu said, “so you cannot really prove anything very interesting about the algorithm.” Nevertheless, “In practice they are very efficient. They solve industrial-scale problems all the time,” sometimes with tens of thousands of variables, he said.

Integer [Linear] Programming

Algorithms for integer programming often take a first stab at a solution with linear programming, which is outwardly similar but allows the variables to vary continuously. Linear constraints, expressed as inequalities, restrict solutions to a convex subregion in what is often a very high-dimensional variable space. The highest or lowest value of a linear objective function occurs at one of the vertices of this convex region, and finding it is relatively fast, depending only polynomially on the dimension n (the number of variables).

In contrast, restricting the variables to integer values requires a time increasing exponentially with n, even if the constraints and objective function are linear (known as integer linear programming). “When you have continuous variables, you have access to all of your tools from calculus,” Basu said, such as following gradients. “Once you enforce that your variables cannot take an arbitrary value, all of this goes out of the window.”

Indeed, integer programs like the traveling salesman problem are in the class of problems for which there is no polynomial algorithm. “If you could solve integer programming as efficiently,” he said, “you would prove that P=NP. We don’t actually believe that you should be able to solve integer programming faster than exponential in the number of variables.”

Heuristic techniques for integer programming typically use problem-specific guidelines to divide the possible integer combinations into subsets and then estimate bounds on the possible outcomes to prune unpromising branches. This widely used “branch and bound” technique, defined in 1960 by Ailsa Land and Alison Doig, can be applied recursively to choose promising branches that lead to good solutions, although with no guarantee of how quickly they will be found.

Randomized, Recursive Algorithm

Reis and Rothvoss’s work also builds on decades of history about provable bounds for integer programs, beginning with 1983 work by Hendrik Lenstra. Unlike heuristics, the algorithms use an abstract procedure that works for any problem to sift through potential solutions.

The techniques focus on the region of variable space that satisfies all the constraints. The constraints are generally linear inequalities that require solutions to be on one side of a hyperplane, so this “feasible region” is a convex, high-dimensional polyhedron. It suffices to ask whether it contains any points that are part of the infinite, regular lattice of integer combinations. “We want to study how the lattice interplays with a convex set,” Reis said.

“From a mathematical perspective, it’s not really very different whether you [aim to] optimize a linear function or just find any feasible point.” Rothvoss said. If the volume contains multiple points, “you can use a binary search and then find the optimum” among them.

A key technique, introduced in the late 1980s by Ravi Kannan (with his frequent coauthor László Lovász) is to project both the lattice and the feasible region onto a space of lower dimension d, and check whether the projected region contains a projected lattice point. “I want reduce the problem to something lower-dimensional,” Reis said. The algorithm randomly chooses a target subspace that approximates the most effective projection. “You … can take the best direction on which to project.”

The projected region may include the projection of various lattice points. For each such point, Dadush’s algorithm reverses the projection to find the subset of the original convex set, with dimension n–d, projected onto that point. The process is applied recursively to see if that subset contains a lattice point. If not, it can be ignored. If it does, the dimension-reducing process is then applied to that subset, to definitively decide in a guaranteed time whether the original convex set contains a lattice point.

Covering Radius

Dadush’s algorithm “is basically the backbone of what we used,” Reis said. “We just had a better approximation to a quantity that’s known as the covering radius. He showed that, if he had such a better approximation, you would get a faster algorithm for integer programming.”

For a lattice completely decorated with n-dimensional balls, the covering radius is the minimum radius that guarantees that they cover all of variable space. For integer programming, the phrase extends to the minimum scaling factor for the constraint-satisfying feasible region to cover space when repeated around every lattice point. More relevant for the algorithm, this also means that no matter how the feasible region is translated around the space, it includes at least one lattice point.

In 2016, Stephens-Davidowitz and his then-Ph.D. co-advisor Oded Regev at New York University proved a conjecture by Dadush that was a key precursor for Reis and Rothvoss’s proof. “What Reis and Rothvoss did is they extended the result about the covering radius of balls to what are called convex bodies, a much, much larger class of bodies, like cubes and parallelograms and all sorts of things like that,” he said. “That’s what’s needed for integer programming.”

“We did think about extending it to arbitrary convex bodies, but we basically convinced ourselves quite quickly that that was really, really hard,” Stephens-Davidowitz said. “The amazing thing about this Rothvoss and Reis paper—I say this entirely with admiration—is it’s not that difficult in hindsight. The proof is quite clean.”

Previously, the proven minimum time to find a solution was roughly nⁿ. The new proof guarantees a much shorter (log n)^O(n), where O(n) means “of order n.” Since even log(n) is a big number for large n, this is somewhat greater than the 2ⁿ bound for the zero/one versions but has the same simple exponential dependence. “Getting it down to 2ⁿ would be amazing, because that would really complete the story, theoretically speaking,” Basu said. But getting to (log n)ⁿ is a big, big deal from the theoretical perspective.”

Practical Challenges

Still, “It’s more like a theoretical understanding of this entire set of problems than something that you actually might want to use for any particular one,” Ries conceded. In most practical cases, “There’s a particular kind of integer program people want to solve. For most of these cases there are ad hoc heuristics that work much better in practice than our worst-case algorithm,” which works for any problem.

“If we want to actually implement this, there are several hurdles we need to overcome,” Ries cautioned. One is that the memory requirements are exponential, whereas practical approaches like heuristics “actually run in polynomial space. We don’t know if that’s possible” for the general-purpose algorithm. In addition, “There are several other subroutines in our algorithm that we still don’t have efficient algorithms for in practice.”

Still, although the performance of heuristics is not proved, “On any practical problem that you come across, they’re actually very good,” Rothvoss agreed. “Could our algorithm be better for certain instances? If you have some particularly nasty instances where the range of the variables is extremely large, or the feasible region is extremely thin in certain directions, maybe.”

Further Reading

• Reis, V. and Rothvoss, T. The Subspace Flatness Conjecture and Faster Integer Programming, https://doi.org/10.48550/arXiv.2303.14605 (2023)
• Regev, O. and Stephens-Davidowitz, N. A Reverse Minkowski Theorem, Annals of Mathematics (2024)
• Dadush, D.N. Integer programming, lattice algorithms, and deterministic volume estimation, Ph.D. Thesis, Georgia Tech (2012)
• Chandrasekaran, L. Researchers Approach New Speed Limit for Seminal Problem, Quanta (2024)