Optimization Online


Mixed n-Step MIR Inequalities: Facets for the n-Mixing Set

Sujeevraja Sanjeevi (sujeevraja***at***tamu.edu)
Kiavash Kianfar (kianfar***at***tamu.edu)

Abstract: Gunluk and Pochet [O. Gunluk, Y. Pochet: Mixing mixed integer inequalities. Mathematical Programming 90(2001) 429-457] 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) 313-346] introduced the n-step MIR inequalities for the mixed integer knapsack set through a generalization of MIR. In this paper, we generalize the mixing procedure to the n-step MIR inequalities and introduce the mixed n-step MIR inequalities. We prove that these inequalities define facets and high-dimensional faces for a generalization of the mixing set with n integer variables in each row (which we refer to as the n-mixing set), i.e. $ \{(y^1,\ldots,y^m,v) \in (Z \times Z_+^{n-1})^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 n-step MIR can generate multi-row valid inequalities for general MIP and can be used to generalize well-known inequalities for capacitated lot-sizing and facility location problems to the multi-capacity case.

Keywords: mixed n-step MIR, n-step MIR, mixing, mixed integer programming, cutting planes, multi-capacity lot-sizing, multi-capacity facility location

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )



Entry Submitted: 09/29/2011
Entry Accepted: 09/30/2011
Entry Last Modified: 06/30/2012

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 Optimization Society