Eliminating objective functions and warm starting algorithms using projections in multi-objective optimization

Many real world optimization problems have more than a single objective. In order to solve these multi-objective problems exactly, usually one has to solve many single objective problems to obtain all the efficient solutions and nondominated points. As the size of the nondominated set increases, so does the computational effort required to solve multi-objective problems. One way to mitigate this and lessen the computational burden is to reduce the number of objective functions in a given problem. When there are redundant objective functions, this reduction is obvious and the only requirement then is to detect the redundant objectives. Otherwise, any reduction will result in information loss in the form of missing some nondominated points. In other words, the set of points that will be obtained from the reduced problem is going to be a representation, which is a subset of the nondominated set of the original problem. In this thesis, we develop a projection based metric in order to determine which objective to remove with the goal of keeping the information loss to a minimum. We base our approach on the characterization of a redundant objective for the linear case. We then assess the level of redundancy for an objective using its similarity to its projection. The performance of this method is evaluated on many sets of test problems from the literature as well as on generated correlated instances and the information loss is quantified using quality metrics. Our method demonstrates strong performance across the majority of tested problems. Moreover, we show that the representation we obtain after solving the reduced problem can be used to warm start the exact solution process of the original multi-objective problem. This way parts of the search region that do not contain any nondominated points can be eliminated and the number of objects that are needed to be maintained throughout the solution process can be reduced. Our preliminary experiments indicate that our initialization method is highly effective in achieving these reductions.