Richard, JPP
de Farias, IR
Nemhauser, GL.
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.
Bibliographic reference |
Richard, JPP ; de Farias, IR ; Nemhauser, GL.. A simplex-based algorithm for 0-1 mixed integer programming.5th International Workshop on Combinatorial Optimization (AUSSOIS(France), Mar 05-09, 2001). In: Lecture Notes in Computer Science, Vol. 2570, p. 158-170 (2003) |
Permanent URL |
http://hdl.handle.net/2078.1/61576 |