Improving benders decomposition using maximum feasible subsystem (MFS) cut generation strategy

A new multi-generation of cuts algorithm is presented in this paper to improve the efficiency of Benders decomposition approach for the cases that optimality cuts are difficult to be achieved within the iterations of the algorithm. This strategy is referred to as maximum feasible subsystem (MFS) cut generation strategy. In this approach in each iteration of the Benders algorithm an additional cut is generated that has the property to restrict the value of the objective function of the Benders master problem. To illustrate the efficiency of the proposed strategy, it is applied to a scheduling problem of multipurpose multiproduct batch plant. Two different partitioning alternatives are tested in order to show the importance of the way that a problem is decomposed upon the efficiency of the Benders algorithm. The application of the proposed acceleration procedure results in substantial reduction of CPU solution time and the total number of iterations in both decomposition alternatives. (C) 2009 Elsevier Ltd. All rights reserved.