Benders's Method Revisited.
Management sciences research rept.,
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
The master problem in Benderss 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 Benderss method. Author
- Theoretical Mathematics