We study the set $S = \{(x, y) \in \Re_{+} \times Z^{n}: x + B_{j} y_{j} \geq b_{j}, j = 1, \ldots, n\}$, where $B_{j}, b_{j} \in \Re_{+} - \{0\}$, $j = 1, \ldots, n$, and $B_{1} | \cdots | B_{n}$. The set $S$ generalizes the mixed-integer rounding (MIR) set of Nemhauser and Wolsey and the mixing-MIR set of G\"{u}nl\"{u}k and Pochet. In addition, it arises as a substructure in general mixed-integer programming (MIP), such as in lot-sizing. Despite its importance, a number of basic questions about $S$ remain unanswered, including the computational complexity of optimization over $S$ and how to efficiently find a most violated cutting plane valid for $P = conv (S)$. One popular approach is to establish and analyze the full inequality description of $P$, or at least interesting families of facets valid for it. Unfortunately, the inequality description of $P$ turns out to be tremendously complicated, and establishing it either fully or partially is an extraordinary task. Fortunately, the extreme points and extreme rays of $P$ have a simple and elegant structure that proves insightful in deriving important properties of $S$. We give all extreme points and extreme rays of $P$. In the worst case, the number of extreme points grows exponentially with $n$. However, we show that, in some interesting cases, it is bounded by a polynomial of $n$. Finally, we use our results on the extreme points of $P$ to give a polynomial-time separation oracle for the polar set of $P$, which, in turn, gives a polynomial-time separation oracle for $P$ and establishes the tractability of optimization over $S$.

## Article

Download

View The Mixing-MIR Set with Divisible Capacities