Accession Number:

ADA048887

Title:

Benders's Method Revisited.

Descriptive Note:

Management sciences research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

• Balas,Egon
• Bergthaller,Christian

Report Date:

1977-05-01

Pagination or Media Count:

29.0

Abstract:

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

Descriptors:

• *INTEGER PROGRAMMING
• *INEQUALITIES
• ALGORITHMS
• OPTIMIZATION
• ITERATIONS
• DECOMPOSITION

Subject Categories:

• Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE