The Mixing-MIR Set with Divisible Capacities

Ming Zhao (mzhaobuffalo.edu)
Ismael de Farias (defariasbuffalo.edu)

Abstract: We study the set $S = \{(x, y) \in \Re_{+} \times Z^{n}: x + B_{j} y_{j} \geq b_{j}, j = 1, \ldots, n\}$, where $B_{j}, b_{j} \in \Re_{+} - \{0\}$, $j = 1, \ldots, n$, and $B_{1} | \cdots | B_{n}$. The set $S$ generalizes the mixed-integer rounding (MIR) set of Nemhauser and Wolsey and the mixing-MIR set of G\"{u}nl\"{u}k and Pochet. In addition, it arises as a substructure in general mixed-integer programming (MIP), such as in lot-sizing. Despite its importance, a number of basic questions about $S$ remain unanswered, including the computational complexity of optimization over $S$ and how to efficiently find a most violated cutting plane valid for $P = conv (S)$. One popular approach is to establish and analyze the full inequality description of $P$, or at least interesting families of facets valid for it. Unfortunately, the inequality description of $P$ turns out to be tremendously complicated, and establishing it either fully or partially is an extraordinary task. Fortunately, the extreme points and extreme rays of $P$ have a simple and elegant structure that proves insightful in deriving important properties of $S$. We give all extreme points and extreme rays of $P$. In the worst case, the number of extreme points grows exponentially with $n$. However, we show that, in some interesting cases, it is bounded by a polynomial of $n$. Finally, we use our results on the extreme points of $P$ to give a polynomial-time separation oracle for the polar set of $P$, which, in turn, gives a polynomial-time separation oracle for $P$ and establishes the tractability of optimization over $S$.

Keywords: mixed-integer programming, simple mixed-integer set, polyhedral combinatorics, computational complexity, branch-and-cut, lot-sizing

Category 1: Integer Programming

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation:

Download: [PDF]

Entry Submitted: 11/05/2006
Entry Accepted: 11/09/2006
Entry Last Modified: 11/05/2006

Modify/Update this entry