Patent ID: 7036720

Claim:
A system, comprising: a memory storing a problem; a processor coupled to the memory, the processor comprising: means for constructing a data structure representative of the problem, the data structure comprising constrained discrete variables of the problem and constraints of the variables, each variable having a referenced set of possible states; means for delivering messages between a variable of the variables and at least one constraint of the variable, the messages comprising a message containing a set of probabilities for various patterns of warning for the variable, a warning giving information on whether the various assignments from the set of possible states of the variable are compatible with the constraints involving the variable; means for calculating a probability of the variable satisfying the at least one constraint of the variable based on the messages delivered in order to compute a degree of polarization of the variable to know to what degree the most favorable assignment of the variable is better than all other possible assignments of the variable; means for assigning at least one of the variable a state from its set of possible states according to the computed degrees of polarization, for simplifying the problem; means for recursively using means for constructing the data structure, delivering messages, calculating probabilities, and assigning until at least all the variables have been assigned for providing a solution to the problem; and an output device coupled to the processor, the output device outputting the solution of the problem.