Abstract
This paper presents a first formalization of an incremental method to solve hierarchies of constraints over finite domains, which borrows techniques developed in intelligent backtracking, and finds locally-predicate-better solutions. A prototype implementation of this method, IHCS, was written in C and can be integrated with different programming environments. In particular, with Prolog producing an instance of an HCLP language. Possible applications of IHCS are briefly illustrated with a time-tabling and a set covering problem.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P. Barahona and R. Ribeiro. Building an Expert Decision Support System: The Integration of AI and OR methods. In Martin Schader and Wolfgang Gaul, editors, Knowledge, Data and Computer-Assisted Decisions, chapter 3, pages 155–168. Springer-Verlag, Berlin Heidelberg, 1990.
A. Borning, M. Maher, A. Martingale, and M. Wilson. Constraints hierarchies and logic programming. In Levi and Martelli, editors, Logic Programming: Proceedings of the 6th International Conference, pages 149–164, Lisbon, Portugal, June 1989. The MIT Press.
C. Codognet and P. Codognet. Non-deterministic Stream AND-Parallelism based on Intelligent Backtracking. In Proceedings of 6th ICLP, Lisbon, 1989. The MIT press.
C. Codognet, P. Codognet, and G. Filé. Yet Another Intelligent Backtracking Method. In Proceedings of 5th ICLP/SLP, Seattle, 1988.
William S. Havens. Intelligent Backtracking in the Echidna Constraint Logic Programming System. Research Report CSS-IS TR 92-12, Simon Fraser University, Canada, 1992.
Vipin Kumar. Algorithms for Constraint-Satisfaction-Problems: A Survey. AI Magazine, pages 32–44, Spring 1992.
Alan K. Mackworth. Consistency in Networks of Relations. Artificial Intelligence, 8:99–118, 1977.
F. Menezes and P. Barahona. Report on IHCS. Research report, Universidade Nova de Lisboa, 1993.
F. Menezes, P. Barahona, and P. Codognet. An Incremental Hierarchical Constraint Solver Applied to a Time-tabling Problem. In Proceedings of Avignon 93, May 1993.
Luis Moniz Pereira and M. Bruynooghe. Deduction Revision by Intelligent Back tracking. In Implementations of Prolog, pages 194–215. J.A. Campbell, 1984.
P. Van Hentenryck, Y. Deville, and C.-M. Teng. A Generic Arc Consistency Algorithm and its Specializations. Technical Report RR 91-22, K.U. Leuven, F.S.A., December 1991.
M. Wilson and A. Borning. Extending Hierarchical Constraint Logic Programming: Nonmonotonocity and Inter-Hierarchy Comparison. In Proceedings of the North American Conference 1989, 1989.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Menezes, F., Barahona, P. (1993). Preliminary formalization of an incremental hierarchical constraint solver. In: Filgueiras, M., Damas, L. (eds) Progress in Artificial Intelligence. EPIA 1993. Lecture Notes in Computer Science, vol 727. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57287-2_54
Download citation
DOI: https://doi.org/10.1007/3-540-57287-2_54
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57287-9
Online ISBN: 978-3-540-48036-5
eBook Packages: Springer Book Archive