Lagrange dual bound computation for stochastic service network design

Xiaoping Jiang, Ruibin Bai, Jianfeng Ren, Jiawei Li and Graham Kendall

European Journal of Operational Research, 2022, vol. 302, issue 3, 1097-1112

Abstract: Information on lower bounds plays an important role in the development of exact and heuristic methods for stochastic service network design (SSND). In this paper, we consider the Lagrange dual problem of SSND for computing lower bounds. The Lagrange dual problem is obtained by introducing scenario bundling into scenario-wise decomposition of the SSND model and dualizing the non-anticipativity constraints in a Lagrangian fashion. Our theoretical analysis establishes the superiority of the resulting optimal Lagrange dual bound over that in the case of scenario-wise decomposition. The Lagrange dual problem is solved from the primal perspective by employing the recently proposed FW-PH algorithm, which combines Progressive Hedging with a Frank-Wolfe-like method. To improve the computing efficiency, scenario-wise decomposition in the FW-PH algorithm is replaced with bundle-wise decomposition, which divides the problem by scenario bundles into multiple-scenario subproblems, rather than by individual scenarios into single-scenario subproblems. Scenario bundles are constructed using Gaussian mixture models. Our convergence analysis shows that this improvement retains the desirable theoretical property of FW-PH about convergence to the optimal Lagrange dual value. Computational experiments on SSND instances demonstrate that the improved FW-PH algorithm is far superior to the basic version, providing either a dramatic saving in the run-time required to achieve convergence or a much tighter lower bound when terminated due to the time limit.

Keywords: Transportation; Service network design; Stochastic mixed-integer programming; Lagrangian relaxation; Progressive hedging (search for similar items in EconPapers)
Date: 2022
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/S0377221722000820
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:302:y:2022:i:3:p:1097-1112

DOI: 10.1016/j.ejor.2022.01.044

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 ().