  


All Cyclic Group Facets Inject
Matthias Köppe (mkoeppemath.ucdavis.edu) 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 twoslope extreme functions [Minimal cutgenerating functions are nearly extreme, IPCO 2016]. Our theorem is for piecewise linear minimal valid functions that have only rational breakpoints (in 1/q Z for some q ∈ N) 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 Z. As a corollary, we obtain that every extreme function for the finite group problem on 1/q Z is the restriction of a continuous piecewise linear twoslope extreme function for the infinite group problem with breakpoints on a refinement 1/(M q) Z for some M ∈ N. 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 1row group relaxations. Keywords: Group relaxation Category 1: Integer Programming (Cutting Plane Approaches ) Citation: Download: [PDF] Entry Submitted: 07/26/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  