Skip to content

More on patents: constraint programming

Diego Olivier Fernandez Pons has continued to search the patent database for interesting patents. Here is one given in 2000 to i2:

US patent 6,031,984

Method and apparatus for optimizing constraint models

February 29, 2000

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.

Looks like i2 has a patent on constraint programming. This could certainly cause some chaos to companies!

{ 1 } Comments

  1. centerwise | December 14, 2006 at 11:08 am | Permalink

    http://www.google.com/patents

    FYI