A New Technique to Compare Algorithms for Bi-criteria Combinatorial Optimization Problems

The recent interest in multiobjective combinatorial optimization problems resulted in the development of several exact algorithms and metaheuristics for the a posteriori solution of these problems. However, there are as yet no commonly used, reliable methods to compare approximations generated by these algorithms. In this paper, we introduce a new measure for this purpose: Integrated Convex Preference (ICP). We compare the performance of ICP with that of the existing measures using approximations generated by two different genetic algoithms for an NP-hard, bi-criteria parallel machine scheduling problem. Our results show that our measure outperforms existing measures previously used in the literature, and that ICP can handle approximate solution sets with diverse geometric features effectively.