US 7,606,776 B1Granted

Flexible constraint propagation engine for combinatorial optimization applications

AssigneeActenum Corporation

InventorsWilliam S. Havens, Bistra N. Dilkina

Life of this patent

Estimating the term…

Loading patent…

Abstract

The present disclosure describes a computer-implemented constraint propagation system that supports a variety of different constraint propagation and/or constraint retraction algorithms, including monotonic and/or non-monotonic algorithms. In one embodiment, the system selects particular constraint propagation and/or retraction methods based on the nature of the combinatorial optimization problem (COP) being solved and the attributes of the particular COP application involved. The system may also enable new methods for constraint propagation and/or retraction to be added with relatively little disruptive effect on other components of the system. Embodiments of the system allow the propagation of constraints to be tuned to the semantics of each constraint, the likelihood of significant variable domain reduction, and other problem specific properties. The constraint propagation system is capable of being used as part of a reconfigurable search engine.

Claims41

Dependent claims

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.

3 more elements

A method for constraint propagation in a search engine configured to search for a solution of a combinatorial optimization problem, the method comprising:

communicating to a propagation processor information relating to an event associated with a solution of a combinatorial optimization problem, the propagation processor comprising hardware capable of executing instructions for a variable event that represents a change to a value or a domain of a variable and a constraint event that represents a change to a value or a domain of a variable associated with the constraint;
in response to said event information, executing instructions related to the event by the propagation processor, wherein the instructions comprise variable event instructions for a variable event or constraint event instructions for a constraint event, wherein:
(1) the variable event instructions are adapted for:
signaling information related to the variable event to a constraint of the combinatorial optimization problem;
determining whether the variable event is relevant to the constraint;
and
updating a constraint event if the variable event is relevant to the constraint;
and
(2) the constraint event instructions are adapted for:
propagating information related to the constraint event to a constraint of the combinatorial optimization problem;
reducing a variable domain of a variable associated with the constraint;
and
updating a variable event associated with the reduced variable domain;
and
searching for a solution to the combinatorial optimization problem based at least in part on the updated variable event or the updated constraint event.

12 more elements

Dependencies are inferred from the claim text.