A polyhedral study of the Hamiltonian p-median problem

Beitrag in einer Fachzeitschrift
(Originalarbeit)


Details zur Publikation

Autorinnen und Autoren: Hupp LM, Liers F
Zeitschrift: Electronic Notes in Discrete Mathematics
Verlag: Elsevier BV
Jahr der Veröffentlichung: 2013
Band: 41
Seitenbereich: 213-220
ISSN: 1571-0653


Abstract


Given an edge-weighted graph G= (V, E), the Hamiltonian p-median problem (HpMP) asks for determining p cycles in G whose total length is minimized such that each node is contained in exactly one cycle. As the travelling salesman problem (TSP) corresponds to the choice p= 1, the HpMP can be interpreted as a generalization of the TSP. In this paper, we study the polytope associated with the HpMP. To this end, we investigate several known classes of valid inequalities with respect to their facet inducing properties. Furthermore, we show that a subset of the well-known 2-matching inequalities from the TSP define facets of the Hamiltonian p-median polytope. © 2013 Elsevier B.V.



FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Hupp, Lena
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)
Liers-Bergmann, Frauke Prof. Dr.
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)


Zitierweisen

APA:
Hupp, L.M., & Liers, F. (2013). A polyhedral study of the Hamiltonian p-median problem. Electronic Notes in Discrete Mathematics, 41, 213-220. https://dx.doi.org/10.1016/j.endm.2013.05.095

MLA:
Hupp, Lena Maria, and Frauke Liers. "A polyhedral study of the Hamiltonian p-median problem." Electronic Notes in Discrete Mathematics 41 (2013): 213-220.

BibTeX: 

Zuletzt aktualisiert 2018-17-10 um 14:53