A simplex-based algorithm for 0-1 mixed integer programming

Jean Philippe P. Richard, Ismael R. De Farias, George L. Nemhauser

Research output: Chapter in Book/Report/Conference proceedingChapter

1 Scopus citations

Abstract

We present a finitely convergent cutting plane algorithm for 0-1 mixed integer programming. The algorithm is a hybrid between a strong cutting plane and a Gomory-type algorithm that generates violated facet-defining inequalities of a relaxation of the simplex tableau and uses them as cuts for the original problem. We show that the cuts can be computed in polynomial time and can be embedded in a finitely convergent algorithm.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsMichael Junger, Gerhard Reinelt, Giovanni Rinaldi
PublisherSpringer-Verlag
Pages158-170
Number of pages13
ISBN (Print)3540005803, 9783540005803
DOIs
StatePublished - 2003

Publication series

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

Fingerprint Dive into the research topics of 'A simplex-based algorithm for 0-1 mixed integer programming'. Together they form a unique fingerprint.

  • Cite this

    Richard, J. P. P., De Farias, I. R., & Nemhauser, G. L. (2003). A simplex-based algorithm for 0-1 mixed integer programming. In M. Junger, G. Reinelt, & G. Rinaldi (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 158-170). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2570). Springer-Verlag. https://doi.org/10.1007/3-540-36478-1_15