  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.
