CHESS - Changing Horizon Efficient Set Search: a simple principle for multiobjective optimization

This paper presents a new concept for generating approximations to the non-dominated set in multiobjective optimization problems. The approximation set A is constructed by solving several single-objective minimization problems in which a particular function D(A, z) is minimized. A new algorithm to calculate D(A, z) is proposed. No general approach is available to solve the one-dimensional optimization problems, but metaheuristics based on local search procedures are used instead. Tests with multiobjective combinatorial problems whose non-dominated sets are known confirm that CHESS can be used to approximate the non-dominated set. Straightforward parallelization of the CHESS approach is illustrated with examples. The algorithm to calculate D(A, z) can be used in any other applications that need to determine Tchebycheff distances between a point and a dominant-free set.