We cordially thank the participants for their attendance and we hope to see you soon at the next workshop in 2018! Also again, we thank the Fraunhofer Institure ITWM for the nice and interesting evening!
The slides of the speakers can be found here.
The group photo and photos of the workshop (taken by Sven O. Krumke) can be found here.
Program Overview
October 19:
12:00-13:00 – Registration and Light Lunch
13:00-15:30 – Scientific Program
15:30-16:00 – Coffee Break
16:00-17:30 – Scientific Program
17:30 – Group Photo
18:00 – Social Event and Dinner at Fraunhofer Institute ITWM
October 20:
09:00-10:30 – Scientific Program
10:30-11:00 – Coffee Break
11:00-12:00 – Scientific Program
The program takes place at Building 42 (Room 110) of the University with the exception of the social event. This event is held at the Fraunhofer Institute ITWM, which is in walking distance of the University. See also the Venue for detailed descriptions, maps, and links.
The program can be downloaded as pdf file here.
Scientific Program
October 19:
13:00 – 14:00 Opening and Keynote I
Chair: Stefan Ruzika
13:00 – 13:10: Opening
13:10 – 14:00: Xavier Gandibleux (Université de Nantes)
Designing and Experimenting with vOptSolver an Algorithm for Computing the Weight Set Decomposition
(Abstract)
The vOptSolver is a free open-source software developed within the framework of the ANR-DFG vOpt research project. It is decomposed into two packages, vOptGeneric and vOptSpecific, and it adresses the modeling and the solving of various multi objective linear optimization problems (MOLP, MOMILP, MOIP, MOCO). The first public version has been released this summer 2017, and we assist to first feedbacks about the use of the solver. The first part of this talk introduces the current available version of the solver, while the second part presents an algorithm for computing the weight set decomposition developed and tested with vOptSolver.
14:00 – 15:30 Session 1 – Algorithmic Advances and Complexity for Multi-Objective Problems
Chair: Michael Emmerich
14:00 – 14:30: Thomas Stidsen (Danmarks Tekniske Universitet)
Hybrid Optimization of Bi-Objective TSP
(Abstract)
Over the last decades two different approaches to solve, to optimality, Multi-Objective Mixed Integer Programming (MOMIP) models has emerged: Criterion space approaches and decision space approaches. Criterion space approaches iteratively solves a number of single-objective MIP’s. Decision space approaches extend the classic Branch & Bound algorithm to handle more than one objective.
Here, we will present a hybrid approach, which both operate in decision space and in objective space. The classic Branch & Bound algorithm is extended to handle two objectives, i.e. specialized bounding and branching methods are utilized. Furthermore, a criterion-space based parallelization is performed, enabling simple massive parallelization, since no communication between the processes is necessary. The approach is compared with other approaches and we argue that in order to improve the performance of multi-objective solvers, we need to apply hybrid approaches. We test the developed approach on the simplest extension of the classic TSP problem, the bi-objective TSP problem. We determine the full set of nondominated points for the most used BITSP dataset, containing 10, 100 city problems. The found exact Pareto fronts have a size between 1900 and 3300 points.
14:30 – 15:00: José Rui Figueira (Universidade de Lisboa)
Compressed data structures for bi-objective {0,1}-knapsack problems
(Abstract)
Solving multi-objective combinatorial optimization problems to optimality is a computationally expensive task. The development of implicit enumeration approaches that efficiently explore certain properties of these problems has been the main focus of recent research. This talk proposes algorithmic techniques that extend and empirically improve the memory usage of a dynamic programming algorithm for computing the set of efficient solutions both in the objective space and in the decision space for the bi-objective knapsack problem. An in-depth experimental analysis provides further information about the performance of these techniques with respect to the trade-off between CPU time and memory usage.
15:00 – 15:30: Michael Emmerich (Universiteit Leiden)
Computational Geometry Challenges & Results in Multiobjective Optimization
(Abstract)
In multiobjective optimization and decision analysis it is common to compute sets of points or polytopes that cover trade off (hyper)surfaces. In this talk we will look at computational geometry problems related to this and their computational complexity. Many of these results have been discovered very recently and show that the boundary between problems that are tractable and intractable depends on various parameters and is very sensitive to the number of objectives.
15:30 – 16:00 Coffee Break
16:00 – 17:30 Session 2 – Multi-Objective Optimization under Uncertainty and Real-World Applications
Chair: Karl-Heinz Küfer
16:00 – 16:30: Anita Schöbel (Georg-August-Universität Göttingen)
Dominance for Multi-Objective Robust Optimization
(Abstract)
In robust optimization, the parameters of an optimization problem are not deterministic but uncertain. Their values depend on the scenarios which may occur. Single-objective robust optimization has been studied extensively. Since 2012, different concepts have been published for multi-objective optimization problems. Robust Pareto solutions are called robust efficient.
In another line of research, single-objective uncertain optimization problems are transformed to deterministic multi-objective problems by treating every scenario as an objective function.
In this talk we combine these two points of view. We treat every scenario as an objective function also in uncertain multi-objective optimization, and we define a corresponding concept of dominance which is called multi-scenario efficiency.
We sketch this idea for finite uncertainty sets and extend it to the general case of infinite uncertainty sets. We then investigate the relation between this dominance and six different robustness concepts. We show that every strictly robust efficient solution is multi-scenario efficient. On the other hand, under a compactness condition, there always exists a robust efficient solution which is at the same time multi-scenario efficient. This generalizes Pareto robustly optimal (PRO) solutions, from single-objective optimization to the multi-objective case.
16:30 – 17:00: Elisabeth Köbis (Martin-Luther-Universität Halle-Wittenberg)
Representation of Set Relations and Jahn-Graef-Younes Methods in Set Optimization
(Abstract)
In practical applications arising in Operational Research, the data necessary for modelling optimization problems is often not exactly known. The reasons for this can be diverse, and include, among others, rounding errors or numerical inaccuracy, errors in measurements, incomplete information or broad estimations leading to inexact data. If uncertainty is included in the optimization model, one is left with not only one objective function value, but possibly a whole set of values. This leads to a set-valued optimization problem, where the objective map is set-valued.
In this talk, we introduce very general definitions of set relations and propose their unified characterization by means of a prominent scalarizing functional from vector optimization. Furthermore, we propose new numerical methods for obtaining minimal elements of a family of finitely many sets. Most set optimization problems, even if given in a continuous framework, need to be handled in a discrete manner concerning computations. Therefore, given a finite discrete family of sets, in this talk we propose several numerical methods that first sort out non-minimal elements and then determine all minimal elements of the family of sets. These methods can be interpreted as extensions of the well-known Jahn-Graef-Younes method from vector to set optimization. When the involved sets are compared by means of a generalized set relation, we use the characterization of set relations by the aforementioned scalarizing functional. Numerical tests justify that our approaches are useful and the numerical effort is drastically reduced.
17:00 – 17:30: Karl-Heinz Küfer (Fraunhofer ITWM Kaiserslautern)
Industrial Applications of Multicriteria Decision Support
(Abstract)
Decision making in industry means making compromises: several objectives, most often cost, quality, production time or environmental impact have to be balanced as they are at least partially in conflict.
The talk will demonstrate and discuss examples of multicriteria decision support tools in medical therapy planning, chemical process engineering and in the layout of renewable energy facilities, all of them in industrial practice for 5 years and more. Special attention is paid to the reception of such concepts in the companies and their impact.
October 20:
09:00 – 10:30 Session 3 – Special Topics in Multi-Objective Optimization
Chair: Matthias Ehrgott
09:00 – 09:30: Sophie Parragh (Johannes Kepler Universität Linz)
Bi-objective branch-and-bound and its application to optimization problems arising in logistics
(Abstract)
In this talk, we present a branch-and-bound framework for bi-objective integer optimization. It relies on the notion of lower and upper bound sets and it uses what we call objective space branching in combination with “standard” variable branching techniques. Furthermore, it exploits integer objective function values in the pruning phase. We illustrate its performance and we show how we adapt it to successfully solve different (real world) optimization problems, such as a bi-objective orienteering problem, the green city hub location problem, and the golf tourist problem.
09:30 – 10:00: Kerstin Dächert (Bergische Universität Wuppertal)
Obtaining rough initial representations for continuous tricriteria optimization problems
(Abstract)
In this talk we present the generation of (discrete) representations of continuous tricriteria optimization problems with the help of different variants of an adaptive parametric algorithm. This algorithm relies on the successive solution of a scalarized problem whose parameters are varied in a systematic way. In particular, we consider a weighted Tchebycheff method as scalarization. In each iteration, either a new nondominated point is obtained or a certain part of the outcome space, which turns out to be empty, can be discarded from further consideration.
We implement different variants of our approach in Matlab and compute representations for certain test problems from the literature. The representations obtained by our adaptive approach are compared to an e-constraint scalarization with equidistant parameter choice based on the ideal point and the individual maxima of the image of the feasible set. Our results show that less infeasible and/or redundant scalarized problems occur for adaptive methods, in general. Moreover, by construction, these methods adapt better to the shape of the nondominated set. In our test problems, the non-adaptive method, for which all parameter values are fixed beforehand, works well when the computed vector of individual maxima equals the nadir point. However, even in these cases, it is outperformed by adaptive methods. The latter show their strength particularly when the vector of individual maxima overestimates the nadir point.
10:00 – 10:30: Matthias Ehrgott (Lancaster University)
Primal and Dual Algorithms for Optimisation over the Efficient Set
(Abstract)
Optimisation over the efficient set of a multi-objective optimisation problem is a mathematical model for the problem of selecting a most preferred solution that arises in multiple criteria decision making to account for trade-offs between objectives within the set of efficient solutions. We consider a particular case of this problem, namely that of optimising a linear function over the image of the efficient set in objective space of a convex multiobjective optimisation problem. We present both primal and dual algorithms for this task. The algorithms are based on recent algorithms for solving convex multi-objective optimisation problems in objective space with suitable modifications to exploit specific properties of the problem of optimisation over the efficient set. We first present the algorithms for the case that the underlying problem is a multi-objective linear programme. We then extend them to be able to solve problems with an underlying convex multi-objective optimisation problem. We compare the new algorithms with several state of the art algorithms from the literature on a set of randomly generated instances to demonstrate that they are considerably faster than the competitors.
10:30 – 11:00 Coffee Break
11:00 – 12:00 Keynote II and Closing
Chair: Clemens Thielen
11:00 – 11:50: Daniel Vanderpooten (Université Paris Dauphine)
Multiobjective Optimization: Approximation with Performance Guarantee
(Abstract)
We first review the main general concepts and results in multiobjective approximation with a priori performance guarantees. The use and power of the weighted sum aggregation to provide approximations is also investigated.
Even if multiobjective approximation and the resulting algorithms are mainly theoretical, we illustrate some applications in terms of producing practically efficient algorithms and providing discrete representations of the nondominated set.
11:50 – 12:00: Closing