Patent ID: 7606776
Filing Date: 2009-10-20
Classification: G06N

Abstract:
1. A system configured to search for solutions to a combinatorial optimization problem, the system comprising: a memory for storing information related to at least one constraint of a combinatorial optimization problem, the combinatorial optimization problem comprising variables and constraints that specify relationships among one or more of the variables, the memory further storing executable instructions that implement a constraint system, a propagator system, and a search engine; and a computer system programmed to execute the executable instructions; wherein the constraint system is configured to provide at least one message related to the at least one constraint, the message comprising at least one of an add constraint message and a retract constraint message, the propagator system is configured to receive the at least one message from the constraint system and to provide constraint propagation instructions in response to the received message, the constraint propagation instructions including instructions for processing (1) a variable event that represents a change to a value or a domain of a variable and (2) a constraint event that represents a change to a value or a domain of a variable associated with the constraint, and the search engine is configured to search for a solution to the combinatorial optimization problem based at least in part on the actions performed by the constraint system and the propagator system.