Semidefinite Programming Methods for the Symmetric Traveling Salesman Problem

Semidefinite Programming Methods for the Symmetric Traveling Salesman Problem
复制标题

对称旅行商问题的半定规划方法

DOI：
--
复制
发表时间：
1999
期刊：
Conference on Integer Programming and Combinatorial Optimization
影响因子：
--
通讯作者：
V. Kovacevic
V. Kovacevic
中科院分区：
--
文献类型：
--
作者：
D. Cvetkovic;M. Cangalovic;V. Kovacevic

文献摘要

被引文献

相似文献

本文将对称旅行商问题建模为离散半定规划问题。定义了STSP模型的一类半定松弛，并提出了基于这类松弛的分枝定界方法的两种变形。报告了随机生成问题的初步数值实验结果。
In this paper the symmetric traveling salesman problem (STSP) is modeled as a problem of discrete semidefinite programming. A class of semidefinite relaxations of STSP model is defined and two variants of a branch-and-bound technique based on this class of relaxations are proposed. The results of preliminary numerical experiments with randomly generated problems are reported.