Please use this identifier to cite or link to this item: http://hdl.handle.net/11718/10188
Full metadata record
DC FieldValueLanguage
dc.contributor.authorTurkensteen, M.
dc.contributor.authorGhosh, Diptesh
dc.contributor.authorGoldengorin, B.
dc.contributor.authorSierksma, G.
dc.date.accessioned2010-11-09T05:23:18Z
dc.date.available2010-11-09T05:23:18Z
dc.date.copyright2008
dc.date.issued2008-11-09T05:23:18Z
dc.identifier.urihttp://hdl.handle.net/11718/10188
dc.descriptionEuropean Journal of Operational Research, 189, (2008), pp. 775 - 88en
dc.description.abstractThe 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 tolerance-based algorithms outperform cost-based 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 tolerance-based DFS algorithms are better in solving difficult instances than the Best First Search algorithm from Carpaneto et al.
dc.language.isoenen
dc.subjectTolerancesen
dc.subjectNP-hard Problemsen
dc.subjectBranch and Bounden
dc.titleTolerance-based branch and bound algorithms for the ATSPen
dc.typeArticleen
Appears in Collections:Journal Articles

Files in This Item:
File Description SizeFormat 
Tolerancebasedbranch.pdf
  Restricted Access
519.87 kBAdobe PDFView/Open Request a copy


Items in IIMA Institutional Repository are protected by copyright, with all rights reserved, unless otherwise indicated.