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

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.