  


Mixed nStep MIR Inequalities: Facets for the nMixing Set
Sujeevraja Sanjeevi (sujeevrajatamu.edu) Abstract: Gunluk and Pochet [O. Gunluk, Y. Pochet: Mixing mixed integer inequalities. Mathematical Programming 90(2001) 429457] proposed a procedure to mix mixed integer rounding (MIR) inequalities. The mixed MIR inequalities define the convex hull of the mixing set $\{(y^1,\ldots,y^m,v) \in Z^m \times R_+:\alpha_1 y^i + v \geq \b_i,i=1,\ldots,m\}$ and can also be used to generate valid inequalities for general as well as several special mixed integer programs (MIPs). In another direction, Kianfar and Fathi [K. Kianfar, Y. Fathi: Generalized mixed integer rounding inequalities: facets for infinite group polyhedra. Mathematical Programming 120(2009) 313346] introduced the nstep MIR inequalities for the mixed integer knapsack set through a generalization of MIR. In this paper, we generalize the mixing procedure to the nstep MIR inequalities and introduce the mixed nstep MIR inequalities. We prove that these inequalities define facets and highdimensional faces for a generalization of the mixing set with n integer variables in each row (which we refer to as the nmixing set), i.e. $ \{(y^1,\ldots,y^m,v) \in (Z \times Z_+^{n1})^m \times R_+ : \sum_{j=1}^n \alpha_j y_j^i + v \geq \b_i, i=1,\ldots,m\}$. The mixed MIR inequalities are simply the special case of n=1. We then show that mixed nstep MIR can generate multirow valid inequalities for general MIP and can be used to generalize wellknown inequalities for capacitated lotsizing and facility location problems to the multicapacity case. Keywords: mixed nstep MIR, nstep MIR, mixing, mixed integer programming, cutting planes, multicapacity lotsizing, multicapacity facility location Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Integer Programming (Cutting Plane Approaches ) Citation: Download: Entry Submitted: 09/29/2011 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  