16e séminaire POC

SPOC 16 "Optimisation Combinatoire Multi-Objectif"

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
Liste des inscrits

1	Hassene	Aissi	LAMSADE - Université Dauphine
2	Zacharie	ALES	ENSTA / CEDRIC
3	Mourad	BAIOU	LIMOS - Université de Clermont-Ferrand
4	Cristina	Bazgan	Université Paris-Dauphine
5	Hajer	BEN FEKIH	Paris-Dauphine
6	Fatiha	Bendali	LIMOS-UCA
7	Pascale	Bendotti	EDF R&D - LIP6
8	Nadjet	BOURDACHE	Université Pierre et Marie Curie
9	Rachid	Chelouah	Univ Paris Seine/EISTI
10	Denis	Cornaz	Université Paris-Dauphine
11	hamdi	dkhil	Normandie université, Le Havre
12	Nicolas	Dupin	Dga
13	Imane	Fadloullah	Fst, USMBA, Fez, Morocco
14	Anne-Elisabeth	FALQ	LIP6-Université Pierre et Marie Curie
15	Pierre	FOUILHOUX	LIP6 - UMPC
16	Xavier	Gandibleux	Université de Nantes
17	Fatima	GHEDJATI	CReSTIC-Université de Reims
18	Laurent	Gourves	CNRS LAMSADE
19	Gabriel	Gouvine	Innovation24 LocalSolver
20	Antoine	Kerbérénès	Université Paris Dauphine
21	hossein	khani
22	MICHAEL	KIKOMBA KAHUNGU	INSTITUT SUPERIEUR DES TECHNIQUES APPLIQUEES DE KASANGULU
23	Arnaud	Knippel	INSA Rouen Normandie
24	ISAAC	KONAN	Université Paris Diderot
25	Meriem	Laradi	Paris 1 panthéon Sorbonne
26	A. Ridha	Mahjoub	LAMSADE - Université Dauphine
27	Jean	Mailfert	Limos-Université Clermont Auvergne
28	Sébastien	Martin	LCOMS-Université de Lorraine
29	Niezi	MHARSI	IMT -Telecom ParisTech
30	ALAIN	NGUYEN	RENAULT
31	Adèle	PASS-LANNEAU	LIP6 - UPMC
32	Pedro Henrique	Pereira Vargas Liguori	Paris Dauphine
33	Pierre	Pesneau	Université de Bordeaux, IMB
34	Thuy	Pham	Paticipant
35	Anthony	Przybylski	Université de Nantes
36	Cécile	Rottner	EDF R&D - LIP6
37	Stefan	Ruzika	University of Kaiserslautern
38	Olivier	SPANJAARD	LIP6 - UMPC
39	Alberto	Tonda	INRA
40	Daniel	Vanderpooten	LAMSADE Université Paris
41	Sonia	Vanier	Université ParisI Panthéon-Sorbonne
42	lizhi	wang	Grenoble INP G-SCOP
43	roberto	wolfler calvo	paris13

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.