Benders decomposition is a broadly used exact solution method for stochastic programs, which has been increasingly applied to solve transportation and logistics planning problems under uncertainty. However, this strategy comes with important drawbacks, such as a weak master problem following the relaxation step that confines the dual cuts to the scenario subproblems. In this paper, we propose a partial Benders decomposition methodology, based on the idea of including explicit information from the scenario subproblems in the master. To investigate the benefits of this methodology, we apply it to solve a general class of two-stage stochastic multicommodity network design models. Specifically, we solve the challenging variant of the model where both the demands and the arc capacities are stochastic. Through an extensive experimental campaign, we clearly show that the proposed methodology yields significant benefits in computational efficiency, solution quality, and stability of the solution process.

(2021). Partial Benders Decomposition: General Methodology and Application to Stochastic Network Design [journal article - articolo]. In TRANSPORTATION SCIENCE. Retrieved from http://hdl.handle.net/10446/170922

Partial Benders Decomposition: General Methodology and Application to Stochastic Network Design

Maggioni, Francesca;
2021-01-01

Abstract

Benders decomposition is a broadly used exact solution method for stochastic programs, which has been increasingly applied to solve transportation and logistics planning problems under uncertainty. However, this strategy comes with important drawbacks, such as a weak master problem following the relaxation step that confines the dual cuts to the scenario subproblems. In this paper, we propose a partial Benders decomposition methodology, based on the idea of including explicit information from the scenario subproblems in the master. To investigate the benefits of this methodology, we apply it to solve a general class of two-stage stochastic multicommodity network design models. Specifically, we solve the challenging variant of the model where both the demands and the arc capacities are stochastic. Through an extensive experimental campaign, we clearly show that the proposed methodology yields significant benefits in computational efficiency, solution quality, and stability of the solution process.
articolo
2021
Crainic, Teodor Gabriel; Hewitt, Mike; Maggioni, Francesca; Rei, Walter
(2021). Partial Benders Decomposition: General Methodology and Application to Stochastic Network Design [journal article - articolo]. In TRANSPORTATION SCIENCE. Retrieved from http://hdl.handle.net/10446/170922
File allegato/i alla scheda:
File Dimensione del file Formato  
trsc.2020.1022.pdf.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 1.59 MB
Formato Adobe PDF
1.59 MB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/170922
Citazioni
  • Scopus 33
  • ???jsp.display-item.citation.isi??? 21
social impact