A Branch-and-Price Algorithm for Solving the Hamiltonian p-Median Problem

References

• Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Inc., Upper Saddle River, NJ).Google Scholar
• Balas E, Padberg MW (1976) Set partitioning: A survey. SIAM Rev. 18(4):710–760.Crossref, Google Scholar
• Branco IM, Coelho JD (1990) The Hamiltonian p-median problem. Eur. J. Oper. Res. 47(1):86–95.Crossref, Google Scholar
• Cerdeira J (1986) The Hamiltonian k-median problem for any given k is NP-complete. Technical Report 14/86, Centro de Estatistica e Aplicacões, Universidade de Lisboa.Google Scholar
• Cunningham WH, Wang Y (2000) Restricted 2-factor polytopes. Math. Programming 87(1):87–111.Crossref, Google Scholar
• Desrochers M, Soumis F (1989) A column generation approach to the urban transit crew scheduling problem. Transportation Sci. 23(1):1–13.Link, Google Scholar
• Edmonds J (1965) Maximum matching and a polyhedron with 0, 1 vertices. J. Res. National Bureau Standards 69B(1):125–130.Crossref, Google Scholar
• Glaab H, Pott A (2000) The Hamiltonian p-median problem. Electronic J. Combinatorics 7(1):R–42.Crossref, Google Scholar
• Gollowitzer S, Gouveia L, Laporte G, Pereira DL, Wojciechowski A (2014) A comparison of several models for the Hamiltonian p-median problem. Networks 63(4):350–363.Crossref, Google Scholar
• Hupp L, Liers F (2013) A polyhedral study of the Hamiltonian p-median problem. Electronic Notes Discrete Math. 41:213–220.Crossref, Google Scholar
• Kolmogorov I (2009) Blossom V: A new implementation of a minimum cost perfect matching algorithm. Math. Programming Comput. 1(1):43–67.Crossref, Google Scholar
• Laporte G, Nobert Y, Pelletier P (1983) Hamiltonian location problems. Eur. J. Oper. Res. 12(1):82–89.Crossref, Google Scholar
• Ryan DM, Foster BA (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling (North-Holland, Amsterdam), 269–280.Google Scholar
• Üster H, Kumar SKS (2008) Algorithms for the design of network topologies with balanced disjoint rings. J. Heuristics 16(1):37–63.Crossref, Google Scholar
• Williamson M, Eirinakis P, Subramani K (2016) Fast algorithms for the undirected negative cost cycle detection problem. Algorithmica 74(1):270–325.Crossref, Google Scholar