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 singleconstraint polyhedron in a sequential manner. We then show that for any n, the last of these facets (which we call the nstep 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 nstep MIR inequalities. The Gomory Mixed Integer Cut and the 2step MIR inequality of Dash and günlük (Math Program 105(1):2953, 2006) are the first two families corresponding to n = 1,2, respectively. The nstep MIR inequalities are easily produced using periodic functions which we refer to as the nstep MIR functions. None of these functions dominates the other on its whole period. Finally, we prove that the nstep MIR inequalities generate twoslope facets for the infinite group polyhedra, and hence are potentially strong. © 2008 SpringerVerlag.
published proceedings
author list (cited authors)
citation count
complete list of authors

Kianfar, KiavashFathi, 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