论文标题
解决签名的罗马统治并以精确和启发式方法签署的罗马统治问题
Solving the signed Roman domination and signed total Roman domination problems with exact and heuristic methods
论文作者
论文摘要
在本文中，我们处理了签名的罗马统治，并签署了罗马统治问题。对于每个问题，我们提出两个整数线性编程（ILP）公式，约束编程（CP）公式和可变邻域搜索（VNS）方法。我们介绍了ILP公式的正确性和一项多面体研究的证据，其中我们表明两个模型弛豫的多面子是等效的。 VNS使用专门设计的惩罚功能，允许出现略微不可行的解决方案。从长远来看，这些解决方案的接受将整体搜索过程引导到有前途的领域。 所有提出的方法均可在大量实例上进行测试。实验结果表明，所有这些结果都达到了大多数中小型实例的最佳解决方案。事实证明，这两种ILP模型都比其他两种方法更成功。
In this paper we deal with the signed Roman domination and signed total Roman domination problems. For each problem we propose two integer linear programming (ILP) formulations, the constraint programming (CP) formulation and variable neighborhood search (VNS) method. We present proofs for the correctness of the ILP formulations and a polyhedral study in which we show that the polyhedrons of the two model relaxations are equivalent. VNS uses specifically designed penalty function that allows the appearance of slightly infeasible solutions. The acceptance of these solutions directs the overall search process to the promising areas in the long run. All proposed approaches are tested on the large number of instances. Experimental results indicate that all of them reach optimal solutions for the most of small and middle scale instances. Both ILP models have proven to be more successful than the other two methods.
