Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm

Daniil Khachai, Ruslan Sadykov, Olga Battaia and Michael Khachay

European Journal of Operational Research, 2023, vol. 309, issue 2, 488-505

Abstract: The 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’ π- and σ-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.

Keywords: Travelling salesman; Integer programming; Branch-and-cut algorithm; Facet-inducing inequalities; Polyhedral structure (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723000735
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:309:y:2023:i:2:p:488-505

DOI: 10.1016/j.ejor.2023.01.039

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().