Oktay Günlük, Tracy Kimbrel, et al.
Transportation Science
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.
Oktay Günlük, Tracy Kimbrel, et al.
Transportation Science
Sanjeeb Dash, Santanu S. Dey, et al.
Mathematical Programming
Dennis Wei, Sanjeeb Dash, et al.
ICML 2019
Rui Chen, Sanjeeb Dash, et al.
ICML 2021