Optimization Online


Facets of Two-Dimensional Infinite Group Problems

Santanu Dey (sdey***at***purdue.edu)
Jean-Philippe Richard (jprichar***at***ecn.purdue.edu)

Abstract: In this paper, we lay the foundation for the study of the two-dimensional mixed integer infinite group problem (2DMIIGP). We introduce tools to determine if a given continuous and piecewise linear function over the two-dimensional 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 facet-defining 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 two-dimensional integer infinite group problem (2DIIGP).We prove that this construction yields all continuous piecewise linear facets of the two-dimensional group problem that have exactly two gradients. The second construction we present has three gradients and yields facet-defining inequalities of 2DMIIGP whose continuous coefficients are not dominated by those of facets of one-dimensional 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


Entry Submitted: 01/06/2006
Entry Accepted: 01/06/2006
Entry Last Modified: 07/04/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society