Effective anytime algorithm for multiobjective combinatorial optimization problems
This work addresses the need for anytime algorithms that provide decision makers with diverse solution sets in multiobjective optimization, representing an incremental improvement over existing methods.
The authors tackled the problem of generating well-spread efficient solutions in multiobjective combinatorial optimization by proposing a new exact anytime algorithm, which outperformed state-of-the-art methods on most of 480 benchmark instances across four performance measures.
In multiobjective optimization, the result of an optimization algorithm is a set of efficient solutions from which the decision maker selects one. It is common that not all the efficient solutions can be computed in a short time and the search algorithm has to be stopped prematurely to analyze the solutions found so far. A set of efficient solutions that are well-spread in the objective space is preferred to provide the decision maker with a great variety of solutions. However, just a few exact algorithms in the literature exist with the ability to provide such a well-spread set of solutions at any moment: we call them anytime algorithms. We propose a new exact anytime algorithm for multiobjective combinatorial optimization combining three novel ideas to enhance the anytime behavior. We compare the proposed algorithm with those in the state-of-the-art for anytime multiobjective combinatorial optimization using a set of 480 instances from different well-known benchmarks and four different performance measures: the overall non-dominated vector generation ratio, the hypervolume, the general spread and the additive epsilon indicator. A comprehensive experimental study reveals that our proposal outperforms the previous algorithms in most of the instances.