Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem

We give an algorithm for testing the extremality of minimal valid functions for Gomory and Johnson's infinite group problem, that are piecewise linear (possibly discontinuous) with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically, for deciding extremality in this important class of minimal valid functions.



View Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem