  


Facets of TwoDimensional Infinite Group Problems
Santanu Dey (sdeypurdue.edu) Abstract: In this paper, we lay the foundation for the study of the twodimensional mixed integer infinite group problem (2DMIIGP). We introduce tools to determine if a given continuous and piecewise linear function over the twodimensional infinite group is subadditive and to determine whether it defines a facet. We then present two different constructions that yield the first known families of facetdefining inequalities for 2DMIIGP. The first construction uses valid inequalities of the one dimensional integer infinite group problem (1DIIGP) as building block for creating inequalities for the twodimensional integer infinite group problem (2DIIGP).We prove that this construction yields all continuous piecewise linear facets of the twodimensional group problem that have exactly two gradients. The second construction we present has three gradients and yields facetdefining inequalities of 2DMIIGP whose continuous coefficients are not dominated by those of facets of onedimensional mixed integer group problem (1DMIIGP). Keywords: Mixed Integer Programs; Multiple Constraints; Polyhedral Theory; Infinite Group Problem Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Integer Programming (Cutting Plane Approaches ) Citation: To appear in Mathematics of Operations Research Download: Entry Submitted: 01/06/2006 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  