Afficher la notice abrégée

An Exact Approach for the Precedence Constrained Generalized Traveling Salesman Problem

hal.structure.identifierKedge Business School [Kedge BS]
hal.structure.identifierFormulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
dc.contributor.authorKHACHAI, Daniil
hal.structure.identifierKedge Business School [Kedge BS]
dc.contributor.authorBATTAÏA, Olga
hal.structure.identifierIvannikov Institute for System Programming of the RAS
dc.contributor.authorKHACHAY, Michael
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierFormulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
dc.contributor.authorSADYKOV, Ruslan
dc.date.accessioned2024-04-04T02:36:59Z
dc.date.available2024-04-04T02:36:59Z
dc.date.created2022-11-20
dc.date.issued2022-11-20
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/190768
dc.description.abstractEnThe Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) is an extension of two well-known combinatorial optimization problems --- the Generalized Traveling Salesman Problem (GTSP) and the Precedence Constrained Asymmetric Traveling Salesman Problem (PCATSP), whose path version is known as the Sequential Ordering Problem (SOP). Similarly to the classic GTSP, the goal of the PCGTSP, for a given input digraph and partition of its node set into clusters, is to find a minimum cost cyclic route (tour) visiting each cluster in a single node. In addition, as in the PCATSP, feasible tours are restricted to visit the clusters with respect to the given partial order. Unlike the GTSP and SOP, to the best of our knowledge, the PCGTSP still remain to be weakly studied both in terms of polyhedral theory and algorithms. In this paper, for the first time for the PCGTSP, we propose several families of valid inequalities, establish dimension of the PCGTS polytope and prove sufficient conditions ensuring that the extended Balas' $\pi$- and $\sigma$-inequalities become facet-inducing. Relying on these theoretical results and evolving the state-of-the-art algorithmic approaches for the PCATSP and SOP, we introduce a family of MILP-models (formulations) and several variants of the branch-and-cut algorithm for the PCGTSP. We prove their high performance in a competitive numerical evaluation against the public benchmark library PCGTSPLIB, a known adaptation of the classic SOPLIB to the problem in question.
dc.language.isoen
dc.title.enAn Exact Approach for the Precedence Constrained Generalized Traveling Salesman Problem
dc.typeDocument de travail - Pré-publication
dc.typePrepublication/Preprint
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
hal.identifierhal-03906983
hal.version1
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-03906983v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2022-11-20&rft.au=KHACHAI,%20Daniil&BATTA%C3%8FA,%20Olga&KHACHAY,%20Michael&SADYKOV,%20Ruslan&rft.genre=preprint&unknown


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