The polar of a simple mixed-integer set

Ming Zhao (mzhaobuffalo.edu)
Ismael de Farias (defariasbuffalo.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/2005
Entry Accepted: 09/13/2005
Entry Last Modified: 09/13/2005

Modify/Update this entry