Where the really hard problems aren’t

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.