SPOC16 "Optimisation Combinatoire Multi-Objectif"
Primary tabs
Date:
Friday, 15 December, 2017
16ème séminaire du groupe POC
Le VENDREDI 15 DECEMBRE 2017
Au laboratoire LAMSADE de l’Université Dauphine
Place du Maréchal de Lattre de Tassigny
75017 PARIS Cedex
Pour l'accès voiture et transport en commun
Amphi 5, Hall du 2ème etage.
Sur le thème
"Optimisation combinatoire Multi-Objectif"
Ce séminaire est libre d'accès mais merci de vous inscrire en utilisant l'onglet situé en-haut de page pour faciliter l'organisation.
Cliquer ici pour voir la liste des inscrits
Programme de la journée:
9h30-10h00 Accueil "café-croissants"
10h00-12h00
Xavier Gandibleux et Antony Przybylski, University of Nantes
Optimisation combinatoire multiobjectif : deux contributions issues du projet de recherche ANR-DFG vOpt
Le projet vOpt aborde le calcul de solutions efficaces de problèmes de programmation linéaire en variables mixtes comportant plusieurs objectifs. Dans le contexte algorithmique et logiciel du projet, deux contributions relevant du thème de la 16ieme journée SPOC sont développés. La première contribution présente l'extension de la notion de borne dans le cas mono-objectif, vers la notion d'ensemble bornant dans le cas multi-objectif. Des ensembles bornants couramment utilisés dans la littérature sont ensuite présentés, avec leurs avantages et leurs inconvénients. Des questions d'ordre général concluent cette présentation. Une étude de cas sur le problème de sac à dos bi-objectif bi-dimensionnel, issue d'un travail en collaboration avec Kathrin Klamroth et Britta Schulze est ensuite présentée. La seconde contribution présente vOptSolver (https://voptsolver.github.io/vOptSolver/), logiciel gratuit et open-source sous licence MIT. Il est décomposé en deux packages, vOptGeneric et vOptSpecific, offrant la possibilité de modéliser et de résoudre différents problèmes d'optimisation multiobjectif (MOLP, MOMILP, MOIP, MOCO). Pour les contributeurs, vOptSolver est disponible en ligne sur un dépôt GitHub; pour les utilisateurs, vOptSolver est intégré à Julia, langage de programmation scientifique (https://julialang.org/), sous la forme de package standard.
12h00-14h00 Repas
14h00 - 15h00
Stefan Ruzika, University of Kaiserslautern (Germany)
Approximation of Nondominated Sets in Multiobjective Progamming
Computing the set of optimal solutions of multiobjective programming problems (so-called efficient solutions) is typically difficult, both in theory and practice. Therefore, the idea of approximating the efficient set together with its image (the so-called nondominated set) arose and there exist several approaches for approximating general multiobjective minimization problems (see e.g. the work of Papadimitriou and Yannakakis or the work of Glaßer et al.). Compared to the single objective case, there are some fundamental differences in the multiobjective case which may become apparent already for the case of two objective functions: The output of a biobjective approximation algorithm is a set of feasible solutions which constitutes an (α,β)-approximation of the efficient set, i.e., for every efficient solution there exists an approximating solution which dominates this efficient solution up to a factor of α in the first objective and up to factor of β in the second. The specific values of α and β depend on the algorithm used. With this talk, we give an introduction to and an overview of approximation results which are widely applicable and not specifically tailored to some concrete problem. Moreover, we present a state-of-the-art algorithm in some more detail. This algorithm relies on iteratively solving weighted-sum scalarization problems for a certain set of weights. We prove correctness, the approximation quality and a bound on the running time of the algorithm, and, finally, we identify current research directions. This talk addresses an audience which is familiar with mathematical programming / operations research but not necessarily specialized in multiobjective optimization.
15h00 - 16h00
Hassene Aissi, University Paris Dauphine
Strongly polynomial algorithms for the parametric and multiobjective global minimum cut problem
We consider parametric and multiobjective versions of the global minimum cut problem in undirected graphs. For a fixed number of edge cost functions, we show that the combinatorial facet complexity of the problem is bounded by a polynomial in the numbers of nodes and edges. We sharpen this bound in the case of two objectives and derive a strongly polynomial upper bound on the total number of non-dominated (Pareto optimal) cuts. We also show that Karger's randomized contraction method (SODA 93) can be adapted to the global minimum cut problems with a constant number of edge or node budget constraints to give efficient algorithms.
16h00 - 16h20 Pause
16h20 - 17h20
Olivier Spanjaard, University Pierre Marie Curie
A Game-Theoretic View of Randomized Fair Multi-Agent Optimization
We tackle fair multi-agent optimization problems and use a generalized Gini index to determine a fair and efficient solution. We claim that considering mixed solutions (i.e., lotteries over solutions) enables to enhance the fairness of an optimal solution. Interpreting a fair multi-agent optimization problem as a zero-sum two-player game between an optimization player choosing a solution and an adversary which has some control over the payoffs of the game, we propose two methods (a cutting-plane method and a double oracle method) to compute an optimal mixed solution. Numerical tests are provided to compare their efficiency.
Joint work with Hugo Gilbert.