Exact Efficient Solution of Mixed Integer Programming Problems with Multiple Objective Functions
Final Report Abstract
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.
Publications
- “A general approximation method for bicriteria minimization problems”. In: Theoretical Computer Science 695 (2017), pp. 1–15
Pascal Halffmann, Stefan Ruzika, Clemens Thielen, and David Willems
(See online at https://doi.org/10.1016/j.tcs.2017.07.003) - “Approximation schemes for the parametric knapsack problem”. In: Information Processing Letters 120 (2017), pp. 11–15
Alberto Giudici, Pascal Halffmann, Stefan Ruzika, and Clemens Thielen
(See online at https://doi.org/10.1016/j.ipl.2016.12.003) - “Easy to say they are Hard, but Hard to see they are Easy— Towards a Categorization of Tractable Multiobjective Combinatorial Optimization Problems”. In: Journal of Multi-Criteria Decision Analysis 24.1-2 (2017), pp. 82–98
José Rui Figueira, Carlos M. Fonseca, Pascal Halffmann, Kathrin Klamroth, Luís Paquete, Stefan Ruzika, Britta Schulze, Michael Stiglmayr, and David Willems
(See online at https://doi.org/10.1002/mcda.1574) - “Multi-objective branch and bound”. In: European Journal of Operational Research 260.3 (2017), pp. 856–872
Anthony Przybylski and Xavier Gandibleux
(See online at https://doi.org/10.1016/j.ejor.2017.01.032) - “Multiobjective optimization for interwoven systems”. In: Journal of Multi-Criteria Decision Analysis 24.1-2 (2017), pp. 71–81
Kathrin Klamroth, Sanaz Mostaghim, Boris Naujoks, Silvia Poles, Robin Purshouse, Günter Rudolph, Stefan Ruzika, Serpil Sayın, Margaret M. Wiecek, and Xin Yao
(See online at https://doi.org/10.1002/mcda.1598) - “On branching heuristics for the bi-objective 0/1 unidimensional knapsack problem”. In: Journal of Heuristics 23.5 (Oct. 2017), pp. 285–319
Audrey Cerqueus, Xavier Gandibleux, Anthony Przybylski, and Frédéric Saubion
(See online at https://doi.org/10.1007/s10732-017-9346-9) - “Introducing multiobjective complex systems”. In: European Journal of Operational Research 280.2 (Jan. 2020), pp. 581–596
Tobias Dietz, Kathrin Klamroth, Konstantin Kraus, Stefan Ruzika, Luca E. Schäfer, Britta Schulze, Michael Stiglmayr, and Margaret M. Wiecek
(See online at https://doi.org/10.1016/j.ejor.2019.07.027)
