Volume-based branch-and-cut algorithm for large-scale fixed-charge multicommodity network design

Rui S. Shibasaki (), Mourad Baïou (), Francisco Barahona (), Philippe Mahey () and Maurício C. de Souza ()
Additional contact information
Rui S. Shibasaki: UPJV
Mourad Baïou: UCA
Francisco Barahona: IBM
Philippe Mahey: UCA
Maurício C. de Souza: UFMG

Annals of Operations Research, 2025, vol. 351, issue 1, No 6, 133-166

Abstract: Abstract The fixed-charge multicommodity capacitated network design (FCMC) problem remains challenging, particularly in large-scale contexts. In this particular case, the ability to produce good-quality solutions in a reasonable amount of time depends on the availability of efficient algorithms. Therefore, this paper proposes a Volume-based branch-and-cut algorithm, which applies a relax-and-cut procedure to solve linear programs in each node of the enumeration tree. Moreover, a Lagrangian feasibility pump heuristic using the Volume Algorithm as a solver for linear programs was implemented to accelerate the search for good feasible solutions in large-scale cases. The obtained results showed that the proposed branch-and-cut scheme is competitive with other state-of-the-art algorithms, and presents better performance when solving large-scale instances.

Keywords: Lagrangian relaxation; Relax-and-cut; Volume Algorithm; Multicommodity network design; Branch-and-cut (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-06303-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:annopr:v:351:y:2025:i:1:d:10.1007_s10479-024-06303-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-06303-y

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().