Stephen J Maher

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.

The subproblems have integer variables, so classical Benders' decomposition can not be applied. However, it is possible to generate Benders' cuts for integer subproblems using the technique of Laporte and Louveaux (1993). To improve the convergence of the integer Benders' decomposition algorithm it is common to generate cuts from the LP relaxation of the subproblem. This common implementation detail that has been enhanced by the authors.

The authors explain that a cut is only required from the scenario with the worst outcome given the current first stage solution. To avoid unnecessary solves of subproblems, the scenarios are sorted to try to easily identify the worst performing for each LP/IP solution.

Dual lifting is performed on the generated Benders' cuts. This is a strengthening technique that is used instead of the Magnanti-Wong technique. The benefit of the dual lifting approach is that is can be performed in linear time w.r.t to the number of variables.

The zero-half cutting technique is applied to the generated Benders' cuts. This technique draws upon the zero-half cutting plane approach that generates rank-1 Chvátal-Gomory cuts with multipliers restricted to {0, 1/2}. The cut generation method appears to be the first use of zero-half cuts for Benders' decomposition.

It is common that only using the current LP, or IP, to generate cuts is not enough for an efficient Benders' decomposition algorithm. It is useful to generate cuts from multiple points to cut of more areas of the polyhedron. To achieve this, the authors develop a metaheuristic that draws upon concepts of local branching (Fischetti and Lodi (2003), Rei et al.(2009)).

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.

Álvarez-Miranda, E., and Fernández, E., and Ljubić, I. The recoverable robust facility location problem. Transportation Research Part B: Methodological, 79, 93-120. 2015.

Laporte, G., Louveaux, F. The integer L-shaped method for stochastic integer programs with complete recourse. Operations Research Letters, 13(3),133–142. 1993.

T. Magnanti and R. Wong. Accelerating Benders’ decomposition: algorithmic enhancement and model selection criteria. Operations Research, 29(3):464–484, 1981.

Fischetti, M, Lodi, A. Local branching. Mathematical Programming, 98(1-3), 23-47. 2003.

Rei, W., Cordeau, J.-F., Gendreau, M., Soriano, P. Accelerating Benders decomposition by local branching. INFORMS Journal on Computing, 21 (2), 333–345. 2009.