Benders's Method Revisited.
Abstract
The master problem in Benders's partitioning method is an integer program with a very large number of constraints, each of which is usually generated by solving the integer program with the constraints generated earlier. Computational experience shows that the subset B of those constraints of the master problem that are satisfied with equality at the linear programming optimum often play a crucial role in determining the integer optimum, in the sense that only a few of the remaining inequalities are needed. We characterize this subset B of inequalities. Though the best upper bound (often attained) on the cardinality of B is 2 to the P power, where p is the number of integer-constrained variables that are basic at the linear programming optimum, none of the inequalities in B is implied by the remaining inequalities of the master problem. We then give an efficient procedure for generating an appropriate subset of the inequalities in B, which leads to a considerably improved version of Benders's method. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1977
- Accession Number
- ADA048887
Entities
People
- Christian Bergthaller
- Egon Balas
Organizations
- Carnegie Mellon University