Accueil des participants

Optimisation multi-objectifs : un tutoriel

Olivier Spanjaard

LIP6, Université Pierre et Marie Curie

Transparents de la présentation

Lors de cet exposé, nous nous efforcerons dans un premier temps de montrer l'utilité de l'optimisation multi-objectifs (même pour des problèmes qui ne semblent pas multi-objectifs au premier abord), puis nous présenterons un panorama des méthodes exactes de résolution des problèmes d'optimisation combinatoire multi-objectifs, en illustrant sur des exemples. En fonction du déroulement de l'exposé, nous aborderons également les méthodes d'approximation multi-objectifs avec garantie de performance.

Pause déjeuner

Multi-objective optimisation and multi-armed bandits

Madalina M. Drugan

AI-Lab , Vrije Universiteit Brussel

Transparents de la présentation

Multi-armed bandits (MAB) is an optimization paradigm often used into stochastic sequential environments. Different multi-armed bandits have been proposed to be efficient in different real-life applications. Multi-armed bandits algorithms use reward vectors in the newly developed multi-objective multi-armed bandits (MOMAB) paradigm. Techniques from multi-objective evolutionary computation are integrated to improve the exploration/exploitation trade-off for complex, large and (possible stochastic) multi-objective environments. We discuss different aspects of MOMAB algorithmic design, like the theoretical and experimental analyses, and the validation of the designed algorithms in practical applications.

Multi-objective optimization in SDN networks: two practical examples

Paolo Medagliani

Huawei Technologies France

According to the SDN paradigm, the SDN controller is a network element that, for every incoming demand, computes and embeds a path within a network. However, for each allocated demand there is an associated cost, related to resource utilization, and some QoS constraints to respect (i.e., delay or maximum number of traversed hops). Therefore, the goal of the SDN controller is to minimize the cost of each path subject to the fulfillment of constraint requirements. Moreover, in order to provide sufficient resilience in case of failures, it is mandatory to allocate a backup path that is maximally disjoint with the primary path, transforming the original problem into a multi-objective one. Additionally, when huge flows need to be allocated in the network, the problem becomes how to split them in order to provide the fairest path allocation under the requirement of minimizing the overall cost as well as the number of times a flow is split. Throughout this presentation, we will provide an overview of multi-objective optimization for guaranteeing resilience in SDN networks. In addition, we will provide some insights on how to optimally address flow splitting in case of multi-commodity flow problem.

Pause café

On the computation of the nondominated set by scalarizations with adaptive parameter selection

Kerstin Dächert

Universität Duisburg-Essen & LAMSADE, Paris-Dauphine

Joint work with Kathrin Klamroth, University of Wuppertal

Transparents de la présentation

In this talk we present an algorithm that computes the nondominated set or a subset of it by solving a sequence of scalarizations whose parameters are varied in an adaptive way. More precisely, the parameters are chosen so that with every scalarization solved either a new nondominated point is computed or the investigated part of the search region, i.e. the part of the outcome space containing possibly further nondominated points, can be discarded. Besides an appropriate computation of the parameters, the main ingredient of such an adaptive parametric algorithm is a systematic decomposition of the search region. In the tricriteria case we present a redundancy-free decomposition which permits to show that the number of scalarized optimization problems that need to be solved in order to generate the nondominated set depends linearly on the number of nondominated points. This improves former results which showed a quadratic dependence in the worst case. We validate our theoretical findings by numerical tests.

Decoding Strategies for the 0/1 Multi-objective Unit Commitment Problem

Sophie Jacquin

Dolphin, Laboratoire d'Informatique Fondamentale de Lille

Transparents de la présentation

In the single objective Unit Commitment Problem (UCP) the problem is usually separated in two sub-problems: the commitment problem which aims to fix the on/off scheduling of each unit and the dispatching problem which goal is to schedule the production of each turned on unit. The dispatching problem is a continuous convex problem that can easily be solved exactly. For the first sub-problem genetic algorithms (GA) are often applied and usually handle binary vectors representing the solutions of the commitment problem.Then the solutions are decoded in solving the dispatching problem with an exact method to obtain the precise production of each unit. In this paper a multi-objective version of the UCP taking the emission of gas into account is presented. In this multi objective UCP the dispatching problem remains easy to solve whereas considering it separatly remains interesting. A multi-objective GA handling binary vectors is applied. However for a binary representation there is a set of solutions of the dispatching problem that are pareto equivalent. Three decoding strategies are proposed and compared. The main contribution of this paper is the third decoding strategy which attaches an approximation of the Pareto front from the associated dispatching problem to each genotypic solution. It is shown that this decoding strategy leads to better results in comparison to the other ones.