Mixed integer nonlinear multiobjective optimization by outer approximations
Deutsche Forschungsgemeinschaft (DFG) - Project number 432218631
2020 - 2023
The aim of the planned research is to develop a deterministic algorithmic solution procedure for multiobjective mixed integer nonlinear optimization problems (MOMIPs). Thus, we aim to solve problems which have multiple objectives and integer and continuous variables at the same time. These types of optimization problems arise in many application fields such as location or production planning, chemical engineering, finance, and manufacturing. MOMIPs combine all the difficulties of both, multiobjective optimization and mixed integer nonlinear programming, which are among the class of theoretically difficult problems (NP-complete). These problems are intrinsically nonconvex and thus require global optimization techniques. Therefore, the design of efficient solution methods is a big challenge.
Team Member: Leo Warnow
- Gabriele Eichfelder and Leo Warnow, On implementation details and numerical experiments for the HyPaD algorithm to solve multi-objective mixed-integer convex optimization problems, Optimization Online, 2021.
- Gabriele Eichfelder and Leo Warnow, A hybrid patch decomposition approach to compute an enclosure for multi-objective mixed-integer convex optimization problems, Optimization Online, 2021.
Int2Grids: Integration of intelligent neighbourhood networks into interconnected networks; Sub-Project: Analysis of the influence of uncertainties for the development of a robust multiobjective optimization
Bundesministerium für Wirtschaft und Energie (BMWi) - Project number 03EI4013B
If neighborhood networks are integrated into overarching distributing networks, a pure optimization of the neighborhood networks under an externally defined weighting of the relevant targets does not do sufficiently justice to the problem. Moreover, uncertainties in the form of fluctuations or other disturbances can appear and a found solution has to be robust against that. In this subproject, the possibilities of the neighborhood networks for providing network and system services are investigated with respect to the individual targets, without aggregating these targets by a weighted sum, and, what is more, with regard to possible uncertainties. The individual criteria are considered individually as competing objectives. A trade-off between them is evaluated in a second step only, when the different, optimal possibilities, taking into account all criteria at the same time, have been determined. Thereby, the uncertainties are modeled using set-optimization to find robust solutions with new-to-develop procedures. If the uncertainties would not be considered within the optimization, the results would not be reliable. The susceptibility to faults could add up and have a negative effect on the entire system and lead to an unwanted destabilization of the network.
The focus of the work will be the study of the effects of uncertainties by using tools from set optimization. We will also study whether and how a combination of set optimization with sensitivity analysis can be useful. The working plan also contains solving the arising bi-level problems by using scalarization approaches, as well as to combine these approaches with KKT-based methods to identify similar structures and to develop hybrid algorithms. Another aspect is the extension of the developed methods to mixed integer problems. The new methods will be compared with existing ones, validated and tested, and all new research results will be published.
Team Member: Dr. Ernest Quintana
Algorithmic approaches to set optimization
Deutsche Forschungsgemeinschaft (DFG) - Project number 392195690
2018 - 2022
Set optimization problems have recently gained a lot of attraction as they appear in many important and timely applications such as finance (dynamic multivariate risk measures) and robust optimization (for instance in case decision uncertainty is taken into account). The main difficulty is that the values of the objective function are now sets and that a practical relevant optimality notion, known as set approach, requires that these sets have to be compared as a whole. This also implies that there is in general an infinite number of optimal solutions and it has to be the aim to find a representation of this set. While there is a continuously growing research in set optimization, it mostly concentrates on theoretical insights as on relations to other optimality concepts or derivative concepts for optimality conditions. So far there is only very limited research on algorithms for solving set optimization problems. With this project we intend to bring a significant contribution to the development of set optimization with the set approach by providing new theoretical insights which will be used for a new solution algorithm. We will follow a completely new direction by formulating suitable multiobjective optimization problems which can then be solved with the help of parameter dependent scalar-valued subproblems. We will allow the set optimization problems to be nonlinear, but other strong assumptions as on the smoothness will be required to allow to solve the arising scalar-valued subproblems numerically. Moreover, we will also bring new ideas to this growing research area by studying concepts like quality criteria for the evaluation of representations of the image of the optimal solution sets which are now union of sets. We also aim to contribute to the extension of classical concepts from scalar-valued optimization, as local and approximate optimal solutions, to set-valued problems which will be important for any algorithmic developments in this field. Our basic idea is to use minimal value functions for sufficient conditions for optimal solutions of the set optimization problem. Based on them new multiobjective optimization problems will be constructed where the objectives of these problems will be selected adaptively within the algorithm. The arising multiobjective problems will be solved by parameter dependent subproblems. The steering of these parameters will also be done adaptively to find representations of the optimal solution sets of the set optimization problem with a high quality and numerically efficient. The difficulties from the set optimization problem (as non-convexity) directly transfer to the difficulties of the subproblems. This limits the type of problems which can practically be solved. The theoretical results will nevertheless apply to wider classes of set optimization problems and will give a completely new direction also for further theoretical examinations as on optimality conditions.
Team Member: Stefan Rocktäschel
- Gabriele Eichfelder and Stefan Rocktäschel, Solving set-valued optimization problems using a multiobjective approach. Preprint (2021), Optimization Online
- Toabis Gerlach and Stefan Rocktäschel, On convexity and quasiconvexity of extremal value functions in set optimization. Preprint (2021), Optimization Online
Exact Approaches for Solving Multiobjective Mixed Integer Nonlinear Programming Problems
DAAD Vsiting Grant, granted to Prof. Marianna De Santis, Sapienza University of Rome for a 4 weeks visit
Most real-world optimization problems in the areas of applied sciences, engineering and economics involve multiple, often conflicting and nonlinear, goals. In the mathematical model of these problems, under the necessity of reflecting discrete quantities, logical relationships or decisions, integer and 0-1-variables need to be considered. We are then in the context of MultiObjective Mixed Integer Nonlinear Problems (MO-MINLPs). MO-MINLP problems combine all the diculties of both MultiObjective Problems (MOPs) and Mixed Integer Nonlinear Programming problems (MINLPs), which are among the class of theoretically dicult problems (NP-complete). These problems are intrinsically nonconvex and thus require global optimization techniques. Therefore, the design of ecient solution methods is a big challenge for people working in optimization and operations research. The research activity will be devoted to the study and the denition of new optimization methodologies to deal with a specic class of MO-MINLPs: in particular, we plan to focus on convex multiobjective mixed integer programming problems.
- Marianna De Santis, Gabriele Eichfelder, Julia Niebling and Stefan Rocktäschel, Solving Multiobjective Mixed Integer Convex Optimization Problems, accepted for publication in SIAM J. Optimization, 2020.
Global multiobjective optimization
Nachwuchsförderprogramm der Carl-Zeiss-Stiftung für Frau Julia Niebling
2017 - 2019
This project aims on the development of deterministic and efficient algorithms with a well-founded theoretical background for nonconvex multi-objective optimization problems. Thereby one has to compare vectors of objective function values based on the componentwise ordering in the multi-objective case. The new algorithms shall calculate a covering or a representation of the set of optimal solutions or of the image of this set under the objective function, respectively, with a predefined quality. The new algorithm will be based on the well-known Branch and Bound method, which is a global optimization method to solve scalar-valued problems. This method will be generalized to vector optimization by defining new and appropriate selection and branching rules. The basic idea of this algorithmic approach is a covering of the feasible set using boxes. The selection rules define which boxes will be partitioned in the next iteration of the algorithm and influence thus the quality of the covering/representation and the effectiveness of the procedure. For the bounding step criteria have to be determined which allow to omit sub-boxes in the remaining of the procedure. The main challenge is that the formulation of these criteria in the case of vector optimization requires the comparison of points with sets and sets with sets numerically. For doing this inner and outer approximations have to be found for these sets. This can be done by adapting known procedures for approximating the efficient set of convex multiobjective optimization problems. Thus, the results of the project will also serve as an important step towards the development of numerical algorithms for the solution of more general set optimization problems.
Team Member: Dr. Julia Niebling
Julia Niebling, Gabriele Eichfelder, A Branch-and-Bound based Algorithm for Nonconvex Multiobjective Optimization, SIAM Journal on Optimization, 29(1), 794 - 821, 2019.
Gabriele Eichfelder, Julia Niebling, Stefan Rocktäschel, An algorithmic approach to multiobjective optimization with decision uncertainty, Journal of Global Optimization, 77, 3-25, 2020.
Gabriele Eichfelder, Kathrin Klamroth, Julia Niebling, Nonconvex Constrained Optimization by a Filtering Branch and Bound, 37p., OptimizationOnline, 2020.
Gabriele Eichfelder, Kathrin Klamroth, Julia Niebling, Using a B&B algorithm from multiobjective optimization to solve constrained optimization problems, AIP Conference Proceedings 2070, 020028 (2019) https://aip.scitation.org/doi/abs/10.1063/1.5089995
Julia Niebling, Gabriele Eichfelder, A Branch-and-Bound Algorithm for Biobjective Problems, Proceedings of the XIII Global Optimization Workshop GOW'16, 57-60, 2016.
Multi-objective optimization of heterogeneous functions
Project B5 in GRK 1567: Lorentz Force Velocimetry and Lorentz Force Eddy Current Testing
Deutsche Forschungsgemeinschaft (DFG) - Project number 89085041
associated 2013 - 2015, Dr. Jana Thomann 2016 - 2019
In several projects of the Research Training Group optimization problems arise which have two or more conflicting objectives. Such problems are called multi-objective optimization problems. For instance, for the Lorentz force velocimetry it is important to find geometric arrangements of magnets such that the weight of the magnets is small while the measurable Lorentz force is large. These two objectives are competing and have to be optimized simultaneously. While the first is comparatively easy to evaluate, the values for the second objective can only be obtained by a time consuming ('expensive') numerical simulation run. Therefore, the goal of project B-5 is to develop a general procedure for multi-objective optimization problems where one of the objective functions is simulation based/expensive. A special focus of the project will be on the heterogeneous character of the objective functions. The procedure will be implemented and numerically tested. The algorithm will also be applied to optimization problems which arise in other projects of the Research Training Group as for instance that of the project B-4 from 2013-2015. The PhD student will further use his or her knowledge in mathematical optimization to perform a deep theoretical investigation of the algorithm. It is the aim to show its convergence and its ability to solve the problems of interest with a pre-defined quality.
Team Member: Dr. Jana Thomann
Jana Thomann, Gabriele Eichfelder, A Trust-Region Algorithm for Heterogeneous Multiobjective Optimization, SIAM Journal on Optimization, 29(2), 1017 - 1047, 2019.
Jana Thomann, Gabriele Eichfelder, Numerical Results for the Multi-Objective Trust Region Algorithm MHT, Data in Briefs, 25 , 18 pages, 2019.
Jana Thomann, Gabriele Eichfelder, Representation of the Pareto front for heterogeneous multi-objective optimizationzation, Journal of Applied and Numerical Optimization, 1(3), 293-323, 2019.
Sebastian Prinz, Jana Thomann, Gabriele Eichfelder, Thomas Boeck, Jörg Schumacher, Expensive multi-objective optimization of electromagnetic mixing in a liquid metal, 23p., Optimization and Engineering, 2020. DOI: 10.1007/s11081-020-09561-4.
Proper optimality and scalarizations for vector optimization problems with a variable ordering relation
DFG - Initiation and Intensification of Bilateral Cooperation
August 2012, guest: Prof. Refail Kasimbeyli, Izmir
It is planned to start joint research in the field of vector optimization, i.e. on optimization problems with a vector-valued objective function, and within this field especially on problems with a variable ordering structure replacing the common partial ordering. That problem class was mentioned already in 1974 in a fundamental paper on vector optimization problems but since then not much research was done in this area. A reason for that might have been that no applications were known using such an ordering principle which allows the preferences to depend on the current values in the image space. Recently, several applications for instance in medical image registration or portfolio optimization have risen the interest and for that reason it is of importance to study these optimization problems more deeply. The basic theory is meanwhile understood, but for deeper understanding several optimality concepts like the notion of proper optimality -- known from vector optimization in partially ordered spaces because of their importance in applications -- need to be studied in this new context. Proper optimality is in general closely related to scalarization functionals such that one needs to study also those and the applicants plan to apply their joint knowledge also here.
Gabriele Eichfelder and Refail Kasimbeyli, Properly optimal elements in vector optimization with variable ordering structures, Journal of Global Optimization, Volume 60(4), 689-712, 2014.