Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

École Polytechnique de Montréal

$20,000.00

Métaheuristiques pour l'optimisation difficile

EF 2012-13

Résumé
Les problèmes d'optimisation combinatoire sont omniprésents, notamment dans les applications. Cependant, un grand nombre de ces problèmes, sinon la plupart, sont difficiles (problèmes NP-difficiles). Même en utilisant les meilleurs algorithmes exacts existants (de complexité exponentielle), la résolution des exemplaires de grande taille de tels problèmes nécessite malheureusement un temps de calcul prohibitif. Pour traiter ces exemplaires, il est nécessaire de recourir à des heuristiques, c'est-à-dire des techniques algorithmiques qui fournissent en un temps réduit des solutions aussi bonnes que possible, mais sans garantie d'optimalité. On appelle métaheuristique un schéma d'heuristique générique (i.e. applicable à de nombreux problèmes). Le premier objectif du programme de recherche proposé consiste à développer des métaheuristiques pour la résolution efficace de problèmes académiques issus de la théorie des graphes (partitionnement, appariement approximatif, feedback set) et des mathématiques combinatoires (covering design). Notre deuxième objectif vise à développer des métaheuristiques pour la résolution efficace de problèmes réels de grande taille issus du génie logiciel et des télécommunications. Ces travaux seront réalisés en collaboration avec des experts de ces domaines. Notre troisième objectif consiste à développer notre approche novatrice qui utilise des heuristiques afin de détecter (extraire) un sous-ensemble irréalisable de contraintes (IIS) dans un CSP irréalisable. Nous développerons de nouveaux algorithmes de détection d'IIS plus rapides et plus puissants, et nous appliquerons nos algorithmes à de nouveaux problèmes.
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
251139-2011
Name nom
Galinier, Philippe
Department département
Génie informatique et génie logiciel
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
2012
Competition year année de concours
2011
Award amount
20000
Program id
RGPIN
Program name 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
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
9999
Area of application group en
Not available
Area of application group fr
Non disponible
Area of application en
Not available
Area of application fr
Non disponible
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
2
Nb partie
5
Application title
Métaheuristiques pour l'optimisation difficile
Keyword
NSERC
Application summary
Les problèmes d'optimisation combinatoire sont omniprésents, notamment dans les applications. Cependant, un grand nombre de ces problèmes, sinon la plupart, sont difficiles (problèmes NP-difficiles). Même en utilisant les meilleurs algorithmes exacts existants (de complexité exponentielle), la résolution des exemplaires de grande taille de tels problèmes nécessite malheureusement un temps de calcul prohibitif. Pour traiter ces exemplaires, il est nécessaire de recourir à des heuristiques, c'est-à-dire des techniques algorithmiques qui fournissent en un temps réduit des solutions aussi bonnes que possible, mais sans garantie d'optimalité. On appelle métaheuristique un schéma d'heuristique générique (i.e. applicable à de nombreux problèmes). Le premier objectif du programme de recherche proposé consiste à développer des métaheuristiques pour la résolution efficace de problèmes académiques issus de la théorie des graphes (partitionnement, appariement approximatif, feedback set) et des mathématiques combinatoires (covering design). Notre deuxième objectif vise à développer des métaheuristiques pour la résolution efficace de problèmes réels de grande taille issus du génie logiciel et des télécommunications. Ces travaux seront réalisés en collaboration avec des experts de ces domaines. Notre troisième objectif consiste à développer notre approche novatrice qui utilise des heuristiques afin de détecter (extraire) un sous-ensemble irréalisable de contraintes (IIS) dans un CSP irréalisable. Nous développerons de nouveaux algorithmes de détection d'IIS plus rapides et plus puissants, et nous appliquerons nos algorithmes à de nouveaux problèmes.