Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$36,000.00

Constraint programming: models and algorithms

FY 2007-08

Summary
Constraint programming is a powerful framework for solving difficult problems. In the constraint programming methodology, one models a problem by stating constraints on acceptable solutions. Once a model has been formulated, various algorithms---usually based on search---are available for solving the model. There are many interesting tasks for which this approach is particularly suited. These tasks range from ones that are simple for humans, such as vision and language comprehension, to ones that are difficult for humans, such as scheduling and planning. What these tasks have in common is that constraints are a natural part of the problem. A good example is scheduling people or machines. What is readily available are constraints such as a worker is only available for certain parts of the week or only able to do certain jobs.I propose constraint programming research projects that fall within the solving stage. A key to improving many applications of constraint programming is to improve the underlying search algorithms. Much progress has been made recently, but more work remains to be done. I propose several projects for improving backtracking search, the most commonly used form of search for solving constraint models, as well as a project investigating an alternative to backtracking search. In addition to this more theoretical and experimental work, I propose to continue an application-driven research project on effectively solving real-world optimization problems. Focusing on applications has had the benefit of identifying shortcomings in existing constraint programming approaches as well as making a contribution to the practice of constraint programming.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
105446-2007
Name nom
VanBeek, Peter
Department département
Computer Science, School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2007
Competition year année de concours
2007
Award amount
36000
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2803
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Knowledge representation
Research subject fr
Répresentation des connaissances
Partie
1
Nb partie
5
Application title
Constraint programming: models and algorithms
Keyword
NA
Application summary
Constraint programming is a powerful framework for solving difficult problems. In the constraint programming methodology, one models a problem by stating constraints on acceptable solutions. Once a model has been formulated, various algorithms---usually based on search---are available for solving the model. There are many interesting tasks for which this approach is particularly suited. These tasks range from ones that are simple for humans, such as vision and language comprehension, to ones that are difficult for humans, such as scheduling and planning. What these tasks have in common is that constraints are a natural part of the problem. A good example is scheduling people or machines. What is readily available are constraints such as a worker is only available for certain parts of the week or only able to do certain jobs.I propose constraint programming research projects that fall within the solving stage. A key to improving many applications of constraint programming is to improve the underlying search algorithms. Much progress has been made recently, but more work remains to be done. I propose several projects for improving backtracking search, the most commonly used form of search for solving constraint models, as well as a project investigating an alternative to backtracking search. In addition to this more theoretical and experimental work, I propose to continue an application-driven research project on effectively solving real-world optimization problems. Focusing on applications has had the benefit of identifying shortcomings in existing constraint programming approaches as well as making a contribution to the practice of constraint programming.