Benders and its sub-problems
Creators: name: Maheo, Arthur
Publisher: name: The Australian National University
Year: 2020

description: The Benders decomposition method is a popular approach to solve large-scale mixed-integer programs (MIPs), it decomposes a problem into its integer component, called the master problem, and uses linear duality on the continuous sub-problem to add constraints in the master. It has garnered increasing interest over the years as an alternate, automatic scheme but remains infamously difficult to use efficiently: its first issue is to be hard to implement; a second is problems need to exhibit a specific structure. In particular, the sub-problem cannot contain integer variables because the dual of integer programs is not well-defined. In this thesis, I will first present how to apply Benders to specific problems, with an emphasis on the problem-agnostic components; then, I will present a framework to extend Benders to the case with integer sub-problems. The first part of this thesis contains results demonstrating the efficiency of a tailored Benders decomposition on a public transportation network design problem. Canberra was planned as a collection of semi-autonomous towns separated by green belts. As such, it covers a very large area which makes public transportation challenging, especially during off-peak periods. The bus network comprises 94 bus lines which cover even the most remote suburbs of the city, but the buses are infrequent and run empty most of the time as patronage is low outside of central districts. BusPlus aims to address this issue by using a combination of high-frequency buses and on-demand shuttles. The first contribution is to tailor a Benders decomposition approach to the resulting network design problem and propose potential network configurations validated in a short time. In a follow-up study, we observe that the Benders sub-problem in BusPlus is a shortest path. It is wasteful to use a linear solver where a dedicated algorithm would be more efficient. We use a linear solver because we need the dual costs of the sub-problem to generate Benders cuts. The second contribution is to design an analytical procedure to derive Benders cuts from the primal solution of the sub-problem. By not relying on a linear solver, we can derive Benders cuts for a much lower computational cost and be competitive with a bespoke method. The second part of the thesis will present a new framework to provide state-of-the-art Benders optimisation in a unified environment and handle the case where the sub-problem contains integer variables. Benders decomposition is a powerful tool for solving large MIPs. But it suffers from low convergence in the general case and must rely on the problem exhibiting a suitable structure. The third contribution is to develop a new framework for the case where the sub-problem contains integer variables -- so the dual is not well-defined and we cannot derive Benders cuts. By using the LP relaxation of the sub-problem as a cut-generation tool and a heuristic as a bounding procedure we demonstrate it is possible to use Benders. This approach combines a branch-and-Benders-cut phase which efficiently enumerates those solutions that fall between the LP relaxation and the heuristic, followed by a post-processing phase where we solve the sub-problem to integer optimality; this delay proved to be a major improvement. Two-stage stochastic program are often solved using a variant of Benders because a natural decomposition occurs: the first stage becomes the master problem and the scenario realisation the sub-problem. A recent example is the TSP with outsourcing, where one wants to find a minimum cost route visiting customers with stochastic demand, or use a third-party. The fourth contribution is to propose an exact method for this problem. We develop new enhancements such as: memoisation of the results, extended master formulation, and state-of-the-art heuristics; combined, they yield an interesting result: the solving time scales linearly with the number of scenarios.