The Benders Decomposition

When dealing with large-scale optimization, decomposition techniques take place as effective exact methods. In addition to Dantzig-Wolfe decomposition covered in a previous topic, Benders decomposition is another prominent method used intensively to tackle several large-scale real-life problems.

In this article, I will go through this extremely interesting algorithm that was successful in tackling many large-scale optimization problems. I especially seek to highlight the benefits of using this technique from a practical perspective.

History

Developed by Jacobus Franciscus (Jacques) Benders in 1962, Benders decomposition can be viewed as a divide-and-conquer trick. Indeed, given a mathematical model, the variables are divided into two subsets so that a master problem is solved over the first set of variables, also called complicating variables, and one or several subproblem(s) are solved over the second set of variables given the master problem solution. Based on the subproblem solution, we add either a Feasibility or an Optimality cut, called Benders cut, to the master problem. The latter is solved again and the process continues until optimality. The solution approach for Benders decomposition is, sometimes, referred to as raw generation.

Mathematical Lexicon

As described above, Benders decomposition operates like Dantzig-Wolfe decomposition (the former is the dual of the latter) with a master problem and one or several subproblems. The master problem provides solutions to the subproblem(s) while the subproblem(s) provide Benders cuts to the master problem.

Problem Reformulation

Let’s consider the problem below with two sets of variables x and y.

Assuming that y variables are the complicating variables. When fixing y, the problem can be written as:

Moving to the dual, we obtain:

The model above is referred to as Benders' dual subproblem. The model below is referred to as Benders’ master problem.

Given a solution y, we can solve the Benders dual subproblem and generate a Benders cut to be added to the Benders master problem, which will generate a new solution of y to be given to the Benders dual subproblem. We consider the dual because its feasible region is independent of y.

Algorithm Approach

The Benders algorithm can be summarized in the figure below. In addition to the insights provided above, it is worth mentioning that, in a minimization case, the master problem provides a lower bound on the optimal value of the original problem while the subproblem provides an upper bound on the optimal value of the original problem. Thus, noting g(y) the objective value of the dual subproblem, the algorithm converges when z=g(y) or when the difference is smaller than a selected threshold. Also, a feasibility cut is generated when the dual subproblem is unbounded while an optimality cut is generated when the dual subproblem is feasible and bounded, i.e., has an optimal solution.

Method Benefits

The main benefit of Benders decomposition is that it exploits the structure of the mathematical formulations and breaks the computational bottleneck that takes place when considering the problem as a whole, especially in the large-scale context. It has some other benefits and shortcomings as well. The literature review by Rahmaniani et al. is a good reference to get more insights.

Real Applications

In many real-life problems, decisions are taken in two stages. In such a case, the first stage variables form the master problem while the second stage variables form the subproblem(s). Such a case can be either deterministic or stochastic. In the latter, Benders decomposition is often referred to as the L-shaped method. A simple and yet famous application of Benders decomposition is the facility location problem where a set of clients must be assigned to a set of facilities. Benders decomposition is suitable for such a problem. Still, it stagnates and shows a zigzagging behavior when the number of clients or facilities is huge.

As witnessed again in this article, in research, simple ideas are usually the key or the starting point to tackling the most complex problems. This is a life principle that should always be highlighted in research contexts as well as others !

What do you think about this method? I am looking forward to hearing your ideas :-)