Benders's method revisited

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. If an optimal basic solution to the linear program is nondegenerate in the continuous variables and has p integer-constrained basic variables, then the corresponding set B contains at most 2^p inequalities, none of which is implied by the others. We 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.