|
|
|
Programme > TutorielsMercredi 6 Mars 2024 - 14h45-15h45 On identification problems in graphs: About hypergraph representations and polyhedral methods to solve such problems Several different types of identification problems in graphs have been actively studied in the literature, for instance the problems of finding identifying codes, locating total-dominating sets or open locating-dominating sets. Hereby, the objective is to separate any two vertices of a graph by their unique neighbourhoods in a suitably chosen dominating or total-dominating set, often referred to as a code, and to find such codes of minimum cardinality. In this tutorial, we will study such problems under a unifying point of view with the help of reformulations in terms of covering problems in suitably constructed hypergraphs. We show which properties and relations of the codes can be deduced by analyzing and comparing these hypergraphs. Moreover, we illustrate how general results on covering problems and polyhedral methods can be applied to solve the studied identification problems in several graph classes.
Annegret Wagler,
Mercredi 6 Mars 2024 - 14h45-15h45 Des puces à l’OR De nos jours, les puces sont présentes partout dans notre vie quotidienne, pour répondre à divers besoins : montres connectées, téléphones, véhicules autonomes, systèmes complexes de calcul à haute performance, santé, etc. Leur conception pose des problèmes d’optimisation spécifiques et difficiles à résoudre à la fois à cause d’une combinatoire importante et de critères nombreux et antagonistes. Le but de cet exposé à trois voix est de présenter trois problèmes liés à la conception de circuit, leur modélisation et leur résolution avec des outils de la recherche opérationnelle. Le premier problème présente la conception d’un circuit pipeliné pour évaluer en inférence un réseau de neurones à partir d’accélérateurs neuronaux paramétrables. Le second porte sur l’optimisation d’opérateurs arithmétiques, tels que la multiplication par plusieurs constantes, omniprésents en deep learning, crypto, traitement du signal, etc. Ici, l’objectif est de lier efficacité, en terme de mémoire, latence, énergie, et précision des calculs. Enfin, le troisième traite de la sécurité matérielle des circuits. Il s’agit d’optimiser l’insertion de contre mesures afin de verrouiller le circuit pour empêcher l’insertion de Chevaux de Troie Matériels ou encore la surproduction et la contrefaçon lors de la production. Les outils de théorie des graphes et programmation mathématiques ont permis de modéliser ce problème de sécurité et de proposer des stratégies de résolutions efficaces. Nous conclurons sur un ensemble de questions ouvertes, intégrant notamment la place de l’intelligence artificielle dans les démarches de conception.
Alix Munier Kordon, Laboratoire LIP6 CNRS 7606, Sorbonne Université
Mercredi 6 Mars 2024 - 15h45-16h45 Préférences structurées en décision collective : reconnaissance et complexité Les préférences structurées en décision collective sont étudiées depuis au moins les travaux Duncan Black (1948) sur les préférences unimodales en théorie du choix social. Du point de vue de l'algorithmicien, la reconnaissance de différents types de structures dans les préférences pose de nombreux problèmes intéressants. Ce sujet a fait l'objet de nombreux travaux depuis une quinzaine d'années, dans le domaine dit du choix social computationnel. Dans cet exposé, nous dresserons un bref panorama de ces travaux, en abordant la reconnaissance de structures, l'impact que cela peut avoir sur la complexité d'un problème de choix social, et des aspects liés à l'apprentissage de préférences.
Olivier Spanjaard
Mercredi 6 Mars 2024 - 15h45-16h45 Multiflots et multicoupes dans la conception de réseaux sous l'angle des travaux de Michel Minoux Dans ce tutoriel, nous rendons hommage à Michel Minoux, professeur au LIP6 et à Sorbonne Université (anciennement Université Pierre et Marie Curie Paris 6) jusqu'en Septembre 2023 à travers ses travaux sur les problèmes de conception et dimensionnement de réseaux sous les contraintes de multiflots. Nous rappelons les différents modèles de programmation mathématique (sommets-arcs, arcs-chemins,...) permettant de modéliser les contraintes de multiflots avec diverses formes pour la fonction de coût. Nous décrivons ensuite des contributions de Michel et ses co-auteurs pour la résolution exacte et approchée de ces problèmes notamment dans les cas où la fonctions de coût est concave non décroissante ou discrète. Par dualité, nous nous intéressons ensuite aux multicoupes caractérisant les solutions réalisables pour les problèmes de partionnement de graphes. Ces derniers avec des contraintes de capacités quadratiques ou de type sac-à-dos peuvent modéliser entre autres des problèmes de conception des réseaux optiques SONET/SDH ou des communications des processus dans les structures multicoeurs. Nous exposons des travaux de Michel et ses co-auteurs sur ces modèles, en particulier la linéarisation des contraintes quadratiques et la réduction des contraintes métriques. Nous terminons par évoquant un des derniers travaux de Michel publié de son vivant, sur une formulation étendue du problème de la coupe maximum.
Viet Hung Nguyen |
| Personnes connectées : 3 | Vie privée |
|
