JACQUES F. BENDERS. THEORY, VARIATIONS AND ENHANCEMENTS.

Benders’ Theory is a Mathematical Optimization Methodology as Transcendental as the Simplex Method of George Dantzig.

Draft Version of the Chapter Five of the Book: Large Scale Optimization in Supply Chain & Smart Manufacturing: Theory & Application

To be Published in the series Springer Optimization and Its Applications

Last PDF Version:

https://www.doanalytics.net/Documents/DOA-Benders-Theory-Variation-Enhacements.pdf 

J. F. Benders: Theory, Variations and Enhancements

Abstract. In 1962, J. F. Benders published his seminal theory in the paper "Partitioning Procedures for Solving Mixed Variables Programming Problems" oriented to optimization of mixed integer problems (MIP) that was been the origin of multiples methodologies oriented to solve large-scale problems related with stochastic complex combinatorial and/or dynamic systems. Since its formulation in 1962, the researchers in Benders Theory (BT) have proven that:

• BT is an effective methodology to solve complex problems that cannot be solved using only “best” basic optimization algorithms (CPLEX, GUROBI, XPRESS, … ).
• Algorithms based in Benders’ Theory can solve NP-Hard problems in reasonable time; for this type of problems BT has proven to be an effective methodology to solve complex problems that cannot be solved using “best” mathematical solvers.
• BT is a mature methodology that is in the accelerated growing phase
• There is a gap between the research in mathematical programming and the application of the large-scale methodologies in real world solutions.

 In this book, there are four chapters oriented to teach about Benders’ Theory they are:

1.     J. F. Benders: Theory, Variations and Enhancements

2.     Stochastic Optimization: Fundamentals 

3.     Dynamics and Stochastic Benders Decomposition

4.     The Future: Mathematical Programming 4.0

The chapters present a mathematical review of many of the aspects that must be considered to know about variations and enhancements oriented to: i) expand problems that can be solved based on Benders concepts, and ii) to speed-up the time of the solution of the complex problems.

 INDEX

1.      Benders Theory

1.1.   Framework

1.2.   Benders Partition Theory

1.3.   Duality Theory & Benders Theory

1.3.1.           Dual Coordinator Problem

1.3.2.           Sub-Problem Degenerate Solutions

1.4.   Benders Decomposition

1.4.1.           Standard Bender’s Cuts (SBC)

1.4.2.           Decoupled Bender’s Cuts (DBC)

1.4.3.           Unified Benders Cuts (UBC)

1.5.   Multilevel Benders

1.5.1.           Benders' Tri-level Partition Theory

1.5.2.           Benders' Multilevel Partition Theory

2.      Economic Interpretation

2.1.   Taxonomy of Organizations

2.2.   Cobb-Douglas Production Functions

2.3.   Markets

2.4.   Multisectoral Planning

 3.      Generalizations & Extensions

3.1.   Generalized Benders Decomposition

3.2.   Benders Integer Linear Subproblems

3.3.   Benders Dual Decomposition

3.3.1.           Benders Dual Decomposition Theory

3.3.2.           Benders Dual Decomposition Implementation

3.4.   Logic Based Benders Decomposition

3.5.   Partial Benders Decomposition

 4.      Dynamic and Stochastic Benders’ Theory

 5.      Coordinator Enhancements

5.1.   MIP/MINLP Coordinators

5.1.1.           Multi-Phase Coordinator

5.1.2.           Modified Optimality Cuts

5.1.3.           Inexact Solutions

5.1.4.           Inexact Cuts

5.1.5.           Combinatorial Benders Cuts

5.2.   Trust Region (Regularization)

5.2.1.           Neighborhood Bounding

5.2.2.           Penalizations Movements

5.2.3.           Binary Variables

 6.      Cuts Enhancements

6.1.   Strong Cuts

6.1.1.           Pareto Optimal

6.1.2.           Other Cuts

6.1.3.           Hybrid Cuts

6.2.   Hybrid Strategy

7.      Benders Parallel Optimization

7.1.   Parallel Optimization

7.2.   The Asynchronous Benders Decomposition Method

 8.      Conclusions

1.     Benders Theory

 1.1. Framework

