Journée "Hors les Murs" 15/12/20
Journée "Hors les Murs" du Mardi 15 décembre 2020
- Horaires, Liens visio et autres infos
- Listes des exposés
- Participants à la journée (n'hésitez pas à écrire Pierre pour vous ajouter)
Liens visios et autres infos
La "journée" est une après-midi qui commence à 14h.
Les exposés seront sur l'outil zoom
https://zoom.us/j/99901068463?pwd=ODg2Q2VTNitHL3pEc0hOZTd4ekdvQT09
ID de réunion : 999 0106 8463
Code secret : POCPOC
Pour discuter de manière informelle par 2 ou 3 ou par petits groupes, essayons l'outil ludique et très intuitif
https://gather.town/app/ZaWPK0bn987RdLTG/Reunion_POC
https://gather.town/app/ZaWPK0bn987RdLTG/Reunion_POC
Exposés de l'après-midi
14:00
A Branch-and-Cut algorithm for solving the multi-commodity flow blocker problem:
Isma BENTOUMI
Doctorante au LAMSADE(Université Paris-Dauphine) et au centre de recherche de HUAWEI, encadré par Ridha Mahjoub, Fabio Furini et Sébastien Martin
In telecommunication networks, to evaluate the resilience of a network, a relevant parameter is the maximum number of simultaneous failures that it can face. This can be seen as a bi-level optimization problem constituting the multi-commodity flow blocker problem. We present an ILP formulation associated with a Branch-and-cut algorithm to solve this problem. We also develop a polyhedral analysis of the proposed model
14:20
Two approaches to solve a particular bilevel problem
Martina CERULLI
doctorante au LIX, CNRS Ecole Polytechnique, encadré par Claudia d'Ambrosio et Leo Liberti
doctorante au LIX, CNRS Ecole Polytechnique, encadré par Claudia d'Ambrosio et Leo Liberti
We propose two different approaches to solve a particular bilevel program with a quadratic lower level: one is based on a dual reformulation of the lower level problem (which can lead to a convex or a semidefinite programming problem depending on the parametrization of the lower level w.r.t. the upper level variables), and the other is a Cutting Plane Algorithm. This is an ongoing work.
Joint work with Antoine Oustry
14:40
Polyhedral Investigation and Branch-and-Cut for the Constrained-Routing and Spectrum Assignment Problem in Spectrally Flexible Optical Networks
Youssouf HADHBI
doctorant au LIMOS (Université de Clermont-Ferrand-Auvergne), encadré par A. Ridha Mahjoub et Ibrahima Diarrassouba.
Présentation en pdf
15:00 - PAUSE - Pensez à utiliser l'outil https://gather.town/app/ZaWPK0bn987RdLTG/Reunion_POC
15:20
A cycle-based formulation for the Distance Geometry Problem"
Gabriele IOMMAZZO
doctorant au LIX, CNRS, Ecole Polytechnique et université de Pise, encadré par Leo Liberti
The distance geometry problem consists in finding a realization of a weighed graph in a Euclidean space of given dimension, where the edges are realized as straight segments of length equal to the edge weight. We propose and test a new mathematical programming formulation based on the incidence between cycles and edges in the given graph.
15:40
Formulations pour le problème du plus grand sous graphe commun
Etienne MACE de GASTINES
doctorant à l'INSA de Rouen, encadré par Arnaud Knippel
Soit G et H deux graphes. Le problème du plus grand sous-graphe commun consiste à déterminer un sous-graphe (non-induit) maximal en nombre d'arêtes, commun à G et H. Ce problème a été posé par S. Bokhari en 1981 pour résoudre l'affectation de processus dans des architectures parallèles, en maximisant la demande de communication entre les processus. Ce problème est également intéressant d'un point de vue théorique car il généralise des problèmes classiques de théorie des graphes (isomorphisme de graphe, clique maximale, chemins hamiltoniens, isomorphisme de sous-graphe). Nous proposons de nouvelles formulations et les comparons avec les formulations précédentes de la littérature.
16:00
Conception multi-objective de réseaux et polyèdre
Charles NOURY
doctorant au LAMSADE (Université Paris-Dauphine), encadré par A.Ridha Mahjoub et Hassene Aissi.
Dans cette thèse, nous nous intéressons à la résolution exacte de certains problèmes de conception de réseaux auxquels on ajoute plusieurs contraintes de budget, celles-ci sont formulées sous la forme d'inégalités de sac à dos. Nous étudions ces problèmes avec une approche basée sur la programmation mathématiques, ces contraintes de ressources vont modifier la structure des polyhèdres associés aux problèmes de réseaux. L'objectif principal de notre travail est de comprendre ces nouvelles descriptions, trouver des inégalités valides, facettes et formulations étendues afin de concevoir des algorithmes de branchements efficaces pour résoudre nos problèmes de réseaux budgettés.
Nous étudions actuellement le problème de l'arbre couvrant de poids min avec des contraintes de budgets. On retrouve ce type de problème aussi bien dans la pratique que comme sous-problème de certaines décompositions. Le problème de l'arbre couvrant classique peut être résolu en temps polynomial, cependant en ajoutant une contrainte de budget, le problème devient faiblement NP-difficile et devient NP-difficile au sens fort à partir de deux contraintes de ressources. Dans un premier temps, nous avons comparé l'impact des contraintes de budgets sur différentes formulations connues de l'arbre couvrant. Nous avons étudié des propriétés polyhédrales; cas particuliers, relaxation, inégalités valides et dimension du problème dans le cas d’une contrainte de budget. Dans un second temps, nous analysons plusieurs formulations étendues, ainsi qu'une approche basée sur les matroids et le théorème d’intersection d'Edmonds.
16:20 - PAUSE - Pensez à utiliser l'outil https://gather.town/app/ZaWPK0bn987RdLTG/Reunion_POC
16:40
The Benders by batch algorithm: design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs
Xavier BLANCHOT (après 16h)
doctorant, Inria Bordeaux / RTE, encadré par Francois Clautiaux et Boris Detienne.
We present in this talk a new algorithm to solve linear two-stage stochastic programs. We propose to solve only a few number of subproblems at each iteration, and develop and simple and exact framework thanks to the multicut formulation of Benders decomposition. We propose three primal stabilization methods for the algorithm and perform an extensive computational study on six large-scale benchmarks of stochastic optimization literature.
17:00
Optimisation robuste pour le fonctionnement automatisé des pompes dans les réseaux d'eau
David WU
doctorant au LIP6 et à Energisme, encadré par Michel Minoux, Viet Hung Nguyen et Haï Tran
17:20
Etude polyédrale du problème de la bond maximale
Alexandre DUPONT-BOUILLARD (après 17h)
doctorant au LIPN, Université Sorbonne Paris Nord, encadré par Pierre Fouilhoux, Roland Grappe et Mathieu Lacroix
Considèrons un graphe connexe G. Une bond est une coupe de G qui est minimale au sens de l'inclusion. De manière équivalente, une bon est une coupe dont la suppression dans G laisse deux composantes connexes. Nous proposons une étude polyédrale en variables naturelles associées aux arêtes de G. Nous proposons des inégalités valides associés à des graphes complets ou planaires.
17:40 - Fin de la journée POC:
18:00 - Réunion de l'équipe d'animation POC sur l'outil zoom
L'outil https://gather.town/app/ZaWPK0bn987RdLTG/Reunion_POC reste à votre disposition pour continuer à discuter!
- Hassene Aissi
- Zacharie Ales
- Amal Benhamiche
- Fatiha Bendali-Mailfert
- Isma Bentoumi
- Xavier Blanchot
- François Clautiaux (à partir de 15h30/16h)
- Martina Cerulli
- Morgan Chopin
- Alexandre Dupont Bouillard (à partir de 17h)
- Maxime Dupuy
- Mauro Escobar
- Pierre Fouilhoux
- Youssouf Hadhbi
- Gabriele Iommazzo
- Sammy Khalife
- Mathieu Lacroix
- Leo Liberti
- A. Ridha Mahjoub
- Jean Mailfert
- Sébastien Martin
- Jean-François Maurras
- Moustafa Nakechbandi
- Viet Hung Nguyen
- Charles Nourry
- Antoine Oustry
- Pierre Pesneau (à partir de 14h30~15h)
- Daniel Porumbel
- Cécile Rottner (après 16h)
- Mamane Souleye Ibrahim
- Raouia Taktak
- Sonia Vanier
- David Wu
- Liding Xu