We study the mixing inequalities which were introduced by Günlük 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.
Given a mixed-integer set PI = P ∩ Z(I) where P is a polyhedron and Z(I) = {x ∈ Rn : xi ∈ Z ∀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 (2006) and Pudlák (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.
By: Sanjeeb Dash; Oktay Günlük
Published in: RC24633 in 2008
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .