The mixing-MIR set with divisible capacities

Research output: Contribution to journalArticle

12 Scopus citations

Abstract

We study the set S = {(x, y) ε R+ × Zn : x + Bjyj ≥ bj, j = 1, ..., n}, where B j, bj ε Re+ - {0}, j = 1, ..., n, and B 1 | ... | B n . The set S generalizes the mixed-integer rounding (MIR) set of Nemhauser and Wolsey and the mixing-MIR set of Günlü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 tractability of optimization over S and how to efficiently find a most violated cutting plane valid for P = conv (S). We address these questions by analyzing the extreme points and extreme rays of P. 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. In such cases, it is possible to derive strong cutting planes for P efficiently. Finally, we use our results on the extreme points of P to give a polynomial-time algorithm for solving optimization over S.

Original languageEnglish
Pages (from-to)73-103
Number of pages31
JournalMathematical Programming
Volume115
Issue number1
DOIs
StatePublished - Sep 2008

Keywords

  • Branch-and-cut
  • Computational complexity
  • Lot-sizing
  • Mixed-integer programming
  • Polyhedral combinatorics
  • Simple mixed-integer set
  • Simple-set cutting plane

Fingerprint Dive into the research topics of 'The mixing-MIR set with divisible capacities'. Together they form a unique fingerprint.

  • Cite this