On mixing inequalities: rank, closure and cutting plane proofs

Sanjeeb Dash (sanjeebdus.ibm.com)
Oktay Gunluk (gunlukus.ibm.com)

Abstract: We study the mixing inequalities which were introduced by Gunluk and Pochet (2001). We show that a mixing inequality which mixes n MIR inequalities has MIR rank at most n if it is a type I mixing inequality and at most n-1 if it is a type II mixing inequality. We also show that these bounds are tight for n=2. We define mixing inequalities for a general mixed-integer set and show that the elementary mixing closure can be described using a bounded number of mixing inequalities, each of which has a bounded number of terms. This implies that the elementary mixing closure is a polyhedron. Finally, we show that any mixing inequality can be derived via a polynomial length MIR cutting plane proof. Combined with results of Dash (2006) and Pudlak (1997), this implies that there are valid inequalities for a certain mixed-integer set that cannot be obtained via a polynomial-size mixing cutting-plane proof.

Keywords: integer programming, mixing, closure, rank, cutting plane proof

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

Citation:

Download: [Postscript][PDF]

Entry Submitted: 09/08/2008
Entry Accepted: 09/08/2008
Entry Last Modified: 09/18/2008

Modify/Update this entry