Grant: Discovery Grants Program - Individual
Simon Fraser University
$24,000.00
Exploiting Structure in Satisfiability-Based Problem Solving
FY 2017-18
Summary
Challenging combinatorial problems, including many optimization problems, arise in almost all areas of science, engineering and business, and applied computer science. A particular approach to software for solving these problems, sometimes called satisfiability-based or constraint-based problem solving, provides workers facing such problems with a model-and-solve capability. Users who are not experts in combinatorial problem solving need only describe their problem in a high-level, declarative, specification language to obtain solutions. Technology based on this approach is very new, but is being shown highly effective for a growing range of problems. This research aims to address two important limitations of the current technology. One is that it is unknown how to adapt the solving algorithms at the core of this technology to exploit very high performance hardware which can be expected in the next decade, involving either very large numbers of compute cores and possibly adiabatic quantum annealing processors. The second is that there is a wide range of problems for which the most effective algorithms are known as dynamic programming algorithms, but mode-and-solve technologies do not exploit this. While of a different nature, both of these problems may be addressed in part by general methods which exploit particular structural properties of problem instances. Taking advantage of these properties in practice, though, required new theory and algorithms, which are the subject of this project.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2015-05855
Name nom
Mitchell, David
Department département
Computing Science, School of - Computing Science, School of
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2015
Award amount
24000
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
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2800
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Artificial intelligence (computer vision, use2603)
Research subject fr
Intelligence artificielle (vision artificielle, utiliser 2603)
Partie
3
Nb partie
5
Application title
Exploiting Structure in Satisfiability-Based Problem Solving
Keyword
NSERC
Application summary
Challenging combinatorial problems, including many optimization problems, arise in almost all areas of science, engineering and business, and applied computer science. A particular approach to software for solving these problems, sometimes called satisfiability-based or constraint-based problem solving, provides workers facing such problems with a model-and-solve capability. Users who are not experts in combinatorial problem solving need only describe their problem in a high-level, declarative, specification language to obtain solutions. Technology based on this approach is very new, but is being shown highly effective for a growing range of problems. This research aims to address two important limitations of the current technology. One is that it is unknown how to adapt the solving algorithms at the core of this technology to exploit very high performance hardware which can be expected in the next decade, involving either very large numbers of compute cores and possibly adiabatic quantum annealing processors. The second is that there is a wide range of problems for which the most effective algorithms are known as dynamic programming algorithms, but mode-and-solve technologies do not exploit this. While of a different nature, both of these problems may be addressed in part by general methods which exploit particular structural properties of problem instances. Taking advantage of these properties in practice, though, required new theory and algorithms, which are the subject of this project.