Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Université du Québec à Montréal

$17,000.00

Problèmes théoriques et pratiques en optimisation combinatoire

EF 2008-09

Résumé
Ma recherche porte sur des modèles mathématiques de systèmes complexes et sur les méthodes permettant de trouver des solutions optimales pour ces systèmes. Par exemple, un problème de transport important (appelé le MDVSP) consiste à partitionner un ensemble de tâches en tournées de véhicules, c'est-à-dire en suites de tâches pouvant être effectuées par un seul véhicule partant d'un garage et y retournant. L'objectif du MDVSP est de trouver une partition de coût minimal. Le MDVSP et des problèmes semblables peuvent être formulés à l'aide d'équations et d'inéquations, et leur objectif représenté par une fonction linéaire. Le but de ma recherche est alors de décrire des méthodes efficaces permettant de calculer la meilleure solution possible d'un modèle formé par des relations mathématiques. D'autre part, je m'intéresse au problème du partitionnement d'un ensemble de magasins en sous-groupes. Supposons qu'une compagnie doive répartir sa production entre des magasins et choisir des entrepôts d'où la production sera écoulée vers les magasins, en fonction de certains critères. Comme dans le cas précédent, ce problème peut être formulé à l'aide de relations (linéaires ou non) et résolu par plusieurs méthodes dont l'efficacité doit être évaluée. J'étudie aussi le problème d'affectation de fréquences, qui consiste à trouver une affectation de fréquences aux cellules d'un réseau téléphonique de telle sorte que l'interférence soit minimisée. Le problème d'affectation de fréquences ressemble au problème de coloration des sommets d'un graphe, et de façon générale, les problèmes décrits ci-dessus ont des liens étroits avec la théorie des graphes et la théorie des polytopes, deux sujets auxquels j'ai apporté ma contribution. En particulier, j'ai déterminé le nombre minimal de couleurs nécessaires pour colorier les arêtes d'un multigraphe lorsque celui-ci ne contient pas certaines structures "interdites". Finalement, un des buts de mes recherches est de décrire certains polytopes à l'aide d'inégalités linéaires. Un polytope est l'enveloppe convexe de tous les vecteurs représentant les solutions potentielles d'un problème donné.
Programme
Discovery Grants Program - Individual
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
9126-2007
Name nom
Marcotte, Odile
Department département
Informatique
Organization id
57
Institution établissement
Université du Québec à Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2008
Competition year année de concours
2007
Award amount
17000
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
20
Committee name en
Industrial Engineering
Committee name fr
Génie industriel
Area of application code
700
Area of application group en
Transportation systems and services
Area of application group fr
Services et systèmes de transport
Area of application en
Transportation systems and services
Area of application fr
Services et systèmes de transport
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Partie
2
Nb partie
3
Application title
Problèmes théoriques et pratiques en optimisation combinatoire
Keyword
NA
Application summary
Ma recherche porte sur des modèles mathématiques de systèmes complexes et sur les méthodes permettant de trouver des solutions optimales pour ces systèmes. Par exemple, un problème de transport important (appelé le MDVSP) consiste à partitionner un ensemble de tâches en tournées de véhicules, c'est-à-dire en suites de tâches pouvant être effectuées par un seul véhicule partant d'un garage et y retournant. L'objectif du MDVSP est de trouver une partition de coût minimal. Le MDVSP et des problèmes semblables peuvent être formulés à l'aide d'équations et d'inéquations, et leur objectif représenté par une fonction linéaire. Le but de ma recherche est alors de décrire des méthodes efficaces permettant de calculer la meilleure solution possible d'un modèle formé par des relations mathématiques. D'autre part, je m'intéresse au problème du partitionnement d'un ensemble de magasins en sous-groupes. Supposons qu'une compagnie doive répartir sa production entre des magasins et choisir des entrepôts d'où la production sera écoulée vers les magasins, en fonction de certains critères. Comme dans le cas précédent, ce problème peut être formulé à l'aide de relations (linéaires ou non) et résolu par plusieurs méthodes dont l'efficacité doit être évaluée. J'étudie aussi le problème d'affectation de fréquences, qui consiste à trouver une affectation de fréquences aux cellules d'un réseau téléphonique de telle sorte que l'interférence soit minimisée. Le problème d'affectation de fréquences ressemble au problème de coloration des sommets d'un graphe, et de façon générale, les problèmes décrits ci-dessus ont des liens étroits avec la théorie des graphes et la théorie des polytopes, deux sujets auxquels j'ai apporté ma contribution. En particulier, j'ai déterminé le nombre minimal de couleurs nécessaires pour colorier les arêtes d'un multigraphe lorsque celui-ci ne contient pas certaines structures "interdites". Finalement, un des buts de mes recherches est de décrire certains polytopes à l'aide d'inégalités linéaires. Un polytope est l'enveloppe convexe de tous les vecteurs représentant les solutions potentielles d'un problème donné.