Canada Spends Logo

Explore our Budget 2026 analysis

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

FY 2009-10

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.
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

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
2009
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
3
Nb partie
5
Application title
Design of generic and robust search heuristic in constraint programming to solve practical combinatorial problems
Keyword
NA
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.