All Cyclic Group Facets Inject

MaRDI QIDQ6304651zbMATH OpenFDO

Authors Matthias Köppe, Yuan Zhou

Publication date 24 July 2018

Mathematics Subject Classification ID

Integer programming (90C10)

Abstract: We give a variant of Basu-Hildebrand-Molinaro's approximation theorem for continuous minimal valid functions for Gomory-Johnson's infinite group problem by piecewise linear two-slope extreme functions [Minimal cut-generating functions are nearly extreme, IPCO 2016]. Our theorem is for piecewise linear minimal valid functions that have only rational breakpoints (in $1/q,mathbbZ$ for some $qinmathbbN$) and that take rational values at the breakpoints. In contrast to Basu et al.'s construction, our construction preserves all function values on $1/q,mathbbZ$. As a corollary, we obtain that every extreme function for the finite group problem on $1/q,mathbbZ$ is the restriction of a continuous piecewise linear two-slope extreme function for the infinite group problem with breakpoints on a refinement $1/(Mq),mathbbZ$ for some $MinmathbbN$. In combination with Gomory's master theorem [Some Polyhedra related to Combinatorial Problems, Lin. Alg. Appl. 2 (1969), 451-558], this shows that the infinite group problem is the correct master problem for facets (extreme functions) of 1-row group relaxations.

This page was built for publication: All Cyclic Group Facets Inject

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6304651)