A Modified Benders' Partitioning Algorithm for Mixed Integer Programming

Dale McDaniel and Mike Devine
Additional contact information
Dale McDaniel: California State University at Northridge
Mike Devine: University of Oklahoma

Management Science, 1977, vol. 24, issue 3, 312-319

Abstract: As applied to mixed-integer programming, Benders' original work made two primary contributions: (1) development of a "pure integer" problem (Problem P) that is equivalent to the original mixed-integer problem, and (2) a relaxation algorithm for solving Problem P that works iteratively on an LP problem and a "pure integer" problem. In this paper a modified algorithm for solving Problem P is proposed, in which the solution of a sequence of integer programs is replaced by the solution of a sequence of linear programs plus some (hopefully few) integer programs. The modified algorithm will still allow for taking advantage of any special structures (e.g., an LP subproblem that is a "network problem") just as in Benders' original algorithm. The modified Benders' algorithm is explained and limited computational results are given.

Date: 1977
References: Add references at CitEc
Citations: View citations in EconPapers (69)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.24.3.312 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:24:y:1977:i:3:p:312-319

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().