Data processing: artificial intelligence – Neural network – Learning task
Reexamination Certificate
2006-09-28
2009-10-20
Holmes, Michael B (Department: 2129)
Data processing: artificial intelligence
Neural network
Learning task
Reexamination Certificate
active
07606776
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.
REFERENCES:
patent: 5148045 (1992-09-01), Oyanagi
patent: 5267346 (1993-11-01), Maruyama et al.
patent: 5745735 (1998-04-01), Cohn et al.
patent: 5764858 (1998-06-01), Sheu et al.
patent: 5819210 (1998-10-01), Maxwell et al.
patent: 5848402 (1998-12-01), Pao et al.
patent: 6004015 (1999-12-01), Watanabe et al.
patent: 6047288 (2000-04-01), Kurosawa et al.
patent: 6148274 (2000-11-01), Watanabe et al.
patent: 6272483 (2001-08-01), Joslin et al.
patent: 6769112 (2004-07-01), Montana et al.
patent: 6826549 (2004-11-01), Marks et al.
patent: 7089221 (2006-08-01), Fromherz et al.
patent: 7444309 (2008-10-01), Branke et al.
patent: 7447669 (2008-11-01), Zhu
patent: 7448022 (2008-11-01), Ram et al.
patent: 7499764 (2009-03-01), Fukui
patent: 7523445 (2009-04-01), Geller et al.
patent: 2003/0154209 (2003-08-01), Maxwell et al.
patent: 2005/0065902 (2005-03-01), De Givry et al.
patent: 2005/0177558 (2005-08-01), Dixon et al.
patent: 2005/0187905 (2005-08-01), Dixon et al.
patent: 2008/0140475 (2008-06-01), Li et al.
Optimization of reliability allocation and testing schedule for software systems Lyu, M.R.; Rangarajan, S.; van Moorsel, A.P.A.; Proceedings The Eighth International Symposium on Software Reliability Engineering Nov. 2-5, 1997 pp. 336-347 Digital Object Identifier 10.1109/ISSRE.1997.630881.
A Varietal Genetic Algorithm by External Self-Evolving Multiple-Archives for Combinatorial Optimization Problems Chang, Pei-Chann; Huang, Wei-Hsiu; Ting, Ching-Jung; Chang, Wei-Je; High Performance Computing and Communications, 2009. HPCC '09. 11th IEEE International Conference on Jun. 25-27, 2009 pp. 609-614.
A New Approach using Machine Learning and Data Fusion Techniques for Solving Hard Combinatorial Optimization Problems Zennaki, M.; Ech-cherif, A.; Information and Communication Technologies: From Theory to Applications, 2008. ICTTA 2008. 3rd International Conference on Apr. 7-11, 2008 pp. 1-5 Digital Object Identifier 10.1109/ICTTA.2008.453.
A pattern-based evolving mechanism for genetic algorithm to solve combinatorial optimization problems Qing Wang; Kai Leung Yung; Wai Hung Ip; Soft Computing in Industrial Applications, 2003. SMCia/03. Proceedings of the 2003 IEEE International Workshop on Jun. 23-25, 2003 pp. 97-101 Digital Object Identifier 10.1109/SMCIA.2003.1231351.
Schimkat et al., “Deploying Distributed State Information in Mobile Agent Systems”, CoopIS 2001, LNCS 2172, Springer Berlin/Heidelberg, pp. 80-94, 2001.
Ginsberg et al., “GSAT and Dynamic Backtracking,” 1994.
Wallace M. et al., “Finding the right hybrid algorithm—A combinatorial meta-problem”, Annals of Mathematics and Artificial Intelligence, vol. 34, pp. 259-269, 2002.
Andrew B. Baker, Intelligent Backtracking on the Hardest Constraint Problems, Feb. 6, 1995.
Laura Barbulescu, L. Darrell Whitley, and Adele E. Howe, Leap Before You Look: An Effective Strategy in an Oversubscribed Scheduling Problem. In Proc. AAAI'04, San Jose, CA, pp. 143-148, 2004.
Roberto J. Bayardo Jr., and Daniel P. Miranker, A Complexity Analysis of Space-Bounded Learning Algorithms for the Constraint Satisfaction Problem, In Proceedings of the Thirteenth National Conference on Artificial Intelligence, pp. 298-304, 1996.
J. Christopher Beck and Mark S. Fox, Dynamic Problem Structure Analysis as a Basis for Constraint-directed Scheduling Heuristics, In Proceedings of the Thirteenth National Conference on Artificial Intelligence, Artificial Intelligence, vol. 117, pp. 31-81, 2000.
Romuald Debruyne, Arc-Consistency in Dynamic CSPs Is No More Prohibitive, In Proc. 8th Conference on Tools with Artificial Intelligence, pp. 299-306, 1996.
Bistra Dilkina, Lei Duan, and William S. Havens, Extending Systematic Local Search for Job Shop Scheduling Problems, In Proceedings of the Eleventh International Conference on Principles and Practice of Constraint Programming, Sitges, Spain, Oct. 1, 2005, pp. 762-766.
K.A. Dowsland, Simulated Annealing, Ch. 2, Modern Heuristic Techniques for Combinatorial Problems, ed. C.R. Reeves, John Wiley & Sons, 1993.
Matthew L. Ginsberg, Dynamic Backtracking, Journal of Artificial Intelligence Research 1, pp. 25-46, 1993.
Fred Glover, Tabu Search Fundamentals and Uses, Jun. 1995.
William S. Havens, NoGood Caching for MultiAgent Backtrack Search, In Proc. AAAI'97 Constraints and Agents Workshop, Providence, Rhode Island, 1997.
William S. Havens and Bistra N. Dilkina, A Hybrid Schema for Systematic Local Search. In Advances in Artificial Intelligence Proceedings of the 17th Conference of the Canadian Society for Computational Studies of Intelligence 2004, Springer-Verlag, pp. 248-260.
H. Hoos and T. Stutzle, Stochastic Local Search: Foundations and Applications, presentation from AAAI-04 Tutorial, 2004.
Eric Horvitz and Tim Paek, A Computational Architecture for Conversation, in Proc. Of the Seventh International Conference on User Modeling, Banff, Canada, Jun. 1999, New York: Springer Wien, pp. 201-210.
ILOG JSolver 2.0 Beta User's Manual, ILOG SA, France, Jul. 2002.
Narendra Jussein, Romuald Debruyne, and Patrice Boizumault, Maintaining Arc-Consistency within Dynamic Backtracking. In Sixth International conference on Principles and Practice of Constraint Programming (CP'2000), Sep. 2000, pp. 249-261.
Narendra Jussein and Vincent Barichard, The PaLM System: Explanation-based Constraint Programming. In Proceedings of TRICS: Techniques for Implementing Constraint Programming Systems, a post-conference workshop of CP'2000, pp. 118-133, 2000.
Narendra Jussein and Olivier Lhomme, Local Search With Constraint Propagation and Conflict-based Heuristics, Artificial Intelligence 139(1):21-45, 2002.
Francois Laburthe, Choco: Implementing a CP Kernel, Proceedings of TRICS: Techniques for Implementing Constraint Programming Systems, a post-conference workshop of CP'2000. In Proceedings CP2000, Lecture Notes in Computer Science series, vol. 1894, Singapore 2000.
Claude Le Pape, Implementation of Resource Constraints in ILOG Schedule: A Library for the Development of Constraint-Based Scheduling Systems, Intelligent Systems Engineering 3(2), pp. 55-66, Summer 1994.
Alan K. Mackworth, Consistency in Networks of Relations, Artificial Intelligence, vol. 8, 99-118, 1997.
Laurent Michel and Pascal Van Hentenryck, A Constraint-Based Architecture for Local Search. In Proc. ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, Seattle, WA, pp. 83-100, 2002.
Steven Minton, Mark D. Johnston, Andrew B. Philips, and Philip Laird, Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems, Artificial Intelligence 58(1-3), pp. 161-205, 1992.
Matthew W. Moskewicz, Conor F. Madigan, Ying Zhao, Lintao Zhao, and Sharad Malik, Chaff: Engineering an Efficient SAT Solver. In Proceedings of the 38th Design Automation Conference (DAC '01), Jun. 2001, pp. 530-535.
Samir Ouis, Narendra Jussein, and Patrice Boizumault, COINS: A Constraint-based Interactive Solving System. In ICLP'02 12tth Workshop on Logic Programming Environments, pp. 31-46, Jul. 12, 2002.
Steven Prestwich, Local Search and Back
Dilkina Bistra N.
Havens William S.
Actenum Corporation
Holmes Michael B
Knobbe Martens Olson & Bear LLP
LandOfFree
Flexible constraint propagation engine for combinatorial... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Flexible constraint propagation engine for combinatorial..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flexible constraint propagation engine for combinatorial... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4123266