Lagrange dual bound computation for stochastic service network design

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

Research output: Journal PublicationArticlepeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Pages (from-to)1097-1112
Number of pages16
JournalEuropean Journal of Operational Research
Issue number3
Early online date3 Feb 2022
Publication statusPublished - 1 Nov 2022


  • Lagrangian relaxation
  • Progressive hedging
  • Service network design
  • Stochastic mixed-integer programming
  • Transportation

ASJC Scopus subject areas

  • Computer Science (all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'Lagrange dual bound computation for stochastic service network design'. Together they form a unique fingerprint.

Cite this