Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore.

Additionally, libraries can receive an extra 5% discount. Learn More

Additionally, libraries can receive an extra 5% discount. Learn More

Antonios Fragkogios (University of Thessaly, Greece) and Georgios K. D. Saharidis (University of Thessaly, Greece)

Copyright: © 2018
|Pages: 11

DOI: 10.4018/978-1-5225-2255-3.ch470

Chapter Preview

TopNowadays, 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.

TopBenders 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.

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.

Search this Book:

Reset

Copyright © 1988-2018, IGI Global - All Rights Reserved