Optimisation and Generalisation: Footprints in Instance Space

Abstract. The chief purpose of research in optimisation is to under-stand how to design (or choose) the most suitable algorithm for a given distribution of problem instances. Ideally, when an algorithm is devel-oped for specific problems, the boundaries of its performance should be clear, and we expect estimates of reasonably good performance within and (at least modestly) outside its ‘seen ’ instance distribution. How-ever, we show that these ideals are highly over-optimistic, and suggest that standard algorithm-choice scenarios will rarely lead to the best al-gorithm for individual instances in the space of interest. We do this by examining algorithm ‘footprints’, indicating how performance generalises in instance space. We find much evidence that typical ways of choosing the ‘best ’ algorithm, via tests over a distribution of instances, are seri-ously flawed. Also, understanding how footprints in instance spaces vary between algorithms and across instance space dimensions, may lead to a future platform for wiser algorithm-choice decisions.