Optimization Online


On mixing inequalities: rank, closure and cutting plane proofs

Sanjeeb Dash (sanjeebd***at***us.ibm.com)
Oktay Gunluk (gunluk***at***us.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 )


Download: [PDF]

Entry Submitted: 09/08/2008
Entry Accepted: 09/08/2008
Entry Last Modified: 05/04/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society