Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(12)
Asymmetric Traveling Salesman Problem
Branch and Bound Algorithm
Branching Process
Computer Experiment
Depth First Search
Exact Solution
Large Scale
Mathematical Software
nphard problem
Optimal Solution
Search Algorithm
Branch and Bound
Related Publications
(1)
Some Basics on Tolerances
Subscribe
Academic
Publications
Tolerancebased Branch and Bound algorithms for the ATSP
Tolerancebased Branch and Bound algorithms for the ATSP,10.1016/j.ejor.2006.10.062,European Journal of Operational Research,Marcel Turkensteen,Diptes
Edit
Tolerancebased Branch and Bound algorithms for the ATSP
(
Citations: 5
)
BibTex

RIS

RefWorks
Download
Marcel Turkensteen
,
Diptesh Ghosh
,
Boris Goldengorin
,
Gerard Sierksma
The selection of entries to be included/excluded in
Branch and Bound
algorithms is usually done on the basis of cost values. We consider the class of
Depth First Search
algorithms, and we propose to use upper tolerances to guide the search for optimal solutions. In spite of the fact that it needs time to calculate tolerances, our computational experiments for Asymmetric
Traveling Salesman
Problems show that in most situations tolerancebased algorithms outperform costbased algorithms. The solution time reductions are mainly caused by the fact that the
branching process
becomes much more effective, so that optimal solutions are found in an earlier stage of the branching process. The use of tolerances also reveals why the widely used choice for branching on a smallest cycle in assignment solutions is on average the most effective one. Moreover, it turns out that tolerancebased DFS algorithms are better in solving difficult instances than the Best First
Search algorithm
from Carpaneto et al. (Carpaneto, G., Dell'Amico, M., Toth, P., 1995.
Exact solution
of largescale asymmetric
traveling salesman
problems. ACM Transactions on
Mathematical Software
21 (4), 394409). 2006 Elsevier B.V. All rights reserved.
Journal:
European Journal of Operational Research  EJOR
, vol. 189, no. 3, pp. 775788, 2008
DOI:
10.1016/j.ejor.2006.10.062
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.sciencedirect.com
)
(
www.informatik.unitrier.de
)
(
www.sciencedirect.com
)
(
wcmsneu1.urz.unihalle.de
)
(
linkinghub.elsevier.com
)
(
dx.doi.org
)
More »
Citation Context
(2)
...Goldengorin et al. [10,11] and Turkensteen et al. [
29
] have shown that the arcs with strictly positive upper tolerance in an optimal Assignment Problem (AP) solution are common arcs for all optimal AP solutions...
...Ghosh et al. [8], Goldengorin and J¨ager [9], Goldengorin et al. [12,13], and Turkensteen et al. [
29
] have applied the largest (bottleneck) upper tolerance for an arc in an optimal solution of the relaxed AP to guide a search of either a high quality heuristic or an exact algorithm for the Asymmetric TSP...
...In Section 2 we define the notion of tolerances [10,
29
]...
Dirk Richter
,
et al.
Improving the Efficiency of Helsgaun's LinKernighan Heuristic for the...
...Recently, Turkensteen, Ghosh et al.[
19
] reported a new branching rule in B&B algorithm which utilizes tolerances to indicate which arcs are preferred to save in the optimal ATSP tour...
Jie Bai
,
et al.
Collaborative Optimization under a Control Framework for ATSP
References
(23)
Branch and bound methods
(
Citations: 73
)
E. Balas
Published in 1985.
Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
(
Citations: 46
)
Giorgio Carpaneto
,
Paolo Toth
Journal:
Management Science  MANAGE SCI
, vol. 26, no. 7, pp. 736743, 1980
Exact solution of largescale, asymmetric traveling salesman problems
(
Citations: 47
)
Giorgio Carpaneto
,
Mauro Dell' Amico
,
Paolo Toth
Journal:
ACM Transactions on Mathematical Software  TOMS
, vol. 21, no. 4, pp. 394409, 1995
Algorithms and codes for dense assignment problems: the state of the art
(
Citations: 38
)
Mauro Dell' Amico
,
Paolo Toth
Journal:
Discrete Applied Mathematics  DAM
, vol. 100, no. 12, pp. 1748, 2000
Exact Methods for the Asymmetric Traveling Salesman Problem
(
Citations: 19
)
Matteo Fischetti
,
Andrea Lodi
,
Paolo Toth
Sort by:
Citations
(5)
A note on robustness tolerances for combinatorial optimization problems
(
Citations: 1
)
Marek Libura
Journal:
Information Processing Letters  IPL
, vol. 110, no. 16, pp. 725729, 2010
Equivalent instances of the simple plant location problem
(
Citations: 6
)
Bader F. AlBdaiwi
,
Boris Goldengorin
,
Gerard Sierksma
Journal:
Computers & Mathematics With Applications  COMPUT MATH APPL
, vol. 57, no. 5, pp. 812820, 2009
Improving the Efficiency of Helsgaun's LinKernighan Heuristic for the Symmetric TSP
(
Citations: 4
)
Dirk Richter
,
Boris Goldengorin
,
Gerold Jäger
,
Paul Molitor
Conference:
Combinatorial and Algorithmic Aspects of Networking  CAAN
, pp. 99111, 2007
Development of an Innovative Algorithm for the Traveling Salesman Problem (TSP)
Mahshid Abtahi Froushani
,
Rosnah Mohd. Yusuff
Collaborative Optimization under a Control Framework for ATSP
Jie Bai
,
Jun Zhu
,
GenKe Yang
,
ChangChun Pan