DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
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
APPROVED FOR PUBLIC RELEASE