Séminaire Sebastien Martin

Jeudi 05 Avril 2012 (14h00)

Sebastien Martin, Laboratoire LAMSADE, Université Paris Dauphine.

Titre : Systèmes algébro-différentiels et optimisation combinatoire.

Résumé : Les systèmes algébro-différentiels permettent de modéliser des systèmes physiques complexes comme les circuits électriques et les mouvements dynamiques. Ils sont souvent de grande taille et difficiles à résoudre.
Dans un premier temps, nous étudions le problème de l'analyse structurelle des systèmes algébro-différentiels conditionnels.

Ce problème permet de vérifier si un tel système ne pourra pas être résolu par des méthodes numériques. Nous montrons que ce problème est équivalent au problème du sous-graphe sans couplage parfait. Nous montrons que ce dernier est NP-difficile. Nous proposons une formulation en termes de graphes et une formulation en nombres entiers pour ce problème. Nous étudions le polyèdre associé et décrivons plusieurs classes de contraintes valides. Nous donnons des conditions nécessaires et suffisantes pour que ces contraintes définissent des facettes. Nous discutons également d'algorithmes de séparation pour ces contraintes et en utilisant ces résultats, nous développons un algorithme de coupes et branchements. Nous étudions aussi une extension de ce problème pour les systèmes algébro-différentiels conditionnels imbriqués. Nous étendons la plupart des résultats précédent à ce cas. Nous identifions de nouvelles contraintes valides pour cette variante du problème.
Dans une deuxième partie, nous nous intéressons au problème de parallélisation des systèmes algébro-différentiels. Ce problème se ramène au problème du séparateur. Nous proposons une formulation en nombres entiers et nous étudions le polyèdre associé. Nous proposons quelques résultats expérimentaux obtenus suite à cette étude.
Ce travail a été réalisé en collaboration avec M. Lacroix et R. Mahjoub..