- The Mixing-MIR Set with Divisible Capacities Ming Zhao (mzhaobuffalo.edu) Ismael de Farias (defariasbuffalo.edu) Abstract: 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$. Keywords: mixed-integer programming, simple mixed-integer set, polyhedral combinatorics, computational complexity, branch-and-cut, lot-sizing Category 1: Integer Programming Category 2: Integer Programming ((Mixed) Integer Linear Programming ) Category 3: Integer Programming (Cutting Plane Approaches ) Citation: Download: [PDF]Entry Submitted: 11/05/2006Entry Accepted: 11/09/2006Entry Last Modified: 11/05/2006Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.