Parallelization In Multi-Objective Optimization Based On The Epsilon-Constraint Scalarization

Many real-world applications lead to complex problems that require the simultaneous optimization of several objective functions. However, these objective functions often conflict with each other. As a result, there is no single solution that is optimal for all objectives. One is instead interested in solutions for which no other solution exists that is strictly better in one objective and not worse in any other. Such solutions are called efficient solutions and the corresponding images are called nondominated. The goal of multi-objective optimization is to find the set of all nondominated images, the so-called nondominated set, or an approximation/representation of this set. A common approach to find nondominated images is to transform the multi-objective optimization problem into single-objective optimization problems. This strategy is called scalarization. Scalarization problems can be constructed, for example, by combining objectives via linear combinations or by converting some objectives into constraints. Such a scalarization problem can then be solved using conventional optimization methods. It is well-known that computing all nondominated images imposes a huge computational burden: Multi-objective optimization problems are in general intractable, i. e., the number of nondominated images or the size of an exact representation of the nondominated set is often exponential in the encoding. In addition, scalarization problems themselves are in generally hard to solve. One promising approach to deal with this huge computational challenge that is rarely considered when designing algorithms for multi-objective optimization problems is to make better use of modern hardware via parallel computing. Modern processors and handheld devices are designed to have processors with multiple cores that are capable of performing complex operations simultaneously. However, the usage of such multi-core technology requires explicit redesign of existing and the development of new algorithms. In this thesis, we analyze the structure of the parameter set associated with the lexicographic epsilon-constraint scalarization for multi-objective optimization problems. We introduce a new order on the nondominated images and a new order on a finite set of parameters. These orders lay the foundation for a new algorithm, the Parallel Epsilon Algorithm (PEA), for computing all nondominated images of multi-objective optimization problems with finite nondominated set. PEA is the first algorithm of its kind. Unlike existing algorithms it does not require any complex data structures and is capable of distributing the computational load associated with computing the nondominated set to independent tasks working in parallel. Therefore, these tasks can be easily allocated to different threads and the only communication exchanged is task distribution. In addition, the number of scalarization problems PEA solves is independent of the number of threads in use and equals the best known bound on the number of scalarization problems which sequential algorithms need to solve. When using multiple threads, PEA is significantly faster than existing state-of-the-art sequential and parallel algorithms and, as our numerical testing indicates, achieves an almost linear speedup in the number of threads.