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

DOI10.1016/J.COR.2022.105819MaRDI QIDQ2147106zbMATH OpenOpenAlexFDO

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

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

complexityinteger linear programmingcolumn generationDantzig-Wolfe decompositionintegral polytopeshortest path tour

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Recommendations

• The constrained shortest path tour problem
• An efficient exact approach for the constrained shortest path tour problem
• Solving the shortest path tour problem
• Complexity analysis and optimization of the shortest path tour problem
• On an exact method for the constrained shortest path problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships
• A heuristic manipulation technique for the sequential ordering problem
• An efficient exact approach for the constrained shortest path tour problem
• Constrained shortest path tour problem: models, valid inequalities, and Lagrangian heuristics
• Decomposition Principle for Linear Programs
• Integer programming formulations for the elementary shortest path problem
• Shortest path tour problem with time windows
• Solving the shortest path tour problem
• The constrained shortest path tour problem
• The edge Hamiltonian path problem is NP-complete

Cited in

(10)

• Reliable production process design problem: compact MILP model and ALNS-based primal heuristic
• scientific article; zbMATH DE number 1445588 (Why is no real title available?)
• The constrained shortest path tour problem
• A generalized shortest path tour problem with time windows
• Solving the shortest path tour problem
• The constrained forward shortest path tour problem: Mathematical modeling and GRASP approximate solutions
• Complexity analysis and optimization of the shortest path tour problem
• Implementation of a three-stage approach for the dynamic resource-constrained shortest-path sub-problem in branch-and-price
• An efficient exact approach for the constrained shortest path tour problem
• Fault-tolerant families of production plans: mathematical model, computational complexity, and branch-and-bound algorithms

Describes a project that uses

Uses Software

• CPLEX
• LEMON

This page was built for publication: Constrained shortest path tour problem: branch-and-price algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2147106)