摘要 |
A computer implemented system (40) for optimizing a constraint model (52) includes a memory (46) for storing the constraint model (52). The constraint model (52) is an over-constrained system model that has constraints with variables. Each variable in the constraint model (52) is assigned a current value from a domain of the variable. A processor (42) generates a current assignment of each variable in the constraint model (52), selects a constraint from a set of unsatisfied constraints, selects at least one variable of the selected constraint, selects a new value for each selected variable, changes the value of each selected variable to its new value to generate a new assignment of variables, and stores the new assignment of variables as a best assignment in a set of one or more best assignments if it satisfies all the constraints and is at least as good as a best stored assignment. The processor (42) repeats the operations of selecting a constraint, a variable, and a new value, changing the value of each selected variable to its new value to generate a new assignment, and storing the new assignment until the new assignment satisfies all the constraints and is approximately optimal or until a specified number of iterations has been performed. In response, the processor (42) communicates at least one best stored assignment or communicates that no assignment satisfying all the constraints was found.
|