Generalized mixed integer rounding inequalities: facets for infinite group polyhedra Academic Article uri icon

abstract

  • We present a generalization of the mixed integer rounding (MIR) approach for generating valid inequalities for (mixed) integer programming (MIP) problems. For any positive integer n, we develop n facets for a certain (n + 1)-dimensional single-constraint polyhedron in a sequential manner. We then show that for any n, the last of these facets (which we call the n-step MIR facet) can be used to generate a family of valid inequalities for the feasible set of a general (mixed) IP constraint, which we refer to as the n-step MIR inequalities. The Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and günlük (Math Program 105(1):29-53, 2006) are the first two families corresponding to n = 1,2, respectively. The n-step MIR inequalities are easily produced using periodic functions which we refer to as the n-step MIR functions. None of these functions dominates the other on its whole period. Finally, we prove that the n-step MIR inequalities generate two-slope facets for the infinite group polyhedra, and hence are potentially strong. © 2008 Springer-Verlag.

published proceedings

  • Mathematical Programming

author list (cited authors)

  • Kianfar, K., & Fathi, Y.

citation count

  • 22

complete list of authors

  • Kianfar, Kiavash||Fathi, Yahya

publication date

  • September 2009