Combining optimisation and simulation using logic-based Benders decomposition

M.A. Forbes, M.G. Harris, H.M. Jansen, F.A. van der Schoot and T. Taimre

European Journal of Operational Research, 2024, vol. 312, issue 3, 840-854

Abstract: Operations Research practitioners often want to model complicated functions that are difficult to encode in their underlying optimisation framework. A common approach is to solve an approximate model, and then use a simulation to evaluate the true objective value of one or more solutions. We propose a new approach to integrating simulation into the optimisation model itself. The idea is to run the simulation at each incumbent solution to a master problem. The simulation results are then used to guide the trajectory of the optimisation model itself using logic-based Benders cuts. We test the approach on a class of stochastic resource allocation problems with monotonic performance measures. We derive strong novel Benders cuts that are provably valid for all problems of the given form. We consider two concrete examples: a nursing home shift scheduling problem, and an airport check in counter allocation problem. While previous papers on these applications could only approximately solve realistic instances, we are able to solve them exactly within a reasonable amount of time. Moreover, while those papers account for the inherent variance of the problem by including estimates of the underlying random variables as model parameters, we are able to compute sample-average approximations to optimality with up to 100 scenarios.

Keywords: Integer programming; Logic-based Benders decomposition; Simulation; Resource allocation; Shift scheduling (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172300591X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:312:y:2024:i:3:p:840-854

DOI: 10.1016/j.ejor.2023.07.032

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().