On mixing inequalities: Rank, closure, and cutting-plane proofs

Abstract

We study the mixing inequalities that were intro duced by Günlük and Pochet [Math. Program., 90 (2001), pp. 429-457]. 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. Given a mixed-integer set PI = P ∩ Z(I), where P is a polyhedron and Z(I) = {x ∈ ℝn: xi ∈ ℤ ∀i ∈ I}, we define mixing inequalities for PI. We show that the elementary mixing closure of P with respect to I 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 of P 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 [On the complexity of cutting plane proofs using split cuts, IBM Research Report RC 24082, Oct. 2006] and Pudlak [J. Symbolic Logic, 62 (1997), pp. 981-998], 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. Copyright © 2009 Society for Industrial and Applied Mathematics.