Afficher la notice abrégée

hal.structure.identifierDipartimento di Informatica
dc.contributor.authorBARBATO, Michele
hal.structure.identifierCentro de Investigação Operacional [CIO]
dc.contributor.authorCANAS, Francisco
hal.structure.identifierCentro de Investigação Operacional [CIO]
dc.contributor.authorGOUVEIA, Luís
hal.structure.identifierFormulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorPESNEAU, Pierre
dc.date2023-06-09
dc.date.accessioned2024-04-04T02:34:03Z
dc.date.available2024-04-04T02:34:03Z
dc.date.issued2023-06-09
dc.identifier.issn0028-3045
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/190527
dc.description.abstractEnIn this paper, we introduce, study and analyse several classes of compact formulations for the symmetric Hamiltonian p-Median Problem (HpMP). Given a positive integer p and a weighted complete undirected graph G = (V, E) with weights on the edges, the HpMP on G is to find a minimum weight set of p elementary cycles partitioning the vertices of G. 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 p cycles. Such formulations are less well known and studied than formulations which prevent solutions with more than p 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 p 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 HpMP (including branch-and-cut algorithms), solving to optimality instances with up to 226 nodes within 1 hour. This corroborates our message that the knowledge of the inequalities for preventing less than p cycles is much less well understood.
dc.language.isoen
dc.publisherWiley
dc.rights.urihttp://creativecommons.org/licenses/by/
dc.subject.enCombinatorial optimization
dc.subject.enInteger linear programming
dc.subject.enPolyhedral theory
dc.subject.enValid inequalities
dc.subject.enHamiltonian p-median problem
dc.subject.enLocation Routing
dc.title.enNode based compact formulations for the Hamiltonian p ‐median problem
dc.typeArticle de revue
dc.identifier.doi10.1002/net.22163
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalNetworks
bordeaux.page336-370
bordeaux.volume82
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue4
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-04124268
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-04124268v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Networks&rft.date=2023-06-09&rft.volume=82&rft.issue=4&rft.spage=336-370&rft.epage=336-370&rft.eissn=0028-3045&rft.issn=0028-3045&rft.au=BARBATO,%20Michele&CANAS,%20Francisco&GOUVEIA,%20Lu%C3%ADs&PESNEAU,%20Pierre&rft.genre=article


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée