Optimization Online


The Mixing-MIR Set with Divisible Capacities

Ming Zhao (mzhao***at***buffalo.edu)
Ismael de Farias (defarias***at***buffalo.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 )


Download: [PDF]

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

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