Facets of Two-Dimensional Infinite Group Problems

Santanu Dey (sdeypurdue.edu)
Jean-Philippe Richard (jpricharecn.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

Download:

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

Modify/Update this entry