Utopia in the solution of the Bucket Order Problem

In this paper we propose two improvements to the standard greedy algorithm usually considered to approach the bucket order problem: the Bucket Pivot Algorithm (BPA). The first improvement is based on the introduction of the Utopian Matrix, a matrix associated to a pair order matrix that represents the precedences in a collection of rankings. This idealization constitutes a superoptimal solution to the OBOP, which can be used as an extreme (sometimes feasible) best value. The second improvement is based on the use of several items as pivots to generate the bucket order, in contrast to BPA that only uses a single pivot. The set of items playing the role of decision-maker is dynamically created. We analyze separately the contribution of each improvement and also their joint effect. The statistical analysis of the experiments carried out shows that the combined use of both techniques is the best choice, showing a significant improvement in accuracy (17%) with respect to the original BPA and providing an important reduction in the variance of the output. Moreover, we provide decision rules to help the decision maker to select the right algorithm according to the problem instance.