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

DOI10.1007/S10589-005-4800-2zbMATH Open1125.90040OpenAlexW2015900974MaRDI QIDQ2490367FDOQ2490367

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

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

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)

Cites Work

• Title not available (Why is that?)
• A multi-modal approach to the location of a rapid transit line
• The Median Shortest Path Problem: A Multiobjective Approach to Analyze Cost vs. Accessibility in the Design of Transportation Networks
• Hamiltonian path and symmetric travelling salesman polytopes
• The optimal location of a path or tree in a tree network
• On the \(p\)-median polytope
• A linear algorithm for a core of a tree
• Logical reduction tests for the p-problem
• A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Technical Note—A Note on Zero-One Programming
• 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

Cited In (11)

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

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)