  


A (k+1)Slope Theorem for the kDimensional Infinite Group Relaxation
Amitabh Basu(abasumath.ucdavis.edu) Abstract: We prove that any minimal valid function for the kdimensional infinite group relaxation that is piecewise linear with at most k+1 slopes and does not factor through a linear map with nontrivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k=1, and Cornu\'ejols and Molinaro for k=2. Keywords: integer programming, infinite group relaxation, minimal valid functions, facets Category 1: Integer Programming (Cutting Plane Approaches ) Category 2: Infinite Dimensional Optimization (Semiinfinite Programming ) Citation: Download: [PDF] Entry Submitted: 09/19/2011 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  