In 1962, J. F. Benders published his seminal theory oriented to optimization of mixed integer problems (MIP) that was been the origin of multiples methodologies oriented to solve large-scale problems. The fundamental idea is the partition of a problem into two subproblems, of reduced complexity, based on the division of the variables like coordination variables and subordinate variables. The solution of the original problem is obtained by the coordinated solution of two complementary subproblems: i) the coordinator linked to the coordination variables, and ii) the sub-problem linked to subordinate variables. The sub-problem provides information to the coordinator by the dual variables associated with its constraints. The coordinator takes the information from the primary level and incorporates it in the form of hyperplanes (Benders cuts) limiting the area of feasibility for the optimal solution of the coordination variables. Benders cuts represent the costs of subordinate variables as a function of the coordination variables. The algorithm defined by Benders is convergent and solves the original problem through the solution of the coordinator problem; it applies only to linear subproblems.

The generalization of the Benders Theory (BT) for several typical cases, where the structure of the optimization problem enables the effective utilization of BT, requires to analyzed three basic cases:

• Decomposition Theory: is useful when it is possible to grouping variables subordinated into independent sets to formulate multiple parallel subordinate subproblems.
• Multilevel Theory: is used when there is a multilevel hierarchical relationship within the variables of the problem, and it is possible inside to subordinate variables to select a new set of coordination variables for establish an additional level of partition.
• Multilevel Decomposition Theory: is the result of the combination of the two previous theories.

The use of these three concepts permits to decompose a mathematical problem in "atoms", in such a way to facilitate its solution by: i) speed-up the solution time, and ii) reducing the memory requirements.

 As a further result, the atomization of the problem allows to work the concepts of:

i)      Asynchronous Parallel Optimization (APO, solve the problem using multiples cores), and

ii)    Distributed Real-Time Optimization (DRTO, solve the problem based on the interaction of multiple smart agents that exchange information continuously, real-time);

these concepts are the base of the optimization in the future.

Three point of view must be considered to know more about BT:

• Mathematical: the original Benders formulation has limitations:

i)      BT requires that all subproblems must be linear, which may not apply to several cases in the real-life; then many researchers have worked on the development of methodologies that allow to apply the concepts of Benders in cases with non- linear and/or discrete subproblems. 

ii)    Although BT is convergent, its speed to find the optimum can be significantly improved, it turned BT into important complement to basic solvers in the solution of very large problems.

• Applications: in a very aggregate manner, Benders applications can be divided into two major groups: i) combinatorial optimization, and ii) dynamic optimization. This fact has generated research works aimed to accelerate the solution time of problems considering their specific features.
• Uncertainty: BT has been applied to stochastic optimization based on scenarios, which inherently includes the concept of scenarios-based decomposition.

 It is important to note, that, even though the variations and improvements have been made in multiple independent research studies, it is possible to integrate “all” in a single paradigm in such a way meet those improvements in an application that are more convenient. To compare methodologies and to present their impact two key performance index (KPI) are considered: i) solution time, and ii) existing gap between the best-known solution (primal bound) and the best-possible solution (dual bound), when the solution is optimal, the gap is zero.

 There are several possibilities for improvement Benders methodology:

1.     Formulating the mathematical problem "properly"

2.     Using the appropriate Benders methodology, according to the mathematical problem

3.     Modifying the master problem according to the formulation

4.     Selecting the correct enhancements to speed-up the solution time; it includes selecting good cuts to add to the master problem at each step.

5.     Making a good selection of initial cuts

6.     Using parallel optimization

The literature review conducted by Rahmaniani et. al. (2017) presents the evidence of the growth of the importance of BT in recent years, which can be attributed to massive development and the drop-in prices of PCs multi-CPUs, enabling the environment to take advantages of atomization/parallelization of optimization algorithmic procedures. BT. The next graphic, from Rahmaniani et. al, presents the number of scientific papers related with BT until 2016.

The following table presents a very small summary of papers showing the gain in speed of the proper use of the improvements in BT. This leads to conclude that the point of reference to compare the speed of mathematical programming to solve complex problems are not the basics solvers, the proper reference is the use of large-scale methodologies that make smart use of these solvers.

There are two of ways to implement the BT enhancements:

• Reformulation of the BT and use computer algebraic languages
• Direct modification of the flow of the solvers.

This document is concentrated in the first alternative, this does not imply a value judgment with respect to the second.

Related papers:

• Dynamic & Stochastic Benders Theory

https://www.dhirubhai.net/pulse/stochastic-dynamic-benders-theory-jesus-velasquez/

• The Future: Mathematical Programming 4.0

https://www.dhirubhai.net/pulse/future-mathematical-programming-jesus-velasquez/

• OPTEX – Optimization Expert System

 https://www.dhirubhai.net/pulse/optex-optimization-expert-system-new-approah-make-models-velasquez/  

 This documents are fundamental to understand the implementation that has been made DO Analytics of the Theory of Benders and its variations in OPTEX Expert Optimization System; it is a working document that will be completed to the extent that research advance in BT and its implementations on OPTEX.

Index

PAST

1.    Benders Theory

2.    Economic Interpretation

3.    Generalizations & Extensions

4.    Stochastic Optimization

5.    Dynamic Benders

6.    Coordinator Enhancements

7.    Cuts Enhancements

8.    Other Enhancements

9.    Benders Parallel Optimization

PRESENT

 10. Benders: Speed Up the Mathematical Programming Algorithms

 11. Benders Optimization Technologies

 FUTURE

12. Normalization & Standardization of Mathematical Programming Modeling

13. Optimization Expert Systems

14. Asynchronous Parallel Optimization

15.Real-Time Distributed Optimization

J. F. Benders Theory & Applications: Past, Present & Future

1.     Benders Theory

 1.1. Jacobus Franciscus (Jacques) Benders

 Jacobus Franciscus (Jacques) Benders (1st June 1924 to 9th January 2017) was a Dutch Mathematician and Emeritus Professor of Operations Research at the Eindhoven University of Technology. In 1963, He was the first Professor in the Netherlands in the field of Operations Research at the Eindhoven University of Technology and is known for his contributions to Mathematical Programming. He retired at the Eindhoven University of Technology on May 31, 1989.

 In 1940s he started his career as statistician for the Rubber Foundation. In 1955 he moved to Shell Laboratory in Amsterdam, where he researched mathematical programming problems concerning the logistics of oil refinery. Later, Benders studied mathematics at the Utrecht University, where he received his Ph. D. in 1960 with the thesis entitled "Partitioning in Mathematical Programming" under supervision of Hans Freudenthal. He developed the technique known as Benders' Partitioning or Benders' Decomposition and used the results in his doctoral thesis. This thesis is a seminal work in Large-Scale Optimizacion Methodologies.

 1.2. Framework

 In 1962, J. F. Benders published his seminal theory oriented to optimization of mixed integer problems (MIP) that was been the origin of multiples methodologies oriented to solve large-scale problems.

Since its formulation in 1962, the researchers in Benders Theory have proven that:

• BT is an effective methodology to solve complex problems that cannot be solved using only “best” basic optimization algorithms (CPLEX, GUROBI, XPRESS, … ).
• Algorithms based in Benders’ Theory can solve NP-Hard problems in reasonable time; for this type of problems BT has proven to be an effective methodology to solve complex problems that cannot be solved using “best” mathematical solvers.
• Benders Theory is a mature methodology that is in the accelerated growing phase; there are many possibilities to research in Benders Theory.
• There is a gap between the research in mathematical programming and the application of the large-scale methodologies in real world solutions.

Looking to the future, it is convenient to consider:

• Benders Theory is a primal methodology (its work in the feasible zone), it is an advantage when: i) the time is a limitation in the optimization process and ii) in real-time distributed optimization.
• The parallel large-scale optimization technologies are the actual state-of-the-art of optimization.
• Benders facilitates the understanding of complex systems dividing the problem in subproblems that represents the operation en each component; it is necessary in the real-time distributed optimization
• Nodaway, the advanced optimization modelers must begin its work using large scale methodologies, because they need to solve large scale problems that the final users need (real-life world).

 The fundamental idea is the partition of a problem into two subproblems, of reduced complexity, based on the division of the variables like coordination variables and subordinate variables. The solution of the original problem is obtained by the coordinated solution of two complementary subproblems: i) the coordinator linked to the coordination variables, and ii) the sub-problem linked to subordinate variables. The sub-problem provides information to the coordinator by the dual variables associated with its constraints. The coordinator takes the information from the primary level and incorporates it in the form of hyperplanes (Benders cuts) limiting the area of feasibility for the optimal solution of the coordination variables. Benders cuts represent the costs of subordinate variables as a function of the coordination variables. The algorithm defined by Benders is convergent and solves the original problem through the solution of the coordinator problem; it applies only to linear subproblems.

The generalization of the Benders Theory (BT) for several typical cases, where the structure of the optimization problem enables the effective utilization of BT, requires to analyzed three basic cases:

• Decomposition Theory: is useful when it is possible to grouping variables subordinated into independent sets to formulate multiple subordinate subproblems. In this case the variables of coordination are also called coupling variables.
• Multilevel Theory: is used when there is a multilevel hierarchical relationship within the variables of the problem, and it is possible inside to subordinate variables to select a new set of coordination variables for establish an additional level of partition.
• Multilevel Decomposition Theory: is the result of the combination of the two previous theories.

The use of these three concepts permits to decompose a mathematical problem in "atoms", in such a way to facilitate its solution by: i) speed-up the solution time, and ii) reducing the memory requirements.

 As a further result, the atomization of the problem allows to work the concepts of:

i)      Asynchronous Parallel Optimization (APO, solve the problem using multiples cores), and

ii)    Distributed Real-time Optimization (DTRO, solve the problem based on the interaction of multiple smart agents that exchange information continuously, real-time); these concepts are the base of the optimization in the future.

 Three point of view must be considered to know more about BT:

• Mathematical: the original Benders formulation has the limitation which requires that all subproblems must be linear, which may not apply to several cases in the real-life; to resolve this problem, many researchers have worked on the development of methodologies that allow to apply the concepts of Benders in cases with subproblems: non- linear (Geofrion 1972, Generalized Benders Decomposition) or discrete (Hocker , Logic Based Benders Decomposition).
• Applications: in a very aggregate manner, Benders applications can be divided into two major groups: i) combinatorial optimization, and ii) dynamic optimization. This fact has generated research works aimed to accelerate the solution time to resolution of problems considering their specific features.
• Uncertainty: BT has been applied to stochastic optimization based on scenarios, which inherently includes the concept of scenarios-based decomposition.

 In a first stage are presented deterministic versions of the methodologies (which are easier to analyze); then, these versions can be converted in stochastic versions.

 It is important to note, that, even though the variations and improvements have been made in multiple independent research studies, it is possible to integrate all the in a single paradigm in such a way meet those improvements in an application that are more convenient. To compare methodologies and to present their impact are two KPIs (key performance index): i) solution time, and ii) existing gap between the best-known solution (primal bound) and the best-possible solution (dual bound), when the solution is optimal, the gap is zero.

The literature review conducted by Rahmaniani et. al. (2016, The Benders Decomposition: A Literature Review) presents the evidence of the growth of the importance of the Benders theory in recent years, which can be attributed to massive development and the drop-in prices of PCs multi-CPUs, enabling the environment to take advantages of atomization/parallelization of optimization algorithmic procedures. The next graphic, from Rahmaniani et. al, presents the number of scientific papers related with BT until 2016.

The scientists interested in BT know, that although the algorithm is convergent, its speed to find the optimum can be significantly improved, it turned BT into important complement to basic solvers in the solution of very large problems.

 There are several possibilities for improvement Benders methodology:

1.     Formulating the mathematical problem "properly"

2.     Using the appropriate Benders methodology, according to the mathematical problem

3.     Modifying the master problem according to the formulation

4.     Selecting the correct enhancements to speed-up the solution time; it includes selecting good cuts to add to the master problem at each step.

5.     Making a good selection of initial cuts

6.     Using parallel optimization

 The following table presents a very small summary of papers showing the gain in speed of the proper use of the improvements in BT. This leads to conclude that the point of reference to compare the speed of mathematical programming to solve complex problems are not the basics solvers, the proper reference is the use of large-scale methodologies that make smart use of these solvers.

There are two of ways to implement the BT enhancements:

• Computer algebraic languages
• Direct modification of the flow of the solvers.

This document is concentrated in the first alternative, this does not imply a value judgment with respect to the second.

 From Rahmaniani et. al. (2016), the next tables present a resume of applications and type of problems that has been solved using BT.

TO READ FULL PAPER PLEASE DOWNLOAD IT: https://goo.gl/SEGcNw

More information: [email protected]