LOWER BOUNDS FOR THE SYMMETRIC TRAVELING SALESMAN PROBLEM FROM LAGRANGEAN RELAXATIONS

被引：2
|
作者：
SMITH, THC [1 ]
MEYER, TWS [1 ]
THOMPSON, GL [1 ]
机构：
[1] CARNEGIE MELLON UNIV,PITTSBURGH,PA 15213
来源：
DISCRETE APPLIED MATHEMATICS | 1990年 / 26卷 / 2-3期
关键词：
Lagrangean relaxation; matching; Travelling salesman problem;
D O I：
10.1016/0166-218X(90)90101-H
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The paper presents new lower bounding and reduction procedures for the symmetric travelling salesman problem. Lower bounds are obtained through the solution of the linear program corresponding to the 2-matching relaxation and improved through a restricted Lagrangean 2-matching approach. A computational comparison of the new bounds with bounds obtained from the well-known Lagrangean 1-tree relaxation is also presented. © 1990.
引用
收藏
页码：209 / 217
页数：9
相关论文
共 50 条
  • [1] NEW LOWER BOUNDS FOR THE SYMMETRIC TRAVELING SALESMAN PROBLEM
    CARPANETO, G
    FISCHETTI, M
    TOTH, P
    MATHEMATICAL PROGRAMMING, 1989, 45 (02) : 233 - 254
  • [2] A comparison of lower bounds for the symmetric circulant traveling salesman problem
    de Klerk, Etienne
    Dobre, Cristian
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (16) : 1815 - 1826
  • [3] IMPROVED LOWER BOUNDS TO THE TRAVELING SALESMAN PROBLEM
    DATRI, G
    RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH, 1978, 12 (04): : 369 - 382
  • [4] Improved lower bounds on the approximability of the Traveling Salesman Problem
    Böckenhauer, HJ
    Seibert, S
    RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 2000, 34 (03): : 213 - 255
  • [5] A RESTRICTED LAGRANGEAN APPROACH TO THE TRAVELING SALESMAN PROBLEM
    BALAS, E
    CHRISTOFIDES, N
    MATHEMATICAL PROGRAMMING, 1981, 21 (01) : 19 - 46
  • [6] Continuous relaxations for the traveling salesman problem
    Sahai, Tuhin
    Ziessler, Adrian
    Klus, Stefan
    Dellnitz, Michael
    NONLINEAR DYNAMICS, 2019, 97 (04) : 2003 - 2022
  • [7] Continuous relaxations for the traveling salesman problem
    Tuhin Sahai
    Adrian Ziessler
    Stefan Klus
    Michael Dellnitz
    Nonlinear Dynamics, 2019, 97 : 2003 - 2022
  • [8] Tight lower bounds for the Traveling Salesman Problem with draft limits
    Balma, Ali
    Mrad, Mehdi
    Ladhari, Talel
    COMPUTERS & OPERATIONS RESEARCH, 2023, 154
  • [9] Combinatorial lower bounds for the Generalized Traveling Salesman Problem with Neighborhoods
    Deckerova, Jindriska
    Vana, Petr
    Faigl, Jan
    EXPERT SYSTEMS WITH APPLICATIONS, 2024, 258
  • [10] FICTITIOUS UPPER-BOUNDS IN AN ALGORITHM FOR THE SYMMETRIC TRAVELING SALESMAN PROBLEM
    VOLGENANT, T
    JONKER, R
    COMPUTERS & OPERATIONS RESEARCH, 1990, 17 (01) : 113 - 117
12345