Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929414459097088 |
|---|---|
| author | Nikolaev, Andrei V. Klimov, Egor V. |
| author_facet | Nikolaev, Andrei V. Klimov, Egor V. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_03846 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming Nikolaev, Andrei V. Klimov, Egor V. Optimization and Control Combinatorics 05C85, 90C10, 90C57, 90C59, 52B05 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. |
| title | Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming |
| topic | Optimization and Control Combinatorics 05C85, 90C10, 90C57, 90C59, 52B05 |
| url | https://arxiv.org/abs/2201.03846 |