Partial evaluation in Rank Aggregation Problems

Solving a problem by using metaheuristic algorithms requires the evaluation of a large number of potential solutions. This paper presents a theoretical and experimental study of the application of partial evaluation in the Rank Aggregation Problem (RAP). Partial evaluation just computes the part of the objective function that is affected by the modifications introduced by certain operators. In particular, we study some of the most common mutation/neighboring operators that are used in problems defined in the space of permutations, namely insertion, interchange and inversion. The theoretical study shows that the complexity of evaluating the original objective function can be reduced from quadratic to linear by using partial evaluation after applying insertion and interchange. Regarding the experimental study, it shows that for the insertion and interchange operators, the running time for the evaluation of the objective function may be reduced by a factor of 10 (30) for problems with more than 50 (100) items to be ranked. In the case of the inversion operator the amount of time saved time is not so large, although it is still significant.