Réunion ATOM du jeudi 24 novembre 2022

La prochaine réunion du groupe ATOM (Application et Théorie de l'Optimisation Multiobjectif) groupe de travail du GDR RO du pôle DMEI (Décision : Evaluation, Modélisation, Incertitude) soutenu par la ROADEF <http://www.roadef.org/> aura lieu le jeudi 24 novembre à Sorbonne Université, Laboratoire LIP6, salle 25-26/105.

Lien Zoom : https://cnrs.zoom.us/j/94731808881?pwd=eEpYajBFS09jcEtCQXVPa0NLM1cxUT09

Le programme de la journée est le suivante :

9h30 : Accueil

10h : Arnaud Liefooghe (Mcf HDR, Laboratoire CRIStAL, Université de Lille, présentation invitée) : Landscape analysis and feature-based automated algorithm selection for multi-objective optimization

Although local search and evolutionary algorithms are methods of choice for multi-objective optimization, it remains impossible to recommend a priori which algorithm to select among the plethora of available methods for solving a given target problem. Of fundamental interest is to understand more precisely the behavior of search heuristics. This issue relates to landscape analysis, which aims at informing about the problem structure from the point of view of algorithms, thus making it possible to apprehend the difficulties that methods have to face depending on the problem being solved. These analytical tools can take the form of quantifiable statistics, known as landscape features, that can be measured over the landscape. The aim here is to present such landscape features for multi-objective optimization, and to analyze which and how landscape features drive algorithm performance. From a more practical point of view, landscape features are in fact a necessity to predict algorithm performance and to automate the tedious task of selecting the algorithm which is most likely to efficiently solve a previously-unseen problem. Machine learning techniques can benefit from these features to automatically predict the most suitable algorithm for the problem to be solved. The challenge here is once again to design and analyze multi-objective landscape features, but this time with a particular emphasis on their computational efficiency, so that they can prove useful for automated algorithm selection.

11h : Yue Zhang (Doctorante, LIPN, Université Sorbonne Paris Nord) : A dynamic criteria-decision space exploited Bi-objective Binary Branch & Cut algorithm

We propose a Branch&Bound framework (BBBB) to enumerate every non-dominated solution of a Bi-objective Binary linear program. The efficiency of a BBBB is mainly based on the availability to prune the nodes using a comparison between the lower bound and upper bound sets. For purpose of strengthening the lower bound sets, we add valid inequalities using classical separation methods initially from mono-objective optimization background. In this bi-objective context, such a cutting plane approach could be enhanced by multi-point separation algorithms. Beyond that, we adapt our BBBB tree to a dynamic exploration both in objective and variable space parallelly. Using the VoptSolver framework in Julia, preliminary experimental results will be presented to show the efficiency of our algorithm.

11h30 : Benjamin Doerr (Professeur, LIX, École Polytechnique) : New Runtime Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)

The non-dominated sorting genetic algorithm II (NSGA-II) is the most intensively used multi-objective evolutionary algorithm (MOEA) in real-world applications. Only very recently, mathematical runtime analyses for this algorithm were started. In this talk, I will give an overview over this young, but very active research direction.

12h : repas

14h : Nicolas Dupin (Mcf, Laboratoire LERIA, Université d'Angers, présentation invitée) : Robust optimization of refueling and maintenance planning of nuclear power plants, from bi-level to multi-objective optimization

This presentation deals with a real-world case study of Multi-Objective Optimization from Energy management, to support decision making for maintenance planning and refueling of nuclear power plants. Firstly, industrial context and constraints of electricity production are presented. Secondly, the optimization problem of maintenance planning and refueling of nuclear power plants is presented with a stochastic mathematical programming formulation, with  methodological insights are shown to solve this complex mono-objective optimization on large scale real-world instances. Lastly, multi-objective optimization extensions are discussed. A first extension dealing with stability in monthly re-optimization is straightforward and efficient. A robust optimization extension, taking into account uncertainty in maintenance duration, can be modeled using bi-level programming. Numerical issues induce the use a multi-objective optimization approach as 100% robust solution may not exist. Diverse solutions with different risk/cost are provided along a Pareto Front instead. This real-world case study illustrates the collaboration between multi-objective optimization for a better decision making, with matheuristics to solve large scale instances using MILP programming to model an highly-constrained optimization problem.

15h : Marie Humbert--Ropers (Doctorante, LAMSADE, Université Paris Dauphine) : On discrete representations of the non-dominated set

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.

15h30 : Discussion