### Benders' decomposition in practice

14th July 2017

I hope that you have read my previous blog on Benders' decomposition. If not, I suggest you read that before continuing. Otherwise, I will assume that you are familiar with the implementation effort that is required when using Benders' decomposition.

This blog is a review of the paper The recoverable robust facility location problem by Eduardo Álvarez-Miranda and Elena Fernández and Ivana Ljubić. I found this paper interesting for two reasons. The first is that it is another application of recoverable robustness. This is a topic that I have published in previously with a focus on an airline applications. The second is the application of Benders' decomposition. I believe that this paper is a great example of what I was explaining in my previous blog on Benders' decomposition: once you decide to use Benders' decomposition, that is only the start of a very big implementation effort. In this blog I will give a review of the paper, highlighting some of the more interesting enhancement techniques.

The recoverable robust facility location problems

This paper is a very nice example of applying recoverable robustness. The facility location problem really suited this technique. To start with, I will provide a short description of the facility location problem. We require a set of customers (*I*), a set of facility locations (*J*) and a set of links (edges in a graph) that link the customers to one or more facilities (*A*). In addition, there is a fixed cost for opening each facility and a transportation cost for facility *j* supplying customer *i*. The facility location problem is to minimise the cost of satisfying the demand of all customers.

The facility location problem is a classical problem in operations research. As such, there have been many papers dedicated to this topic. Much focus has been on the deterministic setting. Additionally, there has been interest in stochastic and robust variants. The recoverable robustness approach applied in this paper is a nice intermediate step between stochastic programming and robust optimisation.

The recoverable robustness technique requires the modelling of uncertainty scenarios that affect the planned deterministic solution. In this case, the authors consider uncertainty on the facility side, the customer side and on the transportation links. Examples of these three types of uncertainty are i) changes to the fixed opening costs for the facilities, ii) changes to the demand of the customers and iii) changes to the transportation cost between the facilities and the customers. By considering the three types of uncertainty, the authors aim to cover all sources of uncertainty for the facility location problems.

Applying Benders' decomposition

Recoverable robustness problems exhibit a classical structure that is particularly suitable for the application of Benders' decomposition. That is, the first stage, or deterministic, problem can be set as the Benders' decomposition master problem and each of the recovery scenarios make up the separable subproblems. So it is understandable why the authors chose to use Benders' decomposition for this problem. Additionally, the experience of the authors with decomposition techniques would have also motivated the use of the solution algorithm.

The enhancements

As mentioned at the start of this blog, the authors apply many enhancements to the Benders' decomposition algorithm. I will give a brief overview of each of the enhancement that have been applied. Many of these are well known from the literature, or variants of well known techniques, and others have been developed specifically for this problem. However, I believe that many of these could be generalised to be applied to be applied in different Benders' decomposition implementations.

Finally, the authors develop a primal heuristic and special branching rules to improve the convergence of the Benders' decomposition algorithm.

Review

One thing I like about this paper is that is clearly shows the work that is needed to implement a good Benders' decomposition algorithm. In my previous blog, I mentioned a number of enhancement techniques and interestingly none of them have been applied here. However, many of the same ideas still come through: strengthening cuts, generating cuts from the LP solution, and generating more cuts from points instead of only the LP and IP optima.

As said in the previous blog, Benders' decomposition is a valuable algorithmic technique; however, you have to be ready for a big implementation effort to make the technique effective.

*Transportation Research Part B: Methodological,*79, 93-120. 2015.

*Operations Research Letters,*13(3),133–142. 1993.

*Operations Research,*29(3):464–484, 1981.

*Mathematical Programming,*98(1-3), 23-47. 2003.

*INFORMS Journal on Computing,*21 (2), 333–345. 2009.