Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Windsor

$29,000.00

Satisfiability Checking and Computer Algebra: A Powerful New Search Method

FY 2024-25

Summary
Fast search algorithms are at the heart of effective solutions to a huge number of industrial and theoretical problems-from search engines to resource allocation to mathematical conjecture verification. Some of the most effective general-purpose search techniques come from the field of satisfiability (SAT) checking. Indeed, programs called SAT solvers that search for solutions to logic problems are extremely effective at solving many kinds of search and optimization problems that arise in practice-though they tend to struggle with mathematically complex problems. In these kinds of problems it is typical to either use a computer algebra system (CAS) or a "SAT modulo theories" (SMT) solver which offer support for more complex mathematics. However, there are many problems that require both sophisticated mathematics (beyond what SAT or SMT solvers offer) and fast search routines (beyond what CASs offer). This proposal aims to advance a new mathematical search paradigm that exploits both the search power of SAT solvers and the mathematical capabilities of CASs-thereby achieving the best in both the worlds of satisfiability checking and computer algebra. This "SAT+CAS" method is still in its infancy but has shown great promise in a number of preliminary results over the last few years. This research grant will support extending the SAT+CAS method to a wider variety of problems, including those from new kinds of domains. The ultimate goal of this research is to make the SAT+CAS method one of the most effective methods-if not the most effective method-for tackling general mathematical search problems. As one example, consider the problem of testing samples for the presence of a virus. The most basic method is simply to test each sample individually, but this is costly. A more efficient strategy is to employ "pooled testing" where multiple samples are tested together. By judiciously choosing which samples to combine together one can develop testing schemes which are essentially as quick and accurate as the basic method but require significantly fewer tests. For example, disjunct matrices are combinatorial matrices that give rise to good pooling schemes. Optimal disjunct matrices are known to exist once the size of the matrices are large enough, but these can be too large for many applications. However, by extending the SAT+CAS method into the domain of combinatorial group testing we can search for new disjunct matrices-and therefore new pooling schemes. These could be useful to facilitate continuous testing for viruses like COVID-19, especially in regions where the medical system is being pushed to its limits. The SAT+CAS method is perfectly positioned to attack such problems and the time is ripe to exploit the advances made by SAT solvers and CASs in order to solve problems previously considered infeasible.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2021-03089
Name nom
Bright, Curtis
Department département
School of Computer Science
Organization id
37
Institution établissement
University of Windsor
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2021
Award amount
29000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
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
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Satisfiability Checking and Computer Algebra: A Powerful New Search Method
Keywords
satisfiability checking; computer algebra; search algorithms; discrete mathematics; conjecture verification; counterexample generation; symbolic computation
Application summary
Fast search algorithms are at the heart of effective solutions to a huge number of industrial and theoretical problems-from search engines to resource allocation to mathematical conjecture verification. Some of the most effective general-purpose search techniques come from the field of satisfiability (SAT) checking. Indeed, programs called SAT solvers that search for solutions to logic problems are extremely effective at solving many kinds of search and optimization problems that arise in practice-though they tend to struggle with mathematically complex problems. In these kinds of problems it is typical to either use a computer algebra system (CAS) or a "SAT modulo theories" (SMT) solver which offer support for more complex mathematics. However, there are many problems that require both sophisticated mathematics (beyond what SAT or SMT solvers offer) and fast search routines (beyond what CASs offer). This proposal aims to advance a new mathematical search paradigm that exploits both the search power of SAT solvers and the mathematical capabilities of CASs-thereby achieving the best in both the worlds of satisfiability checking and computer algebra. This "SAT+CAS" method is still in its infancy but has shown great promise in a number of preliminary results over the last few years. This research grant will support extending the SAT+CAS method to a wider variety of problems, including those from new kinds of domains. The ultimate goal of this research is to make the SAT+CAS method one of the most effective methods-if not the most effective method-for tackling general mathematical search problems. As one example, consider the problem of testing samples for the presence of a virus. The most basic method is simply to test each sample individually, but this is costly. A more efficient strategy is to employ "pooled testing" where multiple samples are tested together. By judiciously choosing which samples to combine together one can develop testing schemes which are essentially as quick and accurate as the basic method but require significantly fewer tests. For example, disjunct matrices are combinatorial matrices that give rise to good pooling schemes. Optimal disjunct matrices are known to exist once the size of the matrices are large enough, but these can be too large for many applications. However, by extending the SAT+CAS method into the domain of combinatorial group testing we can search for new disjunct matrices-and therefore new pooling schemes. These could be useful to facilitate continuous testing for viruses like COVID-19, especially in regions where the medical system is being pushed to its limits. The SAT+CAS method is perfectly positioned to attack such problems and the time is ripe to exploit the advances made by SAT solvers and CASs in order to solve problems previously considered infeasible.
University of Windsor - $29,000 Grant (2024-25) | Canada Spends