Speeding-up Benders decomposition method

 

Abstract: Benders decomposition technique (Benders, 1962) is based on the idea of exploiting decomposable structure present in the formulation of a given problem so that its solution can be converted into the solution of several smaller sub-problems. One is the slave problem which is obtained by fixing a number of decision variables of the initial problem to a feasible value and the second one is the restricted master problem which is expected to provide the optimal solution after the addition of a number of cuts. The cuts are deduced from the resolution of the slave problem in each iteration of the algorithm. In each iteration, cuts are appended to restricted master problem which is solved again to optimality. Benders method is an algorithm that has been applied successfully to a variety of applications and different fields of mathematical programming as for example stochastic programming, global optimization, hierarchical optimization etc. In some cases the straightforward application of the classical Benders algorithm does not lead to fast convergence. Over the years various techniques have been proposed to speed-up the classical Benders decomposition algorithm. The work presented in the literature has mainly focused on either reducing the number of iterations of the algorithm or on restricting the solution space of the decomposed problems.

 

This work presents two new strategies for the speeding-up of the Benders algorithm which are applied to two case studies in order to evaluate their efficiency. These strategies referred to as: covering cut bundle (CCB) generation [saharidis et al. 2009] and maximum feasible sub-system (MFS) cut generation [Saharidis and Ierapetritou 2009]. Both strategies implement in a novel way the multiple constraints generation idea. The CCB and MFS generation are applied to mixed integer problems arising from two types of applications the scheduling of crude oil [Saharidis, 2006] and the scheduling problem for multi-product, multi-purpose batch plants [Ierapetritou and Floudas, 1998]. In both cases CCB and MFS significantly decrease the number of iterations of the Benders method leading to improved resolution times.

 

 

Benders, J.F. Partitioning Procedures for Solving Mixed-Variables Programming Problems. Numerische Mathematic. 1962, 4, p. 238-252.

 

Saharidis, G.K.; M.Minoux; Ierapetritou, M.G. Accelerating Benders decomposition using covering cut bundle generation. Accepted in International Transactions in Operational Research. 2009.

 

Saharidis G.K.; Ierapetritou, M.G. "Improving Benders decomposition using Maximum Feasible Sub-system (MFS) Cut Generation Strategy" Industrial Engineering and Chemistry Research 2009

 

Saharidis, G.K. Pilotage de production a moyen terme et a court terme: contribution aux problematique d'optimisation globale vc locale et a l'ordonnancement dans les raffineries. Genie Industriel. Vol. PhD. 2006, Paris: Ecole Centrale Paris. 150.

 

Ierapetritou, M.G.; Floudas, C. Effective Continuous-time Formulation for Short-Term Scheduling: I Multipurpose Batch Processes Industrial & Engineering Chemical Research. 1998 37(11), p. 4341-4359.