In this paper, we introduce, study and analyze several classes of compact formulations for the symmetric Hamiltonian -median problem (HMP). Given a positive integer and a weighted complete undirected graph with weights on the edges, the HMP on is to find a minimum weight set of elementary cycles partitioning the vertices of . The advantage of developing compact formulations is that they can be readily used in combination with off-the-shelf optimization software, unlike other types of formulations possibly involving the use of exponentially sized sets of variables or constraints. The main part of the paper focuses on compact formulations for eliminating solutions with less than cycles. Such formulations are less well known and studied than formulations which prevent solutions with more than cycles. The proposed formulations are based on a common motivation, that is, the formulations contain variables that assign labels to nodes, and prevent less than cycles by stating that different depots must have different labels and that nodes in the same cycle must have the same label. We introduce and study aggregated formulations (which consider integer variables that represent the label of the node) and disaggregated formulations (which consider binary variables that assign each node to a given label). The aggregated models are new. The disaggregated formulations are not, although in all of them new enhancements have been included to make them more competitive with the aggregated models. The two main conclusions of this study are: (i) in the context of compact formulations, it is worth looking at the models with integer node variables, which have a smaller size. Despite their weaker LP relaxation bounds, the fewer variables and constraints lead to faster integer resolution, especially when solving instances with more than 50 nodes; (ii) the best of our compact models exhibit a performance that, overall, is comparable to that of the best methods known for the HMP (including branch-and-cut algorithms), solving to optimality instances with up to 226 nodes within 1 h. This corroborates our message that the knowledge of the inequalities for preventing less than cycles is much less well understood.

Node based compact formulations for the Hamiltonian p‐median problem / M. Barbato, F. Canas, L. Gouveia, P. Pesneau. - In: NETWORKS. - ISSN 0028-3045. - (2023), pp. 1-35. [Epub ahead of print] [10.1002/net.22163]

Node based compact formulations for the Hamiltonian p‐median problem

M. Barbato
Primo
;
2023

Abstract

In this paper, we introduce, study and analyze several classes of compact formulations for the symmetric Hamiltonian -median problem (HMP). Given a positive integer and a weighted complete undirected graph with weights on the edges, the HMP on is to find a minimum weight set of elementary cycles partitioning the vertices of . The advantage of developing compact formulations is that they can be readily used in combination with off-the-shelf optimization software, unlike other types of formulations possibly involving the use of exponentially sized sets of variables or constraints. The main part of the paper focuses on compact formulations for eliminating solutions with less than cycles. Such formulations are less well known and studied than formulations which prevent solutions with more than cycles. The proposed formulations are based on a common motivation, that is, the formulations contain variables that assign labels to nodes, and prevent less than cycles by stating that different depots must have different labels and that nodes in the same cycle must have the same label. We introduce and study aggregated formulations (which consider integer variables that represent the label of the node) and disaggregated formulations (which consider binary variables that assign each node to a given label). The aggregated models are new. The disaggregated formulations are not, although in all of them new enhancements have been included to make them more competitive with the aggregated models. The two main conclusions of this study are: (i) in the context of compact formulations, it is worth looking at the models with integer node variables, which have a smaller size. Despite their weaker LP relaxation bounds, the fewer variables and constraints lead to faster integer resolution, especially when solving instances with more than 50 nodes; (ii) the best of our compact models exhibit a performance that, overall, is comparable to that of the best methods known for the HMP (including branch-and-cut algorithms), solving to optimality instances with up to 226 nodes within 1 h. This corroborates our message that the knowledge of the inequalities for preventing less than cycles is much less well understood.
combinatorial optimization; Hamiltonian p-median problem; integer linear programming; location routing; polyhedral theory; valid inequalities;
Settore MAT/09 - Ricerca Operativa
2023
9-giu-2023
Article (author)
File in questo prodotto:
File Dimensione Formato  
main.pdf

embargo fino al 09/06/2024

Descrizione: Accepted version
Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 597.38 kB
Formato Adobe PDF
597.38 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
14_Node based compact formulations for the Hamiltonian.pdf

accesso riservato

Descrizione: Publisher's version
Tipologia: Publisher's version/PDF
Dimensione 2.23 MB
Formato Adobe PDF
2.23 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Preprint_Node based compact formulations for the Hamiltonian p-Median Problem.pdf

accesso aperto

Descrizione: preprint (1st submission)
Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 418.35 kB
Formato Adobe PDF
418.35 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/976029
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact