Facets of Two-Dimensional Infinite Group Problems

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 of 2DMIIGP. 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 blocks 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 the one–dimensional mixed integer infinite group problem (1DMIIGP).