- | ||||
|
![]()
|
The polar of a simple mixed-integer set
Ming Zhao (mzhao 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/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 | |
![]() |