- The polar of a simple mixed-integer set Ming Zhao (mzhao buffalo.edu) Ismael de Farias (defarias buffalo.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 mixed-integer rounding (MIR) set of Nemhauser and Wolsey and the mixing-MIR 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: mixed-integer programming, branch-and-cut, polyhedral combinatorics, simple mixed-integer set, lot-sizing Category 1: Integer Programming Citation: State University of New York at Buffalo Download: [PDF]Entry Submitted: 09/13/2005Entry Accepted: 09/13/2005Entry Last Modified: 09/13/2005Modify/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. 