Multi-Objective Mixed-Integer Nonconvex Optimization : Adaptive Relaxation-Refinement Schemes Guided In The Image Space

Abstract

Multi-objective mixed-integer nonlinear optimization problems frequently arise in real-world applications due to their ability to handle conflicting objectives. Examples can be found in various domains, such as healthcare management, energy network planning, or production planning. Since mathematical models of such applications often result in large and complex optimization problems, efficient algorithms to solve them are necessary. This thesis proposes a novel deterministic framework for solving multi-objective mixed-integer nonlinear optimization problems. The framework is based on the idea of iteratively refining piecewise linear outer approximations of the feasible set, a well-known technique from single-objective optimization, which is extended to the multi-objective setting for the first time. To guide the refinement process, the framework leverages image space information. This enables individualization of the outer approximations to the needs of the different relevant regions of the image space. By selecting suitable relaxation and refinement techniques, the framework can be turned into practical algorithms. This thesis presents various options for both, proves correct and finite termination for all resulting variants and provides numerical tests evidencing their applicability. The proposed framework is related to (box-)enclosure algorithms, a relatively new but increasingly prominent class of algorithms for computing a coverage of the nondominated set. While the framework presented here computes a similar coverage, the output does not strictly belong to this category. To address this, a novel theoretical concept is introduced: pseudo enclosures of the nondominated set, which allows to rigorously describe the output of the proposed algorithms mathematically.