Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria

Abstract

This paper proposes methodology for improving the performance of Benders decomposition when applied to mixed integer programs. It introduces a new technique for accelerating the convergence of the algorithm and theory for distinguishing “good” model formulations of a problem that has distinct but equivalent mixed integer programming representations. The acceleration technique is based upon selecting judiciously from the alternate optima of the Benders subproblem to generate strong or pareto-optimal cuts. This methodology also applies to a much broader class of optimization algorithms that includes Dantzig-Wolfe decomposition for linear and nonlinear programs and related “cutting plane” type algorithms that arise in resource directive and price decomposition. When specialized to network location problems, this cut generation technique leads to very efficient algorithms that exploit the underlying structure of these models. In discussing the “proper” formulation of mixed integer programs, we suggest criteria for comparing various mixed integer formulations of a problem and for choosing formulations that can provide stronger cuts for Benders decomposition. From this discussion intimate connections between the previously disparate viewpoints of strong Benders cuts and tight linear programming relaxations of integer programs emerge.