Characterising the rankings produced by combinatorial optimisation problems and finding their intersections.

Abstract

[EN] The aim of this paper is to introduce the concept of intersection between combinatorial optimisation problems. We take into account that most algorithms, in their machinery, do not consider the exact objective function values of the solutions, but only a comparison between them. In this sense, if the solutions of an instance of a combinatorial optimisation problem are sorted into their objective function values, we can see the instances as (partial) rankings of the solutions of the search space. Working with specific problems, particularly, the linear ordering problem and the symmetric and asymmetric traveling salesman problem, we show that they can not generate the whole set of (partial) rankings of the solutions of the search space, but just a subset. First, we characterise the set of (partial) rankings each problem can generate. Secondly, we study the intersections between these problems: those rankings which can be generated by both the linear ordering problem and the symmetric/asymmetric traveling salesman problem, respectively. The fact of finding large intersections between problems can be useful in order to transfer heuristics from one problem to another, or to define heuristics that can be useful for more than one problem.