PIMS-CORDS SFU Operations Research Seminar: Yuan Zhou

In this talk, we study cut-generating functions in the setting of the Gomory-Johnson group relaxations for integer programming. We address an open question: whether every facet (extreme function) for a finite cyclic group relaxation injects into the space of extreme functions for the infinite group problem. We give a variant of the Basu-Hildebrand-Molinaro approximation theorem [IPCO 2016] for continuous minimal functions of the infinite group problem. Specifically, we show that any piecewise linear minimal function with rational breakpoints in 1/qZ and rational values at these breakpoints can be approximated by piecewise linear two-slope extreme functions while preserving all function values on 1/qZ: a feature not guaranteed by the earlier construction. As a corollary, every extreme function for the finite group problem on 1/qZ is the restriction of a continuous piecewise linear two-slope extreme function for the infinite group problem, with breakpoints on a refinement 1/(Mq)Z. Combined with Gomory’s master theorem, this establishes that the infinite group problem indeed serves as the correct master problem for facets of one-row group relaxations.

This is a joint work with Matthias Koeppe.