Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$26,000.00
Design of generic and robust search heuristic in constraint programming to solve practical combinatorial problems
EF 2011-12
Résumé
This research program aims to develop new algorithms for improved computerized methods to solve complex
planning problems that occur in a number of areas of human activity, with important economic and social
impacts. Examples of such problems are employee scheduling, sports scheduling, telecommunications design,
and transportation logistics. The concrete combinatorial problems encountered in these areas are reputedly very
difficult to solve in a satisfactory manner.
Constraint Programming is a powerful technique to solve combinatorial problems. It applies sophisticated
inference to reduce the search space but, to date, lacks a generic and robust search heuristic. This
puts the latter technology at a disadvantage in terms of ease of use even though its modeling flexibility is an
asset to address realistic industrial problems.
Global constraints have played a central role in Constraint Programming because they capture key
substructures of a problem and efficiently exploit them to boost inference. This research project proposes doing
the same thing for search. Whereas most generic dynamic search heuristics in constraint programming rely on
information at the fine-grained level of individual variables, we investigate dynamic
search heuristics based on coarser, but more global, information. The search heuristics proposed revolve
around the knowledge of the number of solutions for individual constraints, the intuition being that a constraint
with few solutions corresponds to a critical part of the problem with respect to satisfiability.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
218028-2007
Name nom
Pesant, Gilles
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
2011
Competition year année de concours
2007
Award amount
26000
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
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
5
Nb partie
5
Application title
Design of generic and robust search heuristic in constraint programming to solve practical combinatorial problems
Keyword
NSERC
Application summary
This research program aims to develop new algorithms for improved computerized methods to solve complex
planning problems that occur in a number of areas of human activity, with important economic and social
impacts. Examples of such problems are employee scheduling, sports scheduling, telecommunications design,
and transportation logistics. The concrete combinatorial problems encountered in these areas are reputedly very
difficult to solve in a satisfactory manner.
Constraint Programming is a powerful technique to solve combinatorial problems. It applies sophisticated
inference to reduce the search space but, to date, lacks a generic and robust search heuristic. This
puts the latter technology at a disadvantage in terms of ease of use even though its modeling flexibility is an
asset to address realistic industrial problems.
Global constraints have played a central role in Constraint Programming because they capture key
substructures of a problem and efficiently exploit them to boost inference. This research project proposes doing
the same thing for search. Whereas most generic dynamic search heuristics in constraint programming rely on
information at the fine-grained level of individual variables, we investigate dynamic
search heuristics based on coarser, but more global, information. The search heuristics proposed revolve
around the knowledge of the number of solutions for individual constraints, the intuition being that a constraint
with few solutions corresponds to a critical part of the problem with respect to satisfiability.