Determining compliance rates for probabilistic requests

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.

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.   
   
   
       2 . 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. 
   
   
       3 . 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. 
   
   
       4 . The method of  claim 1 , further comprising reporting conformance rate for the first probabilistic request based on value of the success counter. 
   
   
       5 . The method of  claim 2 , further comprising reporting conformance rate for the first probabilistic request based on value of the failure counter. 
   
   
       6 . The method of  claim 1 , wherein value of the success counter is recorded in a data structure. 
   
   
       7 . The method of  claim 1 , wherein value of the failure counter is recorded in a data structure. 
   
   
       8 . The method of  claim 6 , wherein the value of the success counter is used to determine success rate of the first probabilistic request. 
   
   
       9 . 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. 
   
   
       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.   
   
   
       11 . 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. 
   
   
       12 . 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. 
   
   
       13 . 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. 
   
   
       14 . The system of  claim 10 , wherein value of the success counter is recorded in a data structure. 
   
   
       15 . The system of  claim 10 , wherein the value of the success counter is used to determine success rate of the first probabilistic request. 
   
   
       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.   
   
   
       17 . 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. 
   
   
       18 . 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. 
   
   
       19 . 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. 
   
   
       20 . 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.