A Branch-And Approach for Computing the Minimum Number of Pairwise Comparisons in Multicriteria Selection Based on Convex Cones

Abstract

We study the multiple criteria selection problem (MCSP), where the aim is to identify the most preferred alternative among a set of known alternatives evaluated on multiple criteria. While several methods have been developed for MCSP, which utilize pairwise comparisons, it remains unknown how close these approaches are to the theoretical minimum number of pairwise comparisons required. To address this gap, we propose a computational framework that determines the theoretical lower bound on the number of pairwise comparisons required under the assumption that the DM's value function is known. Although this assumption is not realistic for real-world decision support, it is essential for establishing a rigorous performance standard against which algorithms can be evaluated. While this framework provides a basis for benchmarking interactive algorithms, its applicability is specific to pairwise comparison procedures that utilize convex cones. The benchmark is formulated as a large-scale integer programming problem and solved via a branch-and-price approach, where column generation is used to generate only the most promising convex cones. We further extend the model to incorporate transitivity, which can reduce the number of comparisons but increases computational effort. Extensive computational experiments are conducted across diverse problem instances. Beyond providing benchmark values, the results reveal structural patterns-such as when the optimal solution relies primarily on 2-point or 3-point cones, and when higher-level cones are required. These insights not only strengthen the role of the benchmark as a theoretical reference, but also offer practical guidance for designing more efficient algorithms for MCSP.