Skip to Main content Skip to Navigation
Journal articles

Matheuristics based on iterative linear programming and slope scaling for multicommodity capacitated fixed charge network design

Abstract : We present new matheuristics for the multicommodity capacitated fixed-charge network design problem (MCND). The matheuristics are based on combining iterative linear programming (ILP) methods and slope scaling (SS) heuristics. Each iteration alternates between solving a linear program obtained by adding pseudo-cuts and a restricted mixed-integer programming (MIP) model. The SS heuristic is used as a warm start to a state-of-the-art generic method that solves the restricted MIP model. The resulting ILP/SS matheuristics are compared against state-of-the-art heuristics for the MCND on a set of large-scale difficult instances. The computational results show that the approach is competitive: when performed for a time limit of 1 hour, it finds more best solutions than any other heuristic, using comparable running times; when performed for a time limit of 5 hours, it identifies an optimal solution for each instance for which an optimal solution is known and it is able to find new best solutions for some very hard instances.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03400567
Contributor : Kathleen Torck Connect in order to contact the contributor
Submitted on : Monday, October 25, 2021 - 9:45:08 AM
Last modification on : Wednesday, November 3, 2021 - 5:22:08 AM

Identifiers

Collections

Citation

Bernard Gendron, Said Hanafi, Raca Todosijević. Matheuristics based on iterative linear programming and slope scaling for multicommodity capacitated fixed charge network design. European Journal of Operational Research, Elsevier, 2018, 268 (1), pp.70-81. ⟨10.1016/j.ejor.2018.01.022⟩. ⟨hal-03400567⟩

Share

Metrics

Record views

4