Formulations and branch-and-cut algorithms for cycle covers with up to p cycles

Francisco Canas and Luís Gouveia

European Journal of Operational Research, 2025, vol. 327, issue 1, 42-57

Abstract: Given a positive integer p and a weighted undirected graph G=(V,E), we study a problem in which the objective is to find a minimum weight set of up to p elementary cycles partitioning the vertices of G. We study several exponentially sized formulations including (i) edge variables only; (ii) edge and depot variables only; (iii) edge, depot and node-depot assignment (NDA) variables only; (iv) edge, depot, NDA and edge-depot assignment (EDA) variables. New flow formulations are also introduced, and relations between all the formulations are established. Branch-and-cut algorithms based on many of these formulations are proposed, and computational experiments are conducted to compare the performance of the different algorithms. The computational testing reveals that some of the formulations including edge, depot and NDA or EDA variables produce the best initial lower bounds and that the best computational times are obtained with the algorithms based on formulations including edge and depot variables only. The best performing algorithm (in terms of computational times) is capable of solving several instances with up to 442 nodes for different values of p.

Keywords: Combinatorial optimization; Integer linear programming; Location-routing; Branch-and-cut; Multicommodity flow (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725003467
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:327:y:2025:i:1:p:42-57

DOI: 10.1016/j.ejor.2025.04.047

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 ().