Tailored Benders decomposition for two-stage distributionally robust combinatorial optimisation

Ozgurbuz, Ekin, Bektas, Tolga ORCID: 0000-0003-0634-144X and Iris, Cagatay ORCID: 0000-0001-5422-354X (2026) Tailored Benders decomposition for two-stage distributionally robust combinatorial optimisation EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 333 (1). pp. 53-66. ISSN 0377-2217, 1872-6860

Text EJOR_Submission_Revised_Document.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (289kB) | Preview

Abstract

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.

Item Type:	Article
Uncontrolled Keywords:	Combinatorial optimisation, Distributionally robust optimisation, Kullback-Leibler divergence ambiguity set, Facility location, Benders decomposition
Divisions:	Faculty of Humanities & Social Sciences Faculty of Humanities & Social Sciences > School of Management Faculty of Humanities & Social Sciences > Faculty of Humanities & Social Sci (All T&R Staff) Faculty of Humanities & Social Sciences > School of Management > School of Management (T&R Staff) Faculty of Humanities & Social Sciences > School of Management > Operations and Supply Chain Management
Depositing User:	Symplectic Admin
Date Deposited:	29 Jan 2026 09:58
Last Modified:	23 May 2026 10:57
DOI:	10.1016/j.ejor.2026.01.048
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3196812
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.