Large solution space is one of the main features of simulation–optimization problems. Reducing the cardinality of the set of alternatives is a key point for increasing the efficiency of simulation–optimization methods. In this work, a new cutting approach is proposed for this purpose. The approach exploits the Benders Decomposition framework that can be effectively applied when the simulation–optimization problems are represented using Discrete Event Optimization models. Benders Decomposition subproblems represent the simulation components, hence, cuts can be easily generated observing the values of the variables while a system alternative is simulated, without solving any subproblem. The cut generation procedure is proposed to approximately solve the Server Allocation Problem in a tandem queueing system. Results on randomly generated instances show its effectiveness in decreasing the computational effort by reducing the solution space.

Simulation-based Benders Cuts: A New Cutting Approach to Approximately Solve Simulation-Optimization Problems

Mengyi Zhang;Andrea Matta;Arianna Alfieri;Giulia Pedrielli
2018

Abstract

Large solution space is one of the main features of simulation–optimization problems. Reducing the cardinality of the set of alternatives is a key point for increasing the efficiency of simulation–optimization methods. In this work, a new cutting approach is proposed for this purpose. The approach exploits the Benders Decomposition framework that can be effectively applied when the simulation–optimization problems are represented using Discrete Event Optimization models. Benders Decomposition subproblems represent the simulation components, hence, cuts can be easily generated observing the values of the variables while a system alternative is simulated, without solving any subproblem. The cut generation procedure is proposed to approximately solve the Server Allocation Problem in a tandem queueing system. Results on randomly generated instances show its effectiveness in decreasing the computational effort by reducing the solution space.
Proceedings of the Winter Simulation Conference 2018
978-1-5386-6572-5
File in questo prodotto:
File Dimensione Formato  
Simulation-based Benders Cuts A New Cutting Approach to Approximately.pdf

Accesso riservato

: Publisher’s version
Dimensione 544.71 kB
Formato Adobe PDF
544.71 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11311/1070955
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact