Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/246430 
Year of Publication: 
2020
Citation: 
[Journal:] Operations Research Perspectives [ISSN:] 2214-7160 [Volume:] 7 [Publisher:] Elsevier [Place:] Amsterdam [Year:] 2020 [Pages:] 1-6
Publisher: 
Elsevier, Amsterdam
Abstract: 
Not all problem instances in combinatorial optimization are equally hard. One famous study "Where the Really Hard Problems Are" shows that for three decision problems and one optimization problem, computational costs can vary dramatically for equally sized instances. Moreover, runtimes could be predicted from an "order parameter", which is a property of the problem instance itself. For the only optimization problem in the study, the asymmetric traveling salesman problem (ATSP), the proposed order parameter was the standard deviation in the probability distribution used for generating distance matrices. For greater standard deviations, most randomly generated instances turned out to be easily solved to optimality, whereas smaller standard deviations produced harder instances. In this replication study, we show these findings can be contested. Most likely, the difference in instance hardness stems from a roundoff error that was possibly overlooked. This gives rise to a sudden emergence of minimum-cost tours, a feature that is readily exploited by most branch and bound algorithms. This new contradiction renders the earlier proposed order parameter unsuitable and changes the perspective on the fundamentals of ATSP instance hardness for this kind of algorithm.
Subjects: 
ATSP
Branch and bound
Instance hardness
Replication
TSP
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.