Dagstuhl Seminar 20031
Scalability in Multiobjective Optimization
( Jan 12 – Jan 17, 2020 )
Permalink
Organizers
- Carlos M. Fonseca (University of Coimbra, PT)
- Kathrin Klamroth (Universität Wuppertal, DE)
- Günter Rudolph (TU Dortmund, DE)
- Margaret M. Wiecek (Clemson University, US)
Contact
- Michael Gerke (for scientific matters)
- Annette Beyer (for administrative matters)
Schedule
Multiobjective optimization (MO) strives for the simultaneous consideration of conflicting objectives and complicating constraints. It has become an indispensable tool in complex decision-making situations involving conflict that arises, for example, among multiple decision makers, or between multiple goals, objectives, and constraints. Applications include many areas of human activity in business, management and engineering. With the ongoing production of big amounts of data and increasing computational power, we have recently experienced a shift of paradigm from decision-making problems with relatively few variables and constraints, and two or three objective functions, towards large-scale problems involving many variables, many objective functions and constraints, and many decision makers. In view of these growing practical needs, the scalability of models and solution approaches, as a decisive characteristic for future applicability and success of multiobjective optimization, has thus become a crucial issue for two main research communities, Evolutionary Multicriterion Optimization (EMO) and Multi-Criterion Decision Making (MCDM).
In this Dagstuhl Seminar, we will focus on three main aspects of scalability in multiobjective optimization and their interplay, namely
- MO with many objective functions,
- MO with many decision makers, and
- MO with many variables and large amounts of data.
This viewpoint explicitly includes problems with computationally heavy objectives, data-heavy objectives, distributed and/or hierarchical decision processes, and the interplay of these. It also brings on board parallel/distributed processing, meta-modelling, group decision making, and other related areas. Each focus will be scrutinized with regard to scalability of the methods currently at our disposal and how parallelism (many cores or GPUs) can serve this purpose. In addition to modelling and algorithm development, we strive for the development of scalable test cases and tools for numerical validation.
During the seminar, we intend to achieve the following goals by combining EMO and MCDM perspectives and tools:
(i) Understand why current approaches in multiobjective optimization do not usually scale well with (1) an increasing number of objectives, (2) an increasing number of decision makers, and (3) an increasing number of variables and data,
(ii) Jointly identify novel strategies for model building, solution algorithms, preference modelling, testing and validation that are capable of handling large-scale problems, and
(iii) Initiate collaborative projects for implementing scalable approaches in challenging real-world decision-making situations.
This seminar carries on a series of six previous Dagstuhl Seminars (04461, 06501, 09041, 12041, 15031 and 18031) that were focused on multiobjective optimization. Our major goal is to further strengthen the links between the EMO and MCDM communities, and to advance both theoretical understanding and computational techniques in multiobjective optimization.
To continue being useful to society, MO has to address new challenges brought to science and engineering by big data that are continuously being produced and stored with a much lower cost than ever in the past. Since massive production of data takes place in the areas of human activity that have traditionally benefited from MCDM (e.g., social media analysis, retail sales, or high-frequency finance), MO needs to enter a new stage of development to be able to handle the high-dimensional data. Driven by this increasing availability of data and also motivated by an unprecedented demand for efficient, reliable and robust optimization methods, research in MO has to focus on the particular difficulties arising in large-scale problems. This requires from MCDM researchers new statistical thinking and leads to an increasing demand for efficient solution methods for large-scale problems, involving many objective functions and/or constraints, many decision makers, many variables and large amounts of data.
In this spirit, the focus in the seminar was on scalability which has become a universal challenge for mathematical optimization, and for EMO and MCDM in particular. Scalability is a characteristic of a system that describes its capability to cope and perform under an increased or expanding workload. A system that scales well will be able to maintain or even increase its level of performance or efficiency when tested by larger operational demands. In an economic context, a company's scalability implies that the underlying business model offers the potential for economic growth within the company. Therefore the main goals of the seminar were the exploration and elucidation of scalability in three fundamental domains: MO with many objective functions, MO with many decision makers, and MO with many variables.
While single objective optimization problems possess (at most) one optimal objective value, biobjective optimization problems are already intractable in many cases, i.e., combinatorial problems such as, for example, shortest path and spanning tree problems, may have an exponential number of nondominated solutions. Going from two to three objectives is another major step in difficulty since there does no longer exist a complete ordering of nondominated solutions. Problems with many objective functions pose even greater challenges. Since the number of nondominated solutions generally grows exponentially with the number of objective functions (as long as these are conflicting), efficient strategies for the detection of redundancies, for model reduction and for metamodelling are crucial for the scalability of existing methods. In the domain of MO with many objective functions the following specific topics were addressed:
- Model building and the derivation of technical properties are crucial for understanding the specific challenges in many-objective optimization. The following topics were undertaken: (i) Identification of interdependencies between objective functions as compared to real conflict; (ii) Relevance of many objective functions to a given real-life decision-making situation; (iii) Exploration of mathematical or statistical tools that can compress information while retaining the important problem features. Methodological approaches in this context included data analysis, metamodelling, partial and full scalarization, and a new concept for approximation schemes with quality guarantees.
- Concise representations are indispensable for the development of efficient algorithms, particularly EMO algorithms, interactive approaches, and decision support tools. The scalability of quality measures and associated representations, including hypervolume, uniformity, coverage, and varepsilon-indicator were discussed and novel representation and visualization paradigms suitable for many-objective optimization were proposed.
- Efficient solution algorithms that scale well with an increasing number of objective functions or computationally expensive objective functions are needed. The shortcomings of existing methods were discussed and new strategies that are specifically designed for large-scale problems were derived.
- Scalable test cases are needed for the evaluation of the developed approaches. This has been a concern of the EMO community to some extent. The difficulties pertaining to construction of the test cases were identified and future work in this direction was proposed.
The discussion of MO with many decision makers considered the inherent changes in the decision process as soon as there is not just a single decision maker. The focus was on building a formal framework that guarantees a fair decision respecting the preferences of all decision makers with the least total loss.
The domain of MO with many variables was discussed jointly with the domain of MO with many objective functions because large-scale optimization problems involving many variables and large amounts of data often also involve many objective functions. However, an emphasis was put on the required adaptations of EMO and MCDM approaches to handle problems with a high-dimensional decision space. While EMO algorithms often scale relatively well with an increasing dimension of the decision space (at least as long as the number of objective functions remains relatively small), this is in general not the case for MCDM approaches. In particular, the most commonly used exact solution approaches, such as dynamic programming and branch and bound, suffer from the curse of dimensionality. Complexity theoretic aspects were discussed and the use of approximation paradigms, metamodelling, hybridization, or parallelization in this situation was investigated.
During the seminar the schedule was updated on a daily basis to maintain flexibility in balancing time slots for talks, discussions, and working groups, and to integrate in the program the talks whose authors were inspired by the ongoing seminar. The working groups were established on the first day in an interactive fashion. Starting with three large working groups focused around the three central topics of the seminar (MO with many objectives, MO with many decision makers, and MO with many variables), each participant was requested to formulate her/his favorite topics and most important challenges.
The three groups then rejoined and the prevailing topics were put into groups through a natural clustering process while the participants made up initial five working groups. During the week the participants were allowed to change the working groups while some groups split. Overall, the teams remained fairly stable throughout to eventually form eight groups by the end of the seminar. Abstracts of the talks and extended abstracts of the eight working groups can be found in subsequent chapters of this report.
Further notable events during the week included: (i) an invitation to the opening of the art exhibition with paintings of the artist Lola Sprenger, (ii) a hike during a time period with the best (!) weather conditions in the entire week, (iii) a presentation session allowing the participants to share details of upcoming events in the research community, and (iv) a wine and cheese party (see Fig. 1) made possible by a donation of Fraunhofer-Institut für Technound Wirtschaftsmathematik (ITWM) represented by Karl-Heinz Küfer. The participants are pleased to announce that they made a donation to Schloss Dagstuhl to make a painting by Lola Sprenger entitled “Berg und Tal” part of the permanent art display.
Offers and Needs Market
A major innovation to this seminar was the Offers & Needs Market open for the entire week. The participants could write their research offers and needs regarding MO on notepads in different colors and post on pin boards (see fig. Traditional wine & cheese party) to attract or find a possible collaborator. The idea was well received and the participants desired its repetition in future events.
Outcomes
The outcomes of each of the working groups can be seen in the sequel. Extended versions of their findings will be submitted to a Special Issue of Computers and Operations Research entitled "Modern Trends in Multiobjective Optimization" and guest-edited by the organizers of this Dagstuhl seminar.
This seminar resulted in a very insightful, productive and enjoyable week. It has already led to first new results and formed new cooperation, research teams and topics.
Acknowledgements
The organizers would like to express their appreciation to the Dagstuhl office and its helpful and patient staff for their professional and smooth cooperation; huge thanks to the organizers of the previous seminars in this series for setting us up for success; and thanks to all the participants, who worked hard and were amiable company all week. In a later section, we also give special thanks to Kathrin Klamroth and Günter Rudolph as they step down from the organizer role.
- Richard Allmendinger (University of Manchester, GB) [dblp]
- Mickaël Binois (INRIA - Valbonne, FR) [dblp]
- Fritz Bökler (Universität Osnabrück, DE) [dblp]
- Jürgen Branke (University of Warwick, GB) [dblp]
- Dimo Brockhoff (INRIA Saclay - Palaiseau, FR) [dblp]
- Carlos A. Coello Coello (CINVESTAV - Mexico, MX) [dblp]
- Kerstin Dächert (Fraunhofer ITWM - Kaiserslautern, DE) [dblp]
- Matthias Ehrgott (Lancaster University, GB) [dblp]
- Gabriele Eichfelder (TU Ilmenau, DE) [dblp]
- Michael Emmerich (Leiden University, NL) [dblp]
- Georges Fadel (Clemson University - Clemson, US) [dblp]
- José Rui Figueira (IST - Lisbon, PT) [dblp]
- Carlos M. Fonseca (University of Coimbra, PT) [dblp]
- Andreia P. Guerreiro (IST - Lisbon, PT) [dblp]
- Jussi Hakanen (University of Jyväskylä, FI) [dblp]
- Susan R. Hunter (Purdue University, US) [dblp]
- Hisao Ishibuchi (Southern Univ. of Science and Technology - Shenzen, CN) [dblp]
- Andrzej Jaszkiewicz (Poznan University of Technology, PL) [dblp]
- Pascal Kerschke (Universität Münster, DE) [dblp]
- Kathrin Klamroth (Universität Wuppertal, DE) [dblp]
- Karl Heinz Küfer (Fraunhofer ITWM - Kaiserslautern, DE) [dblp]
- Arnaud Liefooghe (University of Lille, FR) [dblp]
- Manuel López-Ibáñez (University of Manchester, GB) [dblp]
- Kaisa Miettinen (University of Jyväskylä, FI) [dblp]
- Sanaz Mostaghim (Universität Magdeburg, DE) [dblp]
- Boris Naujoks (TH Köln, DE) [dblp]
- Luís Paquete (University of Coimbra, PT) [dblp]
- Patrick M. Reed (Cornell University - Ithaca, US) [dblp]
- Enrico Rigoni (ESTECO SpA - Trieste, IT) [dblp]
- Günter Rudolph (TU Dortmund, DE) [dblp]
- Stefan Ruzika (TU Kaiserslautern, DE) [dblp]
- Serpil Sayin (Koc University - Istanbul, TR) [dblp]
- Anita Schöbel (Fraunhofer ITWM - Kaiserslautern, DE) [dblp]
- Britta Schulze (Universität Wuppertal, DE) [dblp]
- Pradyumn Kumar Shukla (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Ralph E. Steuer (University of Georgia, US) [dblp]
- Michael Stiglmayr (Universität Wuppertal, DE) [dblp]
- Christiane Tammer (Martin-Luther-Universität Halle-Wittenberg, DE)
- Heike Trautmann (Universität Münster, DE) [dblp]
- Tea Tusar (Jozef Stefan Institute - Ljubljana, SI) [dblp]
- Daniel Vanderpooten (University Paris-Dauphine, FR) [dblp]
- Margaret M. Wiecek (Clemson University, US) [dblp]
Related Seminars
- Dagstuhl Seminar 04461: Practical Approaches to Multi-Objective Optimization (2004-11-07 - 2004-11-12) (Details)
- Dagstuhl Seminar 06501: Practical Approaches to Multi-Objective Optimization (2006-12-10 - 2006-12-15) (Details)
- Dagstuhl Seminar 09041: Hybrid and Robust Approaches to Multiobjective Optimization (2009-01-18 - 2009-01-23) (Details)
- Dagstuhl Seminar 12041: Learning in Multiobjective Optimization (2012-01-22 - 2012-01-27) (Details)
- Dagstuhl Seminar 15031: Understanding Complexity in Multiobjective Optimization (2015-01-11 - 2015-01-16) (Details)
- Dagstuhl Seminar 18031: Personalized Multiobjective Optimization: An Analytics Perspective (2018-01-14 - 2018-01-19) (Details)
- Dagstuhl Seminar 23361: Multiobjective Optimization on a Budget (2023-09-03 - 2023-09-08) (Details)
- Dagstuhl Seminar 26041: Uncertainty Quantification in Multiobjective Optimization (2026-01-18 - 2026-01-23) (Details)
Classification
- modelling / simulation
- optimization / scheduling
- soft computing / evolutionary algorithms
Keywords
- multiobjective optimization
- multiple criterion decision making
- evolutionary multiobjective optimization
- EMO
- MCDM