Mixed nn-step MIR inequalities: Facets for the nn-mixing set

Günlük and Pochet [O. Günlük, 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 {(y1,…,ym,v)∈Zm×R+:α1yi+v≥βi,i=1,…,m}{(y1,…,ym,v)∈Zm×R+:α1yi+v≥βi,i=1,…,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 nn-step MIR inequalities for the mixed integer knapsack set through a generalization of MIR. In this paper, we generalize the mixing procedure to the nn-step MIR inequalities and introduce the mixed nn-step MIR inequalities. We prove that these inequalities define facets for a generalization of the mixing set with nn integer variables in each row (which we refer to as the nn-mixing set), i.e. {(y1,…,ym,v)∈(Z×Z+n−1)m×R+:∑j=1nαjyji+v≥βi,i=1,…,m}. The mixed MIR inequalities are simply the special case of n=1n=1. We also show that mixed nn-step MIR can generate valid inequalities based on multiple constraints for general MIPs. Moreover, we introduce generalizations of the capacitated lot-sizing and facility location problems, which we refer to as the multi-module problems, and show that mixed nn-step MIR can be used to generate valid inequalities for these generalizations. Our computational results on small MIPLIB instances as well as a set of multi-module lot-sizing instances justify the effectiveness of the mixed nn-step MIR inequalities.