An e-Approximation Two Phase Method with Three Objectives applied to Assignment Problem

The two phase method was first introduced by Ulungu and Teghem [1] to solve the bi- objective assignment problem. It is a general method that computes the set of nondominated points for bi-objective combinatorial optimization problems. Two independant extensions of this method have been proposed recently. Przybylski et al [2] have extended both phases of the method to the multi-objective case. The main ideas of this extension are a weight set decomposition for the first phase, and an appropriate formulation of the search area where nondominated points may exist for the second phase. This formulation has been designed for the computation of tight upper bounds and requires the computation of the nadir point. Pedersen et al [3] have proposed a modification of the two phase method for finding an ε- approximation of the set of nondominated points, that is a subset of solutions that contains, for each efficient solution, a solution that is at most at a factor (1 + ε) on all objective values. This has been enabled by using improved upper bounds that avoid the enumeration of ε- dominated solutions. However, the method they proposed is restricted to the bi-objective case. In this paper, we propose a combination of these two extensions, enabling the computation of an ε-approximation for a multi-objective combinatorial optimization problem. The perfor- mance of the proposed method is discussed in comparison with the exact method on various instances of three-objective assignment problem