  


Light on the Infinite Group Relaxation
Amitabh Basu (basu.amitabhjhu.edu) Abstract: This is a survey on the infinite group problem, an infinitedimensional relaxation of integer linear optimization problems introduced by Ralph Gomory and Ellis Johnson in their groundbreaking papers titled "Some continuous functions related to corner polyhedra I, II" [Math. Programming 3 (1972), 2385, 359389]. The survey presents the infinite group problem in the modern context of cut generating functions. It focuses on the recent developments, such as algorithms for testing extremality and breakthroughs for the krow problem for general k >= 1 that extend previous work on the singlerow and tworow problems. The survey also includes some previously unpublished results; among other things, it unveils piecewise linear extreme functions with more than four different slopes. An interactive companion program, implemented in the opensource computer algebra package Sage, provides an updated compendium of known extreme functions. Keywords: cutting planes; cutgenerating functions; minimal and extreme functions; integer programming; infinite group problem Category 1: Integer Programming (Cutting Plane Approaches ) Category 2: Combinatorial Optimization (Branch and Cut Algorithms ) Category 3: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Download: [PDF] Entry Submitted: 10/30/2014 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  