Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$42,000.00
La théorie des graphes : analyse structurelle, algorithmique et applications dans les sciences de l'ingénieur
FY 2023-24
Summary
Mes projets de recherche sont multiples et complémentaires. Ils vont de la recherche fondamentale en théorie des graphes au développement d'algorithmes efficaces pour la résolution de problèmes industriels qu'on peut modéliser à l'aide des graphes. Ces projets sont regroupés en 3 thèmes qui visent un objectif commun : exploiter les graphes pour aider les industriels dans leurs prises de décision. 1er thème. Théorie extrémale Un invariant de graphe est une quantité qui ne dépend pas de la représentation de ce graphe. L'étude des invariants procure des connaissances structurelles, ce qui permet de mieux guider des algorithmes d'optimisation ou de concevoir des réseaux particuliers. Ce type d'analyse s'est avéré utile, par exemple dans la compréhension de structures moléculaires et l'étude de la vulnérabilité des réseaux. Le 1er thème de ma proposition de recherche consiste à déterminer des bornes serrées sur plusieurs invariants et à caractériser les graphes qui atteignent ces valeurs extrémales. 2ème thème. Systèmes de recommandation Un ensemble W de sommets est résolvant si la liste des distances de n'importe quel sommet du graphe à ceux de W permet d'identifier ce sommet de manière unique. Les hypercubes ont des ensembles résolvants de très petite taille, ce qui est utile pour les systèmes de recommandation. En effet, lorsque les produits recommandés sont caractérisés par des attributs booléens, on peut représenter chaque produit et chaque utilisateur d'un système de recommandation à l'aide d'un sommet dans un hypercube. Le score attribué à un produit évalué peut être traduit en termes de distance dans l'hypercube et la connaissance de ces scores permet ainsi de localiser un utilisateur de manière unique dans le graphe et donc de connaître ses préférences. Mon 2ème thème de recherche vise à exploiter les ensembles résolvants des hypercubes pour créer des systèmes de recommandation performants. 3ème thème. Conception et optimisation de réseaux Les graphes sont des modèles naturels en logistique et en télécommunication. Je vais m'atteler à résoudre deux problèmes posés par des partenaires industriels. Le 1er en est un de distribution de biens avec transferts de marchandises : l'acheminement de chaque unité de demande peut être effectué par plusieurs camions qui effectuent alors des transferts de marchandise en cours de route. Ces transferts nécessitent une synchronisation des parcours des camions. Le 2ème problème traité en sera un de conception de réseau dans un contexte d'intervention d'urgence où des secouristes doivent mettre en place leur propre réseau de télécommunication, le but étant de maximiser le débit le plus faible du réseau. Mes recherches procureront des outils d'aide à la décision à divers acteurs de notre société, que ce soit dans le secteur public ou privé. Les étudiants impliqués dans ces travaux seront confrontés à des problèmes industriels, ce qui leur ouvrira d'excellentes perspectives d'emploi à la fin de leurs études.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2023-03349
Name nom
Hertz, Alain
Department département
MAGI
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2023
Award amount
42000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Operations research and management science
Research subject en
Génie industriel
Research subject fr
Recherche opérationnelle et science de la gestion
Application title
La théorie des graphes : analyse structurelle, algorithmique et applications dans les sciences de l'ingénieur
Keyword
Algorithmique; Design de réseaux de transport et de télécommunication; Invariants de graphes; Optimisation combinatoire; Systèmes de recommandation; Théorie des graphes; Théorie extrémale
Application summary
Mes projets de recherche sont multiples et complémentaires. Ils vont de la recherche fondamentale en théorie des graphes au développement d'algorithmes efficaces pour la résolution de problèmes industriels qu'on peut modéliser à l'aide des graphes. Ces projets sont regroupés en 3 thèmes qui visent un objectif commun : exploiter les graphes pour aider les industriels dans leurs prises de décision. 1er thème. Théorie extrémale Un invariant de graphe est une quantité qui ne dépend pas de la représentation de ce graphe. L'étude des invariants procure des connaissances structurelles, ce qui permet de mieux guider des algorithmes d'optimisation ou de concevoir des réseaux particuliers. Ce type d'analyse s'est avéré utile, par exemple dans la compréhension de structures moléculaires et l'étude de la vulnérabilité des réseaux. Le 1er thème de ma proposition de recherche consiste à déterminer des bornes serrées sur plusieurs invariants et à caractériser les graphes qui atteignent ces valeurs extrémales. 2ème thème. Systèmes de recommandation Un ensemble W de sommets est résolvant si la liste des distances de n'importe quel sommet du graphe à ceux de W permet d'identifier ce sommet de manière unique. Les hypercubes ont des ensembles résolvants de très petite taille, ce qui est utile pour les systèmes de recommandation. En effet, lorsque les produits recommandés sont caractérisés par des attributs booléens, on peut représenter chaque produit et chaque utilisateur d'un système de recommandation à l'aide d'un sommet dans un hypercube. Le score attribué à un produit évalué peut être traduit en termes de distance dans l'hypercube et la connaissance de ces scores permet ainsi de localiser un utilisateur de manière unique dans le graphe et donc de connaître ses préférences. Mon 2ème thème de recherche vise à exploiter les ensembles résolvants des hypercubes pour créer des systèmes de recommandation performants. 3ème thème. Conception et optimisation de réseaux Les graphes sont des modèles naturels en logistique et en télécommunication. Je vais m'atteler à résoudre deux problèmes posés par des partenaires industriels. Le 1er en est un de distribution de biens avec transferts de marchandises : l'acheminement de chaque unité de demande peut être effectué par plusieurs camions qui effectuent alors des transferts de marchandise en cours de route. Ces transferts nécessitent une synchronisation des parcours des camions. Le 2ème problème traité en sera un de conception de réseau dans un contexte d'intervention d'urgence où des secouristes doivent mettre en place leur propre réseau de télécommunication, le but étant de maximiser le débit le plus faible du réseau. Mes recherches procureront des outils d'aide à la décision à divers acteurs de notre société, que ce soit dans le secteur public ou privé. Les étudiants impliqués dans ces travaux seront confrontés à des problèmes industriels, ce qui leur ouvrira d'excellentes perspectives d'emploi à la fin de leurs études.