Generalized mixed integer rounding inequalities: facets for infinite group polyhedra |
| |
Authors: | Kiavash Kianfar Yahya Fathi |
| |
Institution: | (1) Department of Industrial and Systems Engineering, Texas A&M University, College Station, TX 77843-3131, USA;(2) Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC 27695-7906, USA |
| |
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.
|
| |
Keywords: | Mixed integer rounding Mixed integer programming Infinite group polyhedron Valid inequality Facet |
本文献已被 SpringerLink 等数据库收录! |
|