Some Relations Between Facets of Low- and High-Dimensional Group Problems

Santanu Dey(sdeypurdue.edu)
Jean-Philippe Richard(jpricharecn.purdue.edu)

Abstract: In this paper, we introduce an operation that creates families of facet-defining inequalities for high-dimensional infinite group problems using facet-defining inequalities of lower-dimensional group problems. We call this family sequential-merge inequalities because they are produced by applying two group cuts one after the other and because the resultant inequality depends on the order of the operation. The sequential-merge inequalities can be used to generate inequalities whose continuous variables coefficients are stronger than those of the constituent low-dimensional cuts. We also show that they can be used to derive the three-gradient facet-defining inequality introduced by Dey and Richard. We then introduce a general scheme for generating valid inequalities for lower-dimensional group problems using valid inequalities of higher-dimensional group problems. We present conditions under which this construction generates facet-defining inequalities when applied to sequential-merge inequalities. We show that this procedure generates a subfamily of the two-step MIR inequalities of Dash and Gunluk.

Keywords: Mixed Integer Programming, Infinite Group Problem

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation:

Download: [PDF]

Entry Submitted: 05/31/2007
Entry Accepted: 05/31/2007
Entry Last Modified: 05/31/2007

Modify/Update this entry