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

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.