All times are Western European Summer Time (WEST), i.e. UTC+1
- 08:40 – 09:00 Registration
- 09:00 – 10:10 Opening & Keynote 1
- 10:10 – 10:30 Coffee Break
- 10:30 – 12:30 Session 1
- 12:30 – 14:00 Lunch break
- 14:00 – 15:30 Session 2
- 15:30 – 15:50 Coffee Break
- 15:50 – 17:20 Session 3
- 17:30 – 18:45 Keynote 2 & Closing
Keynote speakers
Susan R. Hunter, Purdue University
Marta Pascoal, Polytechnic University of Milan / University of Coimbra
Susan R. Hunter is an associate professor in the School of Industrial Engineering at Purdue University. Her research interests include theoretical and algorithmic aspects of stochastic optimization in the presence of multiple performance measures, with emphasis on asymptotics, computation, and application. In 2016, she received a US National Science Foundation CAREER Award to work on multi-objective simulation optimization; that is, multi-objective optimization in which the objective functions can only be observed with stochastic error as the output of a black-box Monte Carlo simulation oracle. Her published works have been recognized by the INFORMS Computing Society in 2011, by IISE Transactions in 2017, and by The Operational Research Society in 2021. She currently serves as Program Chair for the 2024 Winter Simulation Conference, co-chair of local arrangements for the 2022 INFORMS Annual Meeting, and as an associate editor for Operations Research.
Marta Pascoal obtained her BSc in Mathematics-Computer Science and MSc in Mathematics-Applied Mathematics from the University of Coimbra in 1996 and 1998, respectively. She completed the PhD in Mathematics-Applied Mathematics from the same university in 2005. She was Assistant Professor and Associate Professor at the Department of Mathematics of the University of Coimbra since 2005. From 2021 she is Associate Professor in the Operations Research and Discrete Optimization group of the Department of Electronics, Information and Bioengineering of the Politecnico di Milano. She is currently associate editor for the RAIRO-Operations Research journal. Her main research interests are in discrete and network optimization, and in discrete multiobjective optimization; with focus on designing exact algorithms for problems in those contexts. Her
research has addressed application models in the fields of telecommunication networks or transportation.
Detailed Program
08:40 – 9:00 Registration
9:00 – 9:10 Opening
Luís Paquete, Carlos M. Fonseca, Carlos H. Antunes, Organizing Committee
9:10 – 10:10 – Keynote 1
Chair: Kathrin Klamroth
| On quantifying the error in multi-objective stochastic optimization | |
| Susan R. Hunter | |
| In this talk, we discuss recent advances and open questions in quantifying the error in solving multi-objective stochastic optimization (MOSO) problems. MOSO problems are nonlinear multi-objective optimization problems in which the objective functions are expectations and can only be observed with stochastic error, for example, as the output from a Monte Carlo simulation model or as a function of data from a database. We consider error quantification in two scenarios: (a) when the solution to the MOSO problem is unknown, as is the case in most real-world applications, and (b) when the solution to the MOSO problem is known, which is the case when researchers test algorithms on a testbed. In scenario (a), we discuss recent advances toward obtaining frequentist, asymptotically valid confidence sets on the efficient set (in the decision space) and the Pareto set (in the objective space). In scenario (b), we discuss performance metrics for MOSO algorithms and recent advances in obtaining upper bounds on the performance of algorithms under these metrics. |
10:10 – 10:30 – Coffee Break
10:30 – 12:30 – Session 1
Chair: Stefan Ruzika
| ε-constraint Based Representations for Multi-objective Integer Linear Programming Problems | |
| Mariana Cunha (University of Lisbon) | |
| Multi-objective problems have many Pareto optimal solutions. Nevertheless, from the DM’s perspective, some of those solutions are similar to each other and, therefore, of little added value. Hence, it is advantageous to present to the DM instead of the complete set of non-dominated outcome vectors a representation of it that captures the present trade-offs, is well spread, and comprises as few solutions as possible. To that end, three variations based on the ε-constraint method are put forward to generate representations that privilege coverage, uniformity and cardinality, respectively. All three algorithms perform well when generating the complete set of non-dominated outcome vectors compared to other approaches present in the literature, particularly the algorithms targeting uniformity. Furthermore, even though all algorithms are the best in their targeted performance indicator, the cardinality algorithm presents similar coverage errors to the coverage algorithm when the target cardinality is low compared to the complete set of non-dominated outcome vectors’ cardinality, whilst being significantly more efficient. |
| On Various Representations of the Non-dominated Set | |
| Marie Humbert-Ropers, Lucie Galand, Daniel Vanderpooten (Université Paris-Dauphine, PSL Research University, LAMSADE) | |
| Providing a “good representation” of a set of non-dominated points is a challenging issue, in particular for problems with more than two objectives. To assess the quality of a representation, three general properties – coverage, spacing and cardinality – which can be defined using a binary relation, have to be satisfied. To determine such a representation, we propose a method using linear programming formulations similar to the ones used for location problems in order to obtain a subset of points with fixed cardinality ensuring firstly coverage and then spacing properties. This method is general in the sense that it is not restricted to the biobjective case and also, in the sense that various binary relations can be used to define the representation. Thus, we discuss “neutral” binary relations based on distances or ε-dominance leading to representations that aim to provide a concise overview of the non-dominated set, or binary relations involving preference information leading to personalized representations. |
| Exact and Approximate Determination of the Pareto Front Using Minimal Correction Subset | |
| Andreia Guerreiro (Instituto de Engenharia de Sistemas e Computadores – Investigação e Desenvolvimento) | |
| Logic-based algorithms relying on the enumeration of Minimal Correction Subsets (MCSs) have been recently used for solving multiobjective Boolean optimization (MOBO) problems. The effectiveness of this approach relies on how the MOBO problem is encoded as a Maximum Satisfiability (MaxSAT) problem. This talk discusses the connection of Pareto-optimal solutions of a MOBO problem and MCSs. In particular, two approximation versions of the encoding of the objective functions to MaxSAT are discussed, for which enumerating all MCSs results in finding an approximation of the Pareto front with a priori guarantee. |
| Adding Valid Inequalities within Bi-objective Binary Branch & Bound | |
| Yue Zhang, Pierre Fouilhoux and Lucas Létocart (LIPN UMR CNRS 7030, Université Sorbonne Paris Nord) | |
|
In order to enumerate every non-dominated solutions of a Bi-objective Binary linear program, we |
12:30 – 14:00 – Lunch Break
14:00 – 15:30 – Session 2
Chair: Michael Stiglmayr
| Approximation via Scalarization | |
| Stephan Helfrich, Arne Herzel, Stefan Ruzika (University of Kaiserslautern), Clements Thielen (Weihenstephan-Triesdorf University of Applied Sciences, Technical University of Munich) | |
| A major bottleneck for exact solution methods of multiobjective optimization problems is that the cardinalities of the set of nondominated images and the set of efficient solutions may be exponentially large or even infinite. This strongly motivates the approximation of multiobjective optimization problems – a concept to substantially reduce the number of required solutions while still obtaining a provable solution quality. Here, it is sufficient to find a set of (not necessarily efficient) solutions that, for each possible image, contains a solution whose image is component-wise at least as good up to a multiplicative constant. Scalarizations are frequently used in approximation methods for multiobjective optimization problems. For example, it has been shown that optimal solutions of the weighted sum scalarization can be used to obtain approximation sets for each instance of each multiobjective minimization problem. However, these approximation results crucially rely on the assumption that all objectives are to be minimized. In fact, it is known that, for the weighted sum scalarization as well as for every other scalarization studied hitherto in view of approximation, even the set of all the optimal solutions of the scalarization does, in general, not constitute an approximation set in the case of maximization problems. This raises several questions: Are there intrinsic structural differences between minimization and maximization problems with respect to approximation via scalarizations? Does there exist a scalarization such that, in each instance of each maximization problems, optimal solutions of the scalarization constitute an approximation set? Beyond that, can optimization problems in which both minimization and maximization objectives appear also be approximated by means of scalarizations? If yes, what structural properties are necessary in order for scalarizations to be useful concerning the approximation of multiobjective optimization problems in general? In this talk, we tackle these questions and study the power of scalarizations for the approximation of multiobjective optimization problems from a general point of view. We develop a transformation theory for scalarizations with respect to approximation in the following sense: Suppose there exists a scalarization that yields an approximation of a certain quality for each instance of each multiobjective optimization problem with a given decomposition specifying which objective functions are to be minimized / maximized. Then, for each other decomposition, our transformation yields another scalarization that yields the same approximation quality for each instance of each problem with this other decomposition. Hence, we additionally study necessary and sufficient conditions on a scalarization such that optimal solutions can be used to obtain an approximation set and determine the achievable approximation quality. |
| Towards a Polynomial Delay Algorithm for Three-Objective Linear Optimization | |
| Fritz Bökler, Markus Chimani, Alexander Nover (University of Osnabrück) | |
| Multiobjective Linear Programming (MOLP) is a corner stone of multiobjective optimization (MOP) and multiobjective combinatorial optimization in particular. In recent years, methods emerged to classify algorithms for MOLP and other MOP as efficient. The state-of-the-art for computing the non-dominated extreme points of an MOLP is an incremental polynomial delay algorithm based on the Dual Benson algorithm, now usually called an Inner Approximation (IA) strategy. And the state-of-the-art for computing the non-dominated facets of an MOLP is an incremental polynomial delay algorithm based on the original algorithm by Benson, called an Outer Approximation (OA) strategy. For the special case of bi-objective linear programming, the well-known dichotomic approach is capable of finding the extreme points and facets in polynomial delay. A polynomial delay algorithm is not yet known for three and more objective linear programming. In this talk, we present a new algorithm addressing the weaknesses of the IA and OA methods, namely the non-locality of the vertex enumeration needed in both. We show that the new algorithm can compute the non-dominated extreme points of a three objective LP with polynomial delay. We therefore present the first polynomial delay algorithm for three-objective linear programming. For more than three objectives, we show that the algorithmic strategy is capable of computing the non-dominated extreme points in polynomial delay if certain degree bounds hold for the graph of the upper image. |
| A New Exact Method for Linear Bilevel Problems with Multiple Objective Functions at the Lower Level | |
| Maria João Alves, Carlos Henggeler Antunes (University of Coimbra) | |
| Bilevel programming is useful to model optimization problems with a hierarchical relation between two decision makers (the leader and the follower), who make decisions sequentially in a non-cooperative manner. The two decision makers control different sets of variables aiming to optimize their own objective functions. The leader commits to a strategy before the follower, who then optimizes his/her own objective function within the options restricted by the leader’s decision. Dealing with multiple objectives at the lower level (semivectorial bilevel problems) is particularly challenging due to the existence of a set of lower-level efficient solutions for each leader’s decision. In this work, we propose a general-purpose exact method to solve semivectorial linear bilevel problems. The method is based on the exhaustive search of efficient extreme solutions of an associated multiobjective linear programming (MOLP) problem with many objective functions. Therefore, its development required the design and implementation of an effective vector-maximum algorithm for MOLP problems. The method relies on a proposition stating that an optimistic optimal solution to the semivectorial linear bilevel problem is an efficient extreme point of this MOLP problem for which the number of objective functions is equal to the number of lower-level objective functions plus the number of upper-level decision variables plus one. Since the number of objective functions of the associated MOLP problem increases with the number of upper-level decision variables, and the number of efficient extreme points of a MOLP problem grows very quickly with the number of objective functions, this method is mainly adequate to bilevel problems with a small number of upper-level decision variables. This number is the dimension with the major impact on the computational effort required by the method. Based on the same principles, a local search heuristic procedure has also been designed to deal with problems in which the complete extreme point enumeration becomes impracticable within a reasonable computational time. The aim is to provide higher quality solutions when the exact method is not able to reach the optimal solution given a computational time budget. A computational study is presented to evaluate the performance of the exact method and the heuristic procedure, comparing them with an exact and an approximate method proposed by other authors, using randomly generated instances. Our approaches reveal interesting results in problems with few upper-level variables. The heuristic showed to be quite effective in problems where the global optimum is difficult to achieve.
|
15:30 – 15:50 – Coffee Break
15:50 – 17:20 – Session 3
Chair: Carlos H. Antunes
| Augmenting Branch and Bound by Scalarization-Based Information for Multiple Objectives | |
| Julius Bauß, Michael Stiglmayr, Kathrin Klamroth (University of Wuppertal) | |
| While in the single-objective case Branch and Bound based methods are the standard approach for solving (mixed-)integer optimization problems, in the multi-objective case Branch and Bound is rarely used in comparison to the predominant objective space methods. This is mainly due to two reasons: objective space methods benefit from optimized single-objective solvers, while bounding is considerably weaker in multiple objectives. We present improvements to increase the performance of bi-objective Branch and Bound algorithms by utilizing scalarization-based information and transfer the most promising approaches to the multi-objective case. We use the hypervolume indicator as a measure for the gap between lower and upper bound set to implement a dynamic bi-objective branching strategy. We also improve the lower and upper bound set by adaptively solving scalarizations in the root node to integer optimality. The obtained information may be integrated into the lower bounds of all active nodes, while the determined efficient solutions are integrated into the upper bound set. This upper bound set can be decomposed into the incumbent points and the already proven nondominated points. The updated bound sets lead to a higher fathoming rate of nodes and therefore to a decrease of the total computation time. |
| Indicator-Based Branch and Bound for Multi-Objective Optimization | |
| Alexandre Jesus, Luís Paquete (University of Coimbra), Arnaud Liefooghe, Bilel Derbel (University of Lille) | |
| In the branch and bound for the single-objective case, best-first search strategies that choose the most promising node to be expanded at each iteration are commonly used to achieve better (anytime) performance. However, in the multi-objective case such approaches have hardly been discussed. One possible reason is because best-first strategies often rely on the value of the bound to decide which nodes are the most promising, and assigning a value to the bound of a node in the multi-objective case is not as straightforward. In this work, we present the Indicator-Based Branch and Bound (IBB) approach, which makes use of quality indicators to measure the quality of the bound of a node with respect to the archive of solutions kept by the branch and bound, and use this information to decide which node is the most promising. We then carry out an experimental study on a multi-objective knapsack problem with increasing number of objectives, to study the (anytime) performance of the IBB, taking into account the hypervolume indicator and the epsilon-indicator to guide the search. The results show that the best-first search strategy based on quality indicators can often outperform the naive depth-first and breadth-first search strategies. |
| A Parallel Programming Hybrid Decision/Criteria Approach to Bi-objective MIP | |
| Alice Ryhl, Thomas Stidsen (Technical University of Denmark) | |
| We consider a set of bi-objective MIP models, where continuous variables are not allowed in both objectives, hence leading to a point pareto front. Our hypothesis is that the best approach is a collaborative approach where both criteria-space and decision-space method contributes. Furthermore, the approaches are parallelized to utilize independence of the sub-problems. The algorithms are implemented in Rust, and tested on a general set of bi-objecive MIP’s, created based on MIPLIB-2010, by adding a pseudo-random second objective.
|
17:30 – 18:30 – Keynote 2
Chair: Luís Paquete
| On exact methods for bi-objective network optimization problems | |
| Marta Pascoal | |
|
The particular structure of some network optimization problems often allows the application of specific algorithms for finding the corresponding efficient, of Pareto, sets of their multi-objective versions. In the first part of this talk we discuss some of those algorithms. We focus essentially on the bi-objective case and consider that the search can be done for different types of solutions: like paths between two given nodes of a network, sets of paths or trees; and for different types of objective functions: like cost minimization, bottleneck maximization, minimization of the number of types of arcs, maximization of the solutions diversity, or as the combination of some of these. The second part of this talk is dedicated to a path problem involving the maximization of a bottleneck objective function. We present recent algorithmic approaches for finding the Pareto set for this problem, and assess their performance. The relation between these algorithms with methods for more general multi-objective optimization problems and new research directions are highlighted. |
18:30 – 18:45 Closing
Organizing Committee