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

Richard, JPP;de Farias, IR;Nemhauser, GL.
(2003) 5th International Workshop on Combinatorial Optimization — Location: AUSSOIS(France) (5.March.2001)

Files

pdfdocument.pdf
  • Restricted Access
  • Adobe PDF
  • 185.12 KB
No access

Details

Authors
  • Richard, JPP
    Author
  • de Farias, IR
    Author
  • Nemhauser, GL.
    Author
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Richard, J., de Farias, I., & Nemhauser, GL. (2003). A simplex-based algorithm for 0-1 mixed integer programming. Lecture Notes in Computer Science, 2570, 158-170. https://doi.org/10.1007/3-540-36478-1_15 (Original work published 2003)