论文标题
通过整数线性编程找到第二个对4型多编码的哈密顿分解
Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
论文作者
论文摘要
普通图的哈密顿分解是其边缘设置为哈密顿周期的分区。我们考虑了第二个汉密尔顿分解问题：对于4个规范的多编码，发现2个边缘 - 偶发性的哈密顿周期与给定的周期不同。这个问题在多面体组合物质中引起，作为在旅行销售人员多层的1个骨骼中非j骨的足够条件。我们根据经典的Dantzig-Fulkerson-Johnson和Miller-Tucker-Zemlin配方为问题引入了两个整数线性编程模型，以解决旅行销售人员问题。为了提高可行问题的性能，我们用可变的邻里下降启发式W.R.T.补充算法。两个邻里结构和一个链边固定程序。基于计算实验，Dantzig-Fulkerson-Johnson的配方在有向的多编码方面显示出最佳的结果，而在无方向的多编码上，可变的邻域下降启发式剂尤其有效。
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.
