Representation of the non-dominated set in biobjective discrete optimization

摘要

This paper introduces several algorithms for finding a representative subset of the non-dominated point set of a biobjective discrete optimization problem with respect to uniformity, coverage and the epsilon-indicator. We consider the representation problem itself as multiobjective, trying to find a good compromise between these quality measures. These representation problems are formulated as particular facility location problems with a special location structure, which allows for polynomial-time algorithms in the biobjective case based on the principles of dynamic programming and threshold approaches. In addition, we show that several multiobjective variants of these representation problems are also solvable in polynomial time. Computational results obtained by these approaches on a wide range of randomly generated point sets are presented and discussed. (C) 2015 Elsevier Ltd. All rights reserved.