Servicenavigation

Detailseite

Zurück

Projekt Druckansicht

Exakte effiziente Verfahren zur Lösung gemischt-ganzzahliger Optimierungsprobleme mit mehreren Zielfunktionen

Fachliche Zuordnung Mathematik
Förderung Förderung von 2014 bis 2020
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 258775501
 
Erstellungsjahr 2020

Zusammenfassung der Projektergebnisse

Multiobjective Optimization tackles optimization problems where several, often conflicting, objectives have to be optimized simultaneously. Therefore, there usually exists not only one optimal solution to such problems but several so-called Pareto-optimal solutions that describe a trade-off between the particular objective functions. This a rather young field of research in optimization and hence the literature and algorithms, especially when integer and continuous variables are both involved, is sparse. However, solving multiobjective problems is often required as a decision aid for real-world problems: routing and facility location problems, process and supply chain planning, decisions on stock markets and data mining have several contradicting goals. Compromise solutions have to be found that not simply minimize the costs but consider other objectives. This project aims to identify new mathematical and algorithmic results to support decision making processes in complex situations. While for theoretical results we have focused on scalarization techniques that transform the multiobjective problem into a single objective one and the analysis of the mathematical and polyhedral structure of problems, we have concentrated algorithmic-wise on the development of Branch-and-Bound and Branch-and-Cut algorithms. The goal then is the practical implementation of existing and new results in an open-source software ecosystem that is ready to use for researchers but also for application purposes. During the course of the project, we have made substantial theoretical progress, especially regarding scalarization methods. An in-depth analysis of the well-known scalarization methods weighted sum, weighted Tchebyshev, and epsilon constraint has returned properties of the mathematical structure of these methods that has been exploited for algorithmic usage: We have introduced a weight set decomposition algorithm for weighted sum that has the asymptotically best running time of existing algorithms and is competitive in practice. A similar algorithm has been conducted for weighted Tchebyshev, while the epsilon constraint method has been applied in a box algorithm to compute a representation of optimal solutions for three objectives. For the two former scalarization methods these algorithms are in particular based on a rigorous investigation of the parameter set that returned exploitable polyhedral properties. For weighted Tchebyshev, this has been a novelty and for weighted sum we utilized these properties to construct a new approximation algorithm and a heuristic for the weight set decomposition which is again a new feature. Our results on weighted sum and its polyhedral properties have led to an application for approximation algorithms for both multiobjective and parametric problems, where we lead the way in research with significant results. Regarding algorithms, we have designed a state-of-the-art branch and bound method, with the identification of weaknesses in the published propositions. Contributions have been done on all the components of this kind of method: bound sets based on relaxation, branching variables, and choice of active nodes. This led to innovative algorithms that also have been tailored to particular problem such as knapsack and facility location problems. Further improvements have been done in the introduction of new cuts in Branch-and-Cut algorithms. A software ecosystem vOptSolver has been developed, allowing users to model their optimization problem, to associate data for this problem, to solve it and to get formally the results before analysing them. This is an freely accessible, easy-to-use, and open source software package designed for both researchers and users in application and it comes with a library vOptLib of instances of problems. In this software, both existing methods but also algorithms that have been conducted during this project have been integrated. We also have given other researchers the opportunity to contribute to the software by providing the code of their algorithms or providing instances. To the best of our knowledge, this is the most innovative and most complete software that is currently available in the field of multiobjective optimization.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

© 2024 DFG Kontakt / Impressum / Datenschutz

Textvergrößerung und Kontrastanpassung