A tighter cut generation strategy for acceleration of Benders decomposition

作者：Yang Yu; Lee Jong Min^*

来源：Computers & Chemical Engineering, 2012, 44: 84-93.

DOI：10.1016/j.compchemeng.2012.04.015

• Mixed integer linear programming
• Feasibility cut
• Dinkelbach's method
• Scheduling
• Fractional programming
• CPLEX

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.

• 出版日期2012-9-14