  


Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. III. Foundations for the kDimensional Case with Applications to k=2
Amitabh Basu(basu.amitabhjhu.edu) Abstract: We develop foundational tools for classifying the extreme valid functions for the kdimensional infinite group problem. In particular, (1) we present the general regular solution to Cauchy's additive functional equation on bounded convex domains. This provides a kdimensional generalization of the socalled interval lemma, allowing us to deduce affine properties of the function from certain additivity relations. (2) We study the discrete geometry of additivity domains of piecewise linear functions, providing a framework for finite tests of minimality and extremality. (3) We give a theory of nonextremality certificates in the form of perturbation functions. We apply these tools in the context of minimal valid functions for the twodimensional infinite group problem that are piecewise linear on a standard triangulation of the plane, under the assumption of a regularity condition called diagonal constrainedness. We show that the extremality of a minimal valid function is equivalent to the extremality of its restriction to a certain finite twodimensional group problem. This gives an algorithm for testing the extremality of a given minimal valid function. Keywords: Group relaxation, infinite group problem, extreme functions Category 1: Integer Programming (Cutting Plane Approaches ) Category 2: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Download: [PDF] Entry Submitted: 03/18/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  