Accelerated solution of constraint satisfaction problems by partitioning of the variable space
US7409377B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 29, 2005 |
| Grant date | Aug 5, 2008 |
| Priority date | — |
| Expiry date | Aug 10, 2025 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06N20/00
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Methods, systems and apparatus for modeling a target system includes defining a constraint satisfaction problem (CSP) that characterizes the target system in terms of a set of variables, each having a respective input domain, and initial constraints applicable to the variables. The variables are partitioned into at least first and second sets. An abstract solution is found to the CSP, including a given assignment of the variables in the first set. A reduced domain of at least one of the variables in the second set is computed, so as to be compatible with the abstract solution. A redundant constraint on the abstract solution is determined responsively to the reduced domain. A concrete solution to the CSP is then found, using the abstract solution and the redundant constraint.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.