Optimization Online


The polar of a simple mixed-integer set

Ming Zhao (mzhao***at***buffalo.edu)
Ismael de Farias (defarias***at***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/2005
Entry Accepted: 09/13/2005
Entry Last Modified: 09/13/2005

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society