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.

► A bilinear optimization scheme based on a distance metric is proposed to speed up Benders decomposition for solving large-scale mixed integer linear programming problems. ► A sequential procedure is suggested to solve the bilinear programming effectively. ► CPLEX was used to implement the suggested approach. ► Simulation results for scheduling of a multiproduct batch plant are presented to show the efficacy of the proposed method.