The Gomory–Johnson Infinite Group Relaxation

Cutting planes, as a critical ingredient of branch-and-cut algorithms, are a very widely used technique for solving discrete optimization problems. The progress in understanding cutting planes, notably through the associated polyhedral combinatorics, has been the key for the dramatic increase in our ability to solve very hard optimization problems since the early 1980s.

A current research trend to find strong cutting planes is to consider certain infinite-dimensional relaxations of finite-dimensional optimization problems, which lead to so-called cut-generating functions, a term introduced by Cornuejols. The classical model in this context is the Gomory–Johnson infinite group problem, introduced by Ralph Gomory and Ellis Johnson in their seminal papers titled "Some continuous functions related to corner polyhedra I, II" [Math. Programming 3 (1972), 23–85, 359–389].

All integer linear programs with a fixed number k of rows and given right-hand side vector f are embedded into one infinite group problem in a function space. One then studies the convex geometry of this infinite-dimensional relaxation.

The goal of standard polyhedral combinatorics in the finite-dimensional case is to classify the facet-defining inequalities, which are the strongest inequalities among all tight valid inequalities. Likewise, in the infinite-dimensional case, we are interested in classifying all extreme functions, which are strongest among all minimal valid functions.

Video introduction



Research articles


Matthias Köppe