Generalized mixed integer rounding inequalities: facets for infinite group polyhedra
Academic Article
-
- Overview
-
- Research
-
- Identity
-
- Additional Document Info
-
- Other
-
- View All
-
Overview
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
author list (cited authors)
citation count
complete list of authors
-
Kianfar, Kiavash||Fathi, Yahya
publication date
publisher
published in
Research
keywords
-
Facet
-
Infinite Group Polyhedron
-
Mixed Integer Programming
-
Mixed Integer Rounding
-
Valid Inequality
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue
Other