Mixed n-step MIR inequalities: Facets for the

abstract

• 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 {y( 1,⋯, y m,v)∈ ℤ m × ℝ + :α 1 y i + 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 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 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,⋯,y m,v) ∈(ℤ× ℤ n-1+) m × ℝ +: ∑ nj=1 α j y ij + v < β i, i = 1,⋯, m}. The mixed MIR inequalities are simply the special case of n=1. We also show that mixed n-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 n-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 n-step MIR inequalities. © 2012 Elsevier B.V. All rights reserved.

authors

• Kianfar, Kiavash

published proceedings

• Discrete Optimization

author list (cited authors)

• Sanjeevi, S., & Kianfar, K.

citation count

• 12

complete list of authors

• Sanjeevi, Sujeevraja||Kianfar, Kiavash

publication date

• November 2012

publisher

• Elsevier BV  Publisher

published in

• Discrete Optimization  Journal

keywords

• Cutting Planes
• Mixed Integer Programming
• Mixed N-step Mir
• Mixing
• Multi-module Capacitated Facility Location
• Multi-module Capacitated Lot-sizing

Digital Object Identifier (DOI)

• 10.1016/j.disopt.2012.07.003

start page

• 216

end page

• 235

volume

• 9

issue

• 4

user-defined tag

• 10 Reduced Inequalities