# US 2008/0189230 A1 · Determining compliance rates for probabilistic requests > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2008/0189230 A1 - Document ID: US20080189230A1 - Status: Published application - Kind: A1 - Application number: 12/062,319 - Filed: 2008-04-03 - Published: 2008-08-07 - Earliest claimed: 2006-05-18 - Assignees: International Business Machines Corporation - Inventors: Shady Copty; Roy Emek; Itai Jaeger; Yoav Katz; Shai Lubliner - Web page: https://patentgrep.com/patent/US20080189230A1 ## CPC - G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks - G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## Abstract Systems and methods for solving a constraint satisfaction problem (CSP) defined by one or more variables, constraints and probabilistic requests (PRs) are provided. In one embodiment, each PR is mapped onto a set of constraints that implement the PR. The CSP solver then finds a series of solutions to the CSP. For each solution, if a constraint associated with a PR is satisfied, then a success counter for that PR is incremented; else a failure counter for that PR is incremented. If the constraint was not considered for the purpose of solving the CSP, then the failure counter for the PR associated with the constraint is incremented. ## Claims ### Claim 1 A method for determining compliance of one or more solutions with a probabilistic request submitted for solving a constraint satisfaction problem (CSP), wherein the CSP is defined by one or more variables and constraints such that the constraints define limitations for values that can be assigned to each variable in a given domain to solve the CSP, the method comprising: associating a first probabilistic request with a first constraint, wherein the first probabilistic request indicates that the first constraint is to be satisfied in a predefined percentage of the solutions; processing a first solution to determine whether the first constraint is satisfied by the first solution; and incrementing a success counter for the first probabilistic request, in response to determining that the first constraint is satisfied by the first solution. ### Claim 2 (depends on 1) The method of claim 1, further comprising incrementing a failure counter for the first probabilistic request, in response to determining that the first constraint is not satisfied by the first solution. ### Claim 3 (depends on 2) The method of claim 2, further comprising incrementing the failure counter for a second probabilistic request associated with the first constraint, in response to determining that the first constraint is irrelevant to the first solution. ### Claim 4 (depends on 1) The method of claim 1, further comprising reporting conformance rate for the first probabilistic request based on value of the success counter. ### Claim 5 (depends on 2) The method of claim 2, further comprising reporting conformance rate for the first probabilistic request based on value of the failure counter. ### Claim 6 (depends on 1) The method of claim 1, wherein value of the success counter is recorded in a data structure. ### Claim 7 (depends on 1) The method of claim 1, wherein value of the failure counter is recorded in a data structure. ### Claim 8 (depends on 6) The method of claim 6, wherein the value of the success counter is used to determine success rate of the first probabilistic request. ### Claim 9 (depends on 3) The method of claim 3, further comprising aggregating success/failure results for the first probabilistic request over multiples solutions to determine whether the first soft constraint is satisfied in said predefined percentage of the solutions. ### Claim 10 A system for determining compliance of one or more solutions with a probabilistic request submitted for solving a constraint satisfaction problem (CSP), wherein the CSP is defined by one or more variables and constraints such that the constraints define limitations for values that can be assigned to each variable in a given domain to solve the CSP, the system comprising: a logic unit for associating a first probabilistic request with a first constraint, wherein the first probabilistic request indicates that the first constraint is to be satisfied in a predefined percentage of the solutions; a logic unit for processing a first solution to determine whether the first constraint is satisfied by the first solution; and a logic unit for incrementing a success counter for the first probabilistic request, in response to determining that the first constraint is satisfied by the first solution. ### Claim 11 (depends on 10) The system of claim 10, further comprising a logic unit for incrementing a failure counter for the first probabilistic request, in response to determining that the first constraint is not satisfied by the first solution. ### Claim 12 (depends on 11) The system of claim 11, further comprising a logic unit for incrementing the failure counter for a second probabilistic request associated with the first constraint, in response to determining that the first constraint is irrelevant to the first solution. ### Claim 13 (depends on 10) The system of claim 10, further comprising a logic unit for reporting conformance rate for the first probabilistic request based on value of the success counter. ### Claim 14 (depends on 10) The system of claim 10, wherein value of the success counter is recorded in a data structure. ### Claim 15 (depends on 10) The system of claim 10, wherein the value of the success counter is used to determine success rate of the first probabilistic request. ### Claim 16 A computer program product comprising a computer useable medium having a computer readable program, wherein the computer readable program when executed on a computer causes the computer to: associate a first probabilistic request with a first constraint, wherein the first probabilistic request indicates that the first constraint is to be satisfied in a predefined percentage of the solutions; process a first solution to determine whether the first constraint is satisfied by the first solution; and increment a success counter for the first probabilistic request, in response to determining that the first constraint is satisfied by the first solution. ### Claim 17 (depends on 16) The computer program product of claim 16, wherein the computer readable program when executed on a computer further causes the computer to increment a failure counter for the first probabilistic request, in response to determining that the first constraint is not satisfied by the first solution. ### Claim 18 (depends on 17) The computer program product of claim 17, wherein the computer readable program when executed on a computer further causes the computer to increment the failure counter for a second probabilistic request associated with the first constraint, in response to determining that the first constraint is irrelevant to the first solution. ### Claim 19 (depends on 16) The computer program product of claim 16, wherein the computer readable program when executed on a computer further causes the computer to report conformance rate for the first probabilistic request based on value of the success counter. ### Claim 20 (depends on 18) The computer program product of claim 18, wherein the computer readable program when executed on a computer further causes the computer to aggregate success/failure results for the first probabilistic request over multiples solutions to determine whether the first soft constraint is satisfied in said predefined percentage of the solutions.