### 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 language | English |
---|---|

Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Editors | Michael Junger, Gerhard Reinelt, Giovanni Rinaldi |

Publisher | Springer-Verlag |

Pages | 158-170 |

Number of pages | 13 |

ISBN (Print) | 3540005803, 9783540005803 |

DOIs | |

State | Published - 2003 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 2570 |

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