Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming

Andrei V. Nikolaev () and Egor V. Klimov ()
Additional contact information
Andrei V. Nikolaev: P.G. Demidov Yaroslavl State University
Egor V. Klimov: P.G. Demidov Yaroslavl State University

Journal of Combinatorial Optimization, 2024, vol. 47, issue 5, No 19, 31 pages

Abstract: Abstract A Hamiltonian decomposition of a regular graph is a partition of its edge set into Hamiltonian cycles. We consider the second Hamiltonian decomposition problem: for a 4-regular multigraph, find 2 edge-disjoint Hamiltonian cycles different from the given ones. This problem arises in polyhedral combinatorics as a sufficient condition for non-adjacency in the 1-skeleton of the traveling salesperson polytope. We introduce two integer linear programming models for the problem based on the classical Dantzig-Fulkerson-Johnson and Miller-Tucker-Zemlin formulations for the traveling salesperson problem. To enhance the performance on feasible problems, we supplement the algorithm with a variable neighborhood descent heuristic w.r.t. two neighborhood structures and a chain edge fixing procedure. Based on the computational experiments, the Dantzig-Fulkerson-Johnson formulation showed the best results on directed multigraphs, while on undirected multigraphs, the variable neighborhood descent heuristic was especially effective.

Keywords: Hamiltonian decomposition; Traveling salesperson polytope; 1-skeleton; Integer linear programming; Dantzig-Fulkerson-Johnson formulation; Miller-Tucker-Zemlin formulation; Subtour elimination constraints; Edge-disjoint 2-factors; Local search; Variable neighborhood descent; Chain edge fixing; 05C85; 90C10; 90C57; 90C59; 52B05 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01184-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:47:y:2024:i:5:d:10.1007_s10878-024-01184-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01184-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().