Abstract
Operations Research and Mathematical Programming together with Information Science and Technology are tools used to solve various problems in the modern economic environment. This chapter addresses the Benders Decomposition method, which is used for the solution of problems of Operations Research. This method, applied to certain large-scale mathematical problems, can make their solution feasible (if they cannot be solved with another procedure) or can accelerate the solution process in terms of CPU time. The authors provide a thorough presentation of how the decomposition of a problem is made and the Benders algorithm is applied for its solution. Main purpose of this chapter is to analyze the recent studies that address the method's weaknesses and accelerate its application for the faster solution of mathematical problems. A large number of papers is presented and the contribution of each one of them to the improvement of the method is described.
TopIntroduction
Nowadays, the increased demand for energy and goods around the world has made the business environment more and more complex concerning the design and operation of power systems, supply chain and transportation networks, production scheduling of factories etc. This complexity has made real case studies increasingly difficult to solve due to the large-scale mathematical models constructed. These models do not only depend on the number of parameters, decision variables and constraints. Frequently, even if these features are moderate, optimization problems could still be considered as large-scale due to complicating structures making their solution hard to get.
Information Science and Technology together with Operations Research and Mathematical Programming can show the way towards better solutions in all fields of economy. Nowadays, the evolution of computers combined with mathematical decomposition techniques can solve real size mathematical models and optimize the operation of real-life systems by e.g. avoiding an unpleasant outcome, decreasing operations cost or increasing the overall profit.
The mathematical decomposition techniques aim at decomposing the initial large-scale mathematical model into two or more sub-models based on mathematical programming theorems, as for example, the duality theorem. In principle, the mathematical decomposition techniques do not depend on the case study, but on the structure of the developed mathematical model, which describes the system under study. Mathematical decomposition techniques are:
- •
Benders decomposition (Benders, 1962),
- •
Dantzig-Wolfe decomposition (Dantzig & Wolfe, 1960),
- •
Lagrangian relaxation,
- •
Lagrangian decomposition and
- •
Cross decomposition.
The main goal of this chapter is to present the Benders decomposition method, identify its weaknesses and display all the recent research made to tackle them.
In the next section, a very brief literature review on the method is provided. Following, the method is presented and explained together with its main weaknesses. The same section includes the latest advances from the literature, which address these weaknesses. The next section, future and emerging trends on Benders decomposition are discussed. Finally, the chapter is concluded at the final section.
TopBackground
Benders decomposition technique was introduced by (Benders, 1962) for linear problems with coupling integer variables. Although the algorithm was initially used for block-decomposed large-scale optimization problem, lately the algorithm has been applied also in other types of problems. The Benders method has been applied successfully to stochastic programming (Watkins, McKinney, Lasdon, Nielsen, & Martin, 2000) for the solution of multi-scenario, two-stage and multistage stochastic problems where the scenarios are split to sub-scenarios and studied separately decreasing the amount of data taken under consideration in each optimization step; to global optimization problems (Zhu & Kuno, 2003) to address the non-convexity nature of big data; and more recently to build mathematical models (Ierapetriou & Saharidis, 2009), where a large amount of experimental data are available for model building.
Key Terms in this Chapter
Decomposition Technique: Solution method in which the main idea is to decompose the problem into sub-problems which are simpler to be solved.
Valid Inequality: An inequality which significantly restricts the solution space of a problem without excluding the optimal solution and leading to improve the convergence of a solution approach.
Block-Decomposed Mathematical Model: A mathematical model which can be decomposed into sub-models.
Low Density Benders Cut: A cut involving a small number of decision variables of RMP therefore with low contribution to strengthening the RMP.
Benders Decomposition: Benders decomposition method is a classical approach for combinatorial optimization problems, based on the idea of partition and constraint generation.
Quality of Benders Cut: A measurement of how efficient Benders cut is, affecting the Benders algorithm convergence.
Multi-Generation of Cuts: The generation of more than one constraint in each iteration of Benders algorithm.