Mixing MIR inequalities with two divisible coefficients (Q964181): Difference between revisions

In the paper under review, sets \(P^{MMIX}\subset \mathbb R ^+ \times \mathbb Z ^n\) whose elements satisfy \(s+Lz_t\geq b_t\) \((1\leq t \leq k)\), \(s+Cz_t\geq b_t\) \((k+1\leq t \leq n)\), for fixed reals \(b_t\) \((1\leq t \leq n)\), \(L\), \(C>0\) with \(L/C\in \mathbb Z\), are considered. The authors describe a way to obtain the convex hull conv\((P^{MMIX})\) by applying the mixing procedure twice. This approach yields a description of the extreme points and rays of conv\((P^{MMIX})\). A characterization of each facet of the convex hull is also given. This description leads, on the one hand, to a fast optimization algorithm and, on the other hand, to several polynomial size exact formulations for \(P^{MMIX}\). Alternative extended formulations are obtained starting from a decomposition of the continuous variable. The paper closes with a study of conditions under which adding certain constraints on the integer variable preserves the main results.