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

DOI10.1007/S10589-005-4800-2MaRDI QIDQ2490367zbMATH OpenOpenAlexFDO

Authors Pasquale Avella, Maurizio Boccia, Antonio Sforza, Igor' Leonidovich Vasilyev

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)

Recommendations

• On median-path and central-path problems
• Locating median cycles in networks
• Computational study of large-scale \(p\)-median problems
• On the \(p\)-median polytope
• A branch-and-cut method for the obnoxious \(p\)-median problem

Cites work

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

Cited in

(11)

• Finding an optimal core on a tree network with M/G/c/c state-dependent queues
• scientific article; zbMATH DE number 7306903 (Why is no real title available?)
• The \(p\)-median problem with upgrading of transportation costs and minimum travel time allocation
• Finding a core of a tree with pos/neg weight
• An efficient algorithm for solving the median problem on real road networks
• A new MILP formulation for the flying sidekick traveling salesman problem
• Locating median paths on connected outerplanar graphs
• On median-path and central-path problems
• Rapid transit network design for optimal cost and origin-destination demand capture
• A branch and cut heuristic for a runway scheduling problem
• Algorithms for path medi-centers of a tree

Describes a project that uses

Uses Software

• Algorithm 97

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

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