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

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 travelling 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 travelling salesperson problem. To enhance the performance on feasible problems, we supplement the algorithm with a variable neighbourhood descent heuristic w.r.t. two neighbourhood 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 neighbourhood descent heuristic was especially effective.

References in corpus (5)

• Generating subtour elimination constraints for the TSP from pure integer solutions
• On the skeleton of the pyramidal tours polytope
• Simulated annealing approach to verify vertex adjacencies in the traveling salesperson polytope
• On vertex adjacencies in the polytope of pyramidal tours with step-backs
• An iterative ILP approach for constructing a Hamiltonian decomposition of a regular multigraph