Tailored Benders decomposition for two-stage distributionally robust combinatorial optimisation

This paper presents a two-stage distributionally robust formulation of combinatorial optimisation problems under uncertainty, wherein the first stage involves integer decisions, the second stage comprises continuous linear problems, and the ambiguity set uses Kullback-Leibler divergence. A tractable reformulation that leverages the properties of the Kullback-Leibler divergence is first proposed. The paper describes a tailored Benders decomposition algorithm enhanced through Pareto-optimal cuts and bounding techniques to obtain the optimal solution. Extensive computational experiments on the robust capacitated facility location problem are conducted to assess solution characteristics and to compare the performance of deterministic, stochastic, and distributionally robust approaches under scenarios characterised by limited observations. Comparative experiments show that our tailored Benders decomposition algorithm consistently outperforms two state-of-the-art solution approaches, particularly on larger instances where benchmark methods fail to return optimal solutions within the time limit. Experiments are also conducted to observe the stability of the proposed framework under limited data and the effects of sample sizes on the computational time. The findings demonstrate the trade-offs between strategic decisions and operational characteristics in determining the index of ambiguity. The robustness of unmet demand characteristics is ensured by increasing first-stage investments, such as the average number of facilities and associated first-stage costs, and decreasing average number of customers per facility and average facility utilisation.