Constrained shortest path tour problem: branch-and-price algorithm

DOI10.1016/j.cor.2022.105819OpenAlexW4224237592MaRDI QIDQ2147106

Jérémie Leguay, Youcef Magnouche, Corentin Juvigny, Sébastien Martin

Publication date: 22 June 2022

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2022.105819

zbMATH Keywords

complexitycolumn generationDantzig-Wolfe decompositioninteger linear programmingintegral polytopeshortest path tour

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Related Items

A generalized shortest path tour problem with time windows

Uses Software

• CPLEX
• LEMON

Cites Work

• Unnamed Item
• Integer programming formulations for the elementary shortest path problem
• The constrained shortest path tour problem
• A heuristic manipulation technique for the sequential ordering problem
• The edge Hamiltonian path problem is NP-complete
• A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships
• Shortest path tour problem with time windows
• Solving the shortest path tour problem
• Decomposition Principle for Linear Programs
• An efficient exact approach for the constrained shortest path tour problem
• Constrained shortest path tour problem: models, valid inequalities, and Lagrangian heuristics