Solutions for constraint satisfaction problems requiring multiple constraints

• US 20050010922A1
• Filed: 06/30/2003
• Published: 01/13/2005
• Est. Priority Date: 06/30/2003
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Czajkowski, Greg, Miller, Mike F.
• Granted Patent: US 7,260,562 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

In one embodiment, the invention includes sorting a set of constraints based on weights associated with each constraint, the constraints being capable of being satisfied based on values selected for corresponding associated parameters, selecting a constraint that is unsatisfied and that has the greatest weight, selecting parameters associated with the constraint and finding parameter values to satisfy the constraint, after satisfying the selected unsatisfied constraint, selecting a further unsatisfied constraint having the next greatest weight and finding values for associated parameters to satisfy the further constraint, and repeating the selecting of further constraints and the finding of values for associated parameters.

Claims

1. A method comprising:

sorting a set of constraints based on weights associated with each constraint, the constraints being capable of being satisfied based on values selected for corresponding associated parameters;

selecting a constraint that is unsatisfied and that has the greatest weight;

selecting parameters associated with the constraint and finding parameter values to satisfy the constraint;

after satisfying the selected unsatisfied constraint, selecting a further unsatisfied constraint having the next greatest weight and finding values for associated parameters to satisfy the further constraint; and

repeating the selecting of further constraints and the finding of values for associated parameters.

2. The method of claim 1, wherein repeating comprises repeating the selecting of further constraints and the finding of values for associated parameters until the set of constraints is satisfied.

3. The method of claim 1, further comprising evaluating satisfied constraints after finding values for parameters associated with an unsatisfied constraint and, if a satisfied constraint is not satisfied using the found parameter values, then designating the constraint as unsatisfied.

4. The method of claim 1, wherein finding parameter values comprises performing a depth first walk of each selected associated parameter.

5. The method of claim 1, wherein finding parameter values comprises selecting parameters associated with a different constraint, finding parameter values to satisfy the different constraint, and then finding parameter values for the selected constraint.

7. The method of claim 1, further comprising tagging satisfied parameters as unsatisfied after finding parameter values to satisfy the different constraint.

8. The method of claim 1 wherein the parameters correspond to different data types.

9. The method of claim 1, wherein the different data types comprise numbers and strings.

10. The method of claim 1, wherein the parameters are further defined by domains and the domains include numerical ranges and lists.

11. The method of claim 1, further comprising deriving weights for association with constraints using at least one of parameter weights and parameter domain weights.

12. A machine-readable medium having stored thereon data representing instructions which, when executed by a machine, cause the machine to perform operations comprising comprising:

sorting a set of constraints based on weights associated with each constraint, the constraints being capable of being satisfied based on values selected for corresponding associated parameters;

selecting a constraint that is unsatisfied and that has the greatest weight;

selecting parameters associated with the constraint and finding parameter values to satisfy the constraint;

after satisfying the selected unsatisfied constraint, selecting a further unsatisfied constraint having the next greatest weight and finding values for associated parameters to satisfy the further constraint; and

repeating the selecting of further constraints and the finding of values for associated parameters.

13. The medium of claim 12, wherein the instructions for repeating comprise instructions which, when executed by the machine, cause the machine to perform further operations comprising repeating the selecting of further constraints and the finding of values for associated parameters until the set of constraints is satisfied.

14. The medium of claim 12, wherein the instructions for finding parameter values comprise instructions which, when executed by the machine, cause the machine to perform further operations comprising selecting parameters associated with a different constraint, finding parameter values to satisfy the different constraint, and then finding parameter values for the selected constraint.

15. The medium of claim 12, wherein the parameters correspond to different data types.

16. The medium of claim 12, wherein the parameters are further defined by domains, the domains are associated with weights, and the domains include numerical ranges and lists.

17. The medium of claim 12, further comprising instructions which, when executed by the machine, cause the machine to perform further operations comprising deriving weights for association with constraints using at least one of parameter weights and parameter domain weights.

18. An apparatus comprising:

a memory containing information regarding a set of constraints, the constraints being associated with weights, and the constraints being capable of being satisfied based on values selected for corresponding associated parameters; and

a processor to solve a constraint satisfaction problem by;

sorting the set of constraints based on the weights associated with each constraint;

selecting a constraint that is unsatisfied and that has the greatest weight;

selecting parameters associated with the constraint and finding parameter values to satisfy the constraint;

after satisfying the selected unsatisfied constraint, selecting a further unsatisfied constraint having the next greatest weight and finding values for associated parameters to satisfy the further constraint; and

repeating the selecting of further constraints and the finding of values for associated parameters.

19. The apparatus of claim 18, wherein repeating comprises repeating the selecting of further constraints and the finding of values for associated parameters until the set of constraints is satisfied.

20. The apparatus of claim 18, wherein the processor further solves the constraint satisfaction problem by evaluating satisfied constraints after finding values for parameters associated with an unsatisfied constraint and, if a satisfied constraint is not satisfied using the found parameter values, then designating the constraint as unsatisfied.

21. The apparatus of claim 18, wherein the information is stored as metatext in a markup language.

22. The apparatus of claim 18, wherein the metatext defines different data types.

23. A system comprising:

an I/O interface to receive metadata regarding a set of constraints, the constraints being associated with weights, and the constraints being capable of being satisfied based on values selected for corresponding associated parameters;

a compiler to convert the metadata into operable information;

a constraint sorter to sort the set of constraints based on the weights associated with each constraint, and to repeat the sorting of constraints upon the satisfaction of a constraint;

a constraint selector to select a constraint that is unsatisfied and that has the greatest weight, and after the selected unsatisfied constraint is satisfied, selecting a further unsatisfied constraint having the next greatest weight; and

a parameter selector to select parameters associated with selected constraint and find parameter values to satisfy the constraints.

24. The system of claim 23, wherein the constraint selector selects further constraints and the parameter selector finds further values for associated parameters until the set of constraints is satisfied.

25. The system of claim 23, wherein the constraint sorter evaluates satisfied constraints after values for parameters associated with an unsatisfied constraint are found and, if a satisfied constraint is not satisfied using the found parameter values, then designates the constraint as unsatisfied.

26. The system of claim 23, wherein the metatext defines different data types.

27. A method comprising:

selecting a set of parameters for a problem;

defining domains for each of the parameters;

establishing constraints to limit solutions to the problem;

applying a weight to each constraint, the weight being related to the priority of the constraint; and

setting relationships between the parameters and the constraints.

28. The method of claim 27, further comprising expressing the domains as metatext and expressing the constraints in a higher level language.

29. The method of claim 27, further comprising assigning weights to each of the parameters.

30. The method of claim 27, further comprising assigning weights to possible value for at least some of the parameters.

31. The method of claim 27, wherein establishing constraints comprises defining relationships among the parameters.