A tighter cut generation strategy for acceleration of Benders decomposition

This paper presents a novel strategy for speeding up the classical Benders decomposition for large-scale mixed integer linear programming problems. The proposed method is particularly useful when the optimality cut is difficult to obtain. A ratio of distances from a feasible point to an infeasible point and a feasibility cut is used as a metric to determine the tightest constraint for the region located by the feasible point, thus improving the convergence rate. Application of the proposed approach to a multi-product batch plant scheduling problem shows substantial improvement both in the computational time and the number of iterations. (C) 2012 Elsevier Ltd. All rights reserved.