Combining optimisation and simulation using logic-based Benders decomposition
From MaRDI portal
Abstract: Operations research practitioners frequently want to model complicated functions that are are difficult to encode in their underlying optimisation framework. A common approach is to solve an approximate model, and to 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 the master problem. The simulation data is 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.
Cites work
- scientific article; zbMATH DE number 1638973 (Why is no real title available?)
- scientific article; zbMATH DE number 2084694 (Why is no real title available?)
- scientific article; zbMATH DE number 1550909 (Why is no real title available?)
- L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
- A mathematical model for the optimization of the airport check-in service problem
- Canonical Cuts on the Unit Hypercube
- Check-in computation and optimization by simulation and IP in combination
- Disaggregated Benders decomposition and branch-and-cut for solving the budget-constrained dynamic uncapacitated facility location and network design problem
- Handbook of constraint programming.
- Interdiction Games and Monotonicity, with Application to Knapsack Problems
- Logic-Based Benders Decomposition and Binary Decision Diagram Based Approaches for Stochastic Distributed Operating Room Scheduling
- Logic-based Benders decomposition
- Logic-based Benders decomposition for large-scale optimization
- Partitioning procedures for solving mixed-variables programming problems
- Stochastic allocation and scheduling for conditional task graphs in multi-processor systems-on-chip
- Stochastic planning and scheduling with logic-based Benders decomposition
- The Benders decomposition algorithm: a literature review
- The integer \(L\)-shaped method for stochastic integer programs with complete recourse
Cited in
(4)- Solving a multi-resolution model of the train platforming problem using Lagrangian relaxation with dynamic multiplier aggregation
- A generalized Benders decomposition approach for the optimal design of a local multi-energy system
- Logic-based Benders decomposition for additive manufacturing scheduling on unrelated parallel machines
- Logic-based benders decomposition methods for the distributed flexible job shop scheduling problem
This page was built for publication: Combining optimisation and simulation using logic-based Benders decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087478)
