A branch-and-cut algorithm for the median-path problem

DOI10.1007/s10589-005-4800-2zbMath1125.90040OpenAlexW2015900974MaRDI QIDQ2490367

Igor' Leonidovich Vasilyev, Maurizio Boccia, Pasquale Avella, Aantonio Sforza

Publication date: 2 May 2006

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-005-4800-2

zbMATH Keywords

branch-and-cutmedian-pathpath-location

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (8)

Rapid transit network design for optimal cost and origin-destination demand capture ⋮ The \(p\)-median problem with upgrading of transportation costs and minimum travel time allocation ⋮ Finding a core of a tree with pos/neg weight ⋮ A new MILP formulation for the flying sidekick traveling salesman problem ⋮ Finding an optimal core on a tree network with M/G/c/c state-dependent queues ⋮ Locating median paths on connected outerplanar graphs ⋮ A branch and cut heuristic for a runway scheduling problem ⋮ Unnamed Item

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Logical reduction tests for the p-problem
• A multi-modal approach to the location of a rapid transit line
• Hamiltonian path and symmetric travelling salesman polytopes
• A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
• The Median Shortest Path Problem: A Multiobjective Approach to Analyze Cost vs. Accessibility in the Design of Transportation Networks
• On locating path- or tree-shaped facilities on networks
• Optimal location of a path or tree on a network with cycles
• On finding the core of a tree with a specified length
• The optimal location of a path or tree in a tree network
• A linear algorithm for a core of a tree
• Technical Note—A Note on Zero-One Programming
• On the \(p\)-median polytope

This page was built for publication: A branch-and-cut algorithm for the median-path problem