Abstract: We prove that any minimal valid function for the k-dimensional infinite group relaxation that is piecewise linear with at most k+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k=1, and Cornuejols and Molinaro for k=2.
Introduction: The Search for Extreme Functions
Integer Programming (IP) is a fundamental tool in operations research, essential for solving complex discrete optimization problems ranging from logistics to telecommunications. Because IPs are generally NP-hard, solvers rely on "cuts"—valid inequalities that prune the search space. The Gomory–Johnson infinite group relaxation provides a theoretical framework for studying these cuts.
In this model, we seek extreme functions. An extreme function represents a cut that is non-redundant; it cannot be expressed as a combination of other valid inequalities. Identifying these functions is crucial for developing the most powerful cutting planes. For decades, a central question has been: how many "slopes" (gradients) can a piecewise linear function have while remaining guaranteed to be extreme?
The (k+1)-Slope Theorem
The primary contribution of this paper is the proof of the $(k+1)$-slope theorem for any dimension $k$. This result unifies and extends decades of research. In one dimension ($k=1$), it was long known that 2-slope functions are extreme. Recent work established that in two dimensions ($k=2$), 3-slope functions are extreme. This paper proves the general case: a piecewise linear function with at most $k+1$ slopes is extreme, provided it satisfies a "genuineness" condition.
The "genuinely $k$-dimensional" requirement ensures the function is not merely a lower-dimensional function embedded in a higher-dimensional space. Specifically, the function must not factor through a linear map with a non-trivial kernel. As shown in Figure 1(b), a function that is constant along one axis effectively reduces to a lower-dimensional problem and may not satisfy the extremality conditions of the $k$-dimensional space.
Methodological Innovation: Topology in Optimization
Proving extremality in high dimensions requires more than standard polyhedral combinatorics. The authors employ a novel combination of linear algebra and combinatorial topology:
- Linear Algebra of Gradients: The proof constructs a system of linear equations based on the gradients of the function's pieces. To prove extremality, one must show this system has a unique solution.
- The KKM Lemma: In high dimensions, the way different "cells" of a piecewise linear function meet becomes incredibly complex. The authors utilize the Knaster–Kuratowski–Mazurkiewicz (KKM) Lemma, a deep result from topology related to fixed-point theorems, to ensure that the geometric arrangement of these cells allows for a unique solution to the gradient equations.
This application of topological tools to the geometry of optimization cuts represents a significant methodological leap, providing a rigorous way to handle the "boundary conditions" where different slopes meet in $k$-dimensional space.
Significance and Future Work
This theorem settles an open question posed by Gomory and Johnson in 2003 and provides a clear target for researchers: functions with exactly $k+1$ slopes are the "perfect" building blocks for high-dimensional cuts.
However, several challenges remain. The theorem proves that $k+1$ slopes are sufficient for extremality, but it does not establish necessity. There may exist extreme functions with significantly more slopes that require different proof techniques. Furthermore, while this theory identifies the "best" functions, translating these mathematical objects into efficient algorithms for commercial solvers remains an active area of research. Future work will likely focus on the algorithmic generation of these $(k+1)$-slope functions to improve the practical performance of integer programming solvers.
Summary updated