  


The MixingMIR Set with Divisible Capacities
Ming Zhao (mzhaobuffalo.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 mixedinteger rounding (MIR) set of Nemhauser and Wolsey and the mixingMIR set of G\"{u}nl\"{u}k and Pochet. In addition, it arises as a substructure in general mixedinteger programming (MIP), such as in lotsizing. 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 polynomialtime separation oracle for the polar set of $P$, which, in turn, gives a polynomialtime separation oracle for $P$ and establishes the tractability of optimization over $S$. Keywords: mixedinteger programming, simple mixedinteger set, polyhedral combinatorics, computational complexity, branchandcut, lotsizing 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/2006 Modify/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  