Method and apparatus for optimizing constraint models

Data processing: artificial intelligence – Neural network – Structure

Patent

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

39550043, 395708, 395709, 706 13, 706 45, G06F 9455

Patent

active

060319844

ABSTRACT:
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.

REFERENCES:
patent: 5267346 (1993-11-01), Maruyama et al.
patent: 5343388 (1994-08-01), Wedelin
patent: 5471408 (1995-11-01), Takamoto et al.
patent: 5636328 (1997-06-01), Kautz et al.
patent: 5640491 (1997-06-01), Bhat et al.
patent: 5657256 (1997-08-01), Swanson et al.
patent: 5781432 (1998-07-01), Keeler et al.
patent: 5848403 (1998-12-01), Gabrirner et al.
patent: 5855009 (1998-12-01), Garcia et al.
Fred Glover and Manuel Laguna. Tabu Search. In Colin R. Reeves, Editor, Modern Heuristic Techniques for Combinatorial Problems, chapter 3, pp. 70-150, Halsted Press, 1993.
Y.J. Jiang, H. Kautz, and B. Selman, Solving Problems with Hard and Soft Constraints Using a Stochastic Algorithm for MAX-SAT., In Proceedings of the First International Joint Workshop on Artificial Intelligence and Operations Research, 1995.
B. Selman, H.A. Kautz, and B. Choen. Local Search Strategies for Satisfiability Testing. Presented at Second DIMACS Challenge on Cliques, Coloring, and Satisfiability, Oct. 1993.
R. Aboudi and K. Jornsten. Tabu Search for General Zero-One Integer Programs Using the Pivot and Complement Heuristic. ORSA Journal on Computing, 6(1):82-93, 1994.
B. Selman, H.A. Kautz, and B. Cohen. Noise Strategies for Improving Local Search. In Proceedings AAAI-94, pp. 337-343, 1994.
S. Minton, M.D. Johnston, A.B. Philips, and P. Laird. Minimizing Conflicts: A Heuristic Repair Method for Constraint Satisfaction and Scheduling Problems. Artificial Intelligence, 58: 161-205, 1992.
Egon Balas and C.H. Martin. Pivot and Complement--a Heuristic for 0-1 Programming. Management Science, 26:86-96, 1980.
J.-K. Hao and R. Dorne. Empirical Studies of Heuristic Local Search for Constraint Solving. In Proceedings CP-96, pp. 194-208, 1996.
B. Selman, H. Levesque, D. Mitchell. A New Method for Solving Hard Satisfiability Problems. In Proceedings AAAI-92, pp. 440-446, 1992.
J.P. Walser. Solving Linear Pseudo-Boolean Constraint Problems with Local Search. In Proceedings AAAI-97, 1997.
D. Abramson and M. Randall. A Simulated Annealing Code for General Integer Linear Programs. pp. 1-19, May 9, 1997.
M.B. Jampel. Over-Constrained Systems in CLP and CSP, Ph.D. Thesis, Department of Computer Science, City University, Sep. 19, 1996, pp. 1-156.
D. Connolly. General Purpose Simulated Annealing. J. Opl. Res. Soc., vol. 43, No. 5, pp. 495-505, 1992.
D. Abramson, H. Dang, and M. Krishnamoorthy. A Comparison of Two Methods for Solving 0-1 Integer Programs Using a General Purpose Simulated Annealing Algorithm. Annals of Operations Research 63 (1996), pp. 129-150.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Method and apparatus for optimizing constraint models does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for optimizing constraint models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for optimizing constraint models will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-690879

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.