  


On mixing inequalities: rank, closure and cutting plane proofs
Sanjeeb Dash (sanjeebdus.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 n1 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 mixedinteger 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 mixedinteger set that cannot be obtained via a polynomialsize mixing cuttingplane proof. Keywords: integer programming, mixing, closure, rank, cutting plane proof Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Download: [PDF] Entry Submitted: 09/08/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  