On the exact separation of mixed integer knapsack cuts

Ricardo Fukasawa, Marcos Goycoolea

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations


During the last decades, much research has been conducted deriving classes of valid inequalities for single-row mixed integer programming polyhedrons. However, no such class has had as much practical success as the MIR inequality when used in cutting plane algorithms for general mixed integer programming problems. In this work we analyze this empirical observation by developing an algorithm which takes as input a point and a single-row mixed integer polyhedron, and either proves the point is in the convex hull of said polyhedron, or finds a separating hyperplane. The main feature of this algorithm is a specialized subroutine for solving the Mixed Integer Knapsack Problem which exploits cost and lexicographic dominance. Separating over the entire closure of single-row systems allows us to establish natural benchmarks by which to evaluate specific classes of knapsack cuts. Using these benchmarks on Miplib 3.0 instances we analyze the performance of MIR inequalities. Computations are performed in exact arithmetic.

Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization - 12th International IPCO Conference, Proceedings
PublisherSpringer Verlag
Number of pages15
ISBN (Print)9783540727910
StatePublished - 2007
Event12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII - Ithaca, NY, United States
Duration: 25 Jun 200727 Jun 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4513 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII
Country/TerritoryUnited States
CityIthaca, NY


  • Cutting plane algorithms
  • Integer programming


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

Cite this