Sanjeeb Dash, Oktay Günlük
Mathematical Programming
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.
Sanjeeb Dash, Oktay Günlük
Mathematical Programming
Sanjeeb Dash, Ricardo Fukasawa, et al.
Mathematical Programming
Rui Chen, Sanjeeb Dash, et al.
Discrete Optimization
Amir Ali Ahmadi, Oktay Günlük
CDC 2015