Efficient matheuristics for multicommodity capacitated network design

Bernard Gendron , Said Hanafi (1, 2) , Raca Todosijević (1)

1 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201
2 INSA Hauts-De-France - INSA Institut National des Sciences Appliquées Hauts-de-France

We present 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-theart heuristics for the MCND on a set of large-scale difficult instances.

Domaines: Informatique [cs]

Bernard Gendron, Said Hanafi, Raca Todosijević. Efficient matheuristics for multicommodity capacitated network design. Journées de l’Optimisation / Optimization Days, 2019, Montréal, Canada. ⟨hal-03472597⟩