  


The polar of a simple mixedinteger set
Ming Zhao (mzhaobuffalo.edu) Abstract: We study the convex hull $P$ of the set $S = \{(x, y) \in \Re_{+} \times Z^{n}: x + B_{i} y_{ij} \geq b_{ij}, j \in N_{i}, i \in M\}$, where $M = \{1, \ldots, m\}$, $N_{i} = \{1, \ldots, n_{i}\}$ $\forall i \in M$, $\sum_{i = 1}^{m}n_{i} = n$, and $B_{1}  \cdots  B_{m}$. The set $P$ generalizes the mixedinteger rounding (MIR) set of Nemhauser and Wolsey and the mixingMIR set of G\"{u}nl\"{u}k and Pochet. Our main result is a {\em compact} full inequality description of $\Omega$, the polar of $P$. In the worst case, the number of inequalities $I(\Omega)$ in our description of $\Omega$ grows exponentially with $n$. However, when $B_{m} / B_{1}$ is bounded by a polynomial of $n$, $I(\Omega)$ grows polynomially with $n$. In particular, when $B_{m} / B_{1}$ is bounded by a constant, $I(\Omega) = O(n)$. Also, when $m$ is fixed, $I(\Omega)$ grows polynomially with $n$, regardles of the values of the $B_{i}$'s. This means that, in these cases, it is possible to find a most violated cut for $(x^{*}, y^{*}) \not \in S$ in polynomial time. Finally, we indicate how our study may be extended to the case of nondivisible $B_{i}$'s. Keywords: mixedinteger programming, branchandcut, polyhedral combinatorics, simple mixedinteger set, lotsizing Category 1: Integer Programming Citation: State University of New York at Buffalo Download: [PDF] Entry Submitted: 09/13/2005 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  