Solving Multi-Objective Mixed-Integer Nonlinear Optimization Problems
Multi-objective mixed-integer optimization problems arise in a wide variety of practical
applications. Examples include portfolio management, scheduling, and distribution
planning. Usually, these optimization problems are characterized by a large
number of variables and a relatively small number of objective functions.
This thesis presents three new deterministic approaches to approximate the nondominated
set of such optimization problems. Two of them operate almost entirely
in the criterion space. As a result, their computational performance is only weakly
affected by the large number of variables usually encountered in practical optimization
problems. While one of the approaches is a rather general algorithmic framework that
is not always applicable in practice, the other one is able to solve almost all kinds of
multi-objective mixed-integer convex optimization problems both theoretically and
practically. For multi-objective mixed-integer nonconvex optimization problems, a
third approach is presented. All three approaches are among the rst to solve multiobjective
mixed-integer optimization problems and provide guarantees on the quality
of the approximation that they compute. Numerical tests and evaluations of all of
them are also presented in this thesis.
All three approaches use the same concept, called enclosure, to approximate the nondominated
set. Its computation combines concepts from multi-objective integer optimization
and multi-objective continuous optimization. In addition, the approach for
multi-objective mixed-integer convex optimization problems explicitly explores the
mixed-integer structure of the optimization problem and combines techniques from
multi-objective continuous and single-objective mixed-integer optimization. It is the
first of its kind to simultaneously work with and make use of a multi-objective mixedinteger
linear relaxation and a multi-objective continuous convex decomposition of
the overall multi-objective mixed-integer convex optimization problem.
Dr. Julia Fligge-Niebling
Nonconvex and mixed integer multiobjective optimization with an application to decision uncertainty
Published on: 08. January 2020, Link to pdf
Multiobjective optimization problems commonly arise in different fields like economics or engineering. In general, when dealing with several conflicting objective functions, there is an infinite number of optimal solutions which cannot usually be determined analytically.
This thesis presents new branch-and-bound-based approaches for computing the globally optimal solutions of multiobjective optimization problems of various types. New algorithms are proposed for smooth multiobjective nonconvex optimization problems with convex constraints as well as for multiobjective mixed integer convex optimization problems. Both algorithms guarantee a certain accuracy of the computed solutions, and belong to the first deterministic algorithms within their class of optimization problems. Additionally, a new approach to compute a covering of the optimal solution set of multiobjective optimization problems with decision uncertainty is presented. The three new algorithms are tested numerically. The results are evaluated in this thesis as well.
The branch-and-bound based algorithms deal with box partitions and use selection rules, discarding tests and termination criteria. The discarding tests are the most important aspect, as they give criteria whether a box can be discarded as it does not contain any optimal solution. We present discarding tests which combine techniques from global single objective optimization with outer approximation techniques from multiobjective convex optimization and with the concept of local upper bounds from multiobjective combinatorial optimization. The new discarding tests aim to find appropriate lower bounds of subsets of the image set in order to compare them with known upper bounds numerically.
Dr. Jana Thomann
A trust region approach for multi-objective heterogeneous optimization
Published on: March 13, 2019, Link to pdf
This thesis presents a trust region approach for multi-objective optimization problems with heterogeneous objective functions. One of the objective functions is an expensive black-box function, not given analytically, but for example by a simulation. Computing function values is assumed to be time-consuming and derivative information is not available with reasonable effort. The other objective functions are assumed to be given analytically and function evaluations and derivatives are easily available with low numerical effort.
A basic algorithm for such optimization problems is presented. It is an iterative approach using local model functions and a search direction which is defined in the image space. The algorithm generates a sequence of iteration points. It is proved that the accumulation point of this sequence fulfills a necessary condition for local optimality. Moreover, several modifications of the basic algorithm are presented that make more use of the heterogeneity of the objective functions and partly produce several points as output.
Numerical results for the basic algorithm and several modifications are presented and discussed. They confirm the theoretical findings and show the usefulness of the approaches. Moreover, an application-motivated optimization problem from fluid dynamics is considered and the results are presented and interpreted according to the application.