On the exact separation of mixed integer knapsack cuts

Ricardo Fukasawa, Marcos Goycoolea

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

During the last decades, much research has been conducted on deriving classes of valid inequalities for mixed integer knapsack sets, which we call knapsack cuts. Bixby et al. (The sharpest cut: the impact of Manfred Padberg and his work. MPS/SIAM Series on Optimization, pp. 309-326, 2004) empirically observe that, within the context of branch-and-cut algorithms to solve mixed integer programming problems, the most important inequalities are knapsack cuts derived by the mixed integer rounding (MIR) procedure. In this work we analyze this empirical observation by developing an algorithm to separate over the convex hull of a mixed integer knapsack set. The main feature of this algorithm is a specialized subroutine for optimizing over a mixed integer knapsack set which exploits dominance relationships. The exact separation of knapsack cuts allows us to establish natural benchmarks by which to evaluate specific classes of them. Using these benchmarks on MIPLIB 3.0 and MIPLIB 2003 instances we analyze the performance of MIR inequalities. Our computations, which are performed in exact arithmetic, are surprising: In the vast majority of the instances in which knapsack cuts yield bound improvements, MIR cuts alone achieve over 87% of the observed gain.

Original languageEnglish
Pages (from-to)19-41
Number of pages23
JournalMathematical Programming
Volume128
Issue number1-2
DOIs
StatePublished - Jun 2011

Keywords

  • Cutting plane algorithms
  • Mixed integer knapsack problem
  • Mixed integer programming

Fingerprint

Dive into the research topics of 'On the exact separation of mixed integer knapsack cuts'. Together they form a unique fingerprint.

Cite this