Mixing MIR Inequalities with Two Divisible Coefficients
CONSTANTINO, Miguel
Centro de Investigação Operacional - Departamento de Estatística e Investigação Operacional [CIO - DEIO]
Centro de Investigação Operacional - Departamento de Estatística e Investigação Operacional [CIO - DEIO]
MILLER, Andrew
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
CONSTANTINO, Miguel
Centro de Investigação Operacional - Departamento de Estatística e Investigação Operacional [CIO - DEIO]
Centro de Investigação Operacional - Departamento de Estatística e Investigação Operacional [CIO - DEIO]
MILLER, Andrew
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
< Réduire
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Langue
en
Article de revue
Ce document a été publié dans
Mathematical Programming, Series A. 2010, vol. 123, p. 451-483
Springer
Résumé en anglais
This paper is a polyhedral study of a generalization of the mixing set where two different, divisible coefficients are allowed for the integral variables. Our results generalize earlier work on mixed integer rounding, ...Lire la suite >
This paper is a polyhedral study of a generalization of the mixing set where two different, divisible coefficients are allowed for the integral variables. Our results generalize earlier work on mixed integer rounding, mixing, and extensions. They also directly apply to applications such as production planning problems involving lower bounds or start-ups on production, when these are modeled as mixed-integer linear programs. We define a new class of valid inequalities and give two proofs that they suffice to describe the convex hull of this mixed-integer set. We give a characterization of each of the maximal faces of the convex hull, as well as a closed form description of its extreme points and rays, and show how to separate over this set in O(n log n). Finally, we give several extended formulations of polynomial size, and study conditions under which adding certain simple constraints on the integer variables preserves our main result.< Réduire
Origine
Importé de halUnités de recherche