Newsgroups: comp.constraints,comp.answers,news.answers From: jampel@cs.city.ac.uk (Michael Jampel) Subject: comp.constraints FAQ 1/2 Frequently Asked Questions [Monthly posting] Followup-To: comp.constraints Summary: Frequently asked questions about constraints Reply-To: jampel@cs.city.ac.uk (Michael Jampel) Organization: Department of Computer Science, City University Approved: news-answers-request@MIT.Edu Archive-name: constraints-faq/part1 Last-Modified: Fri Feb 23 10:15:00 1996 by Michael Jampel Version: 1.83 [Version 1.82 was dated February 1995 when of course it should have been Feb 1996. MBJ] Important Changes (since last posting): , Constraints journal now has a web page. Contributions and corrections should be sent to Michael Jampel . This is a list of Frequently Asked Questions (and answers) for the area of constraints, including books, journal articles, ftp archives, and systems & products. It is posted once a month to the newsgroups comp.constraints, comp.answers, and news.answers. NOTE: the WWW page associated with this FAQ now contains far more information than the FAQ does, including meta-information, i.e. pointers to other WWW pages and ftp sites. I strongly suggest you have a look at it: http://web.cs.city.ac.uk/archive/constraints/constraints.html People who helped with this FAQ include Philippe Blache , Mark Kantrowitz , Wm Leler , Manfred Meyer , Milind Tambe , Thomas Schiex , and Tad Hogg . Thanks to Mark Kantrowitz for allowing me to use large parts of his FAQs and Resource Guides for comp.lang.prolog and comp.ai. ---------------------------------------------------------------- Table of Contents: [1-1] Introduction [1-2] Definitions, scope of the word `constraint' [1-3] Sources of information about constraints [1-4] Constraints-related Mailing Lists and Journals [1-5] FTP Archives, WWW Pages, and Other Resources [1-6] Books and Journal Articles [1-7] Reviews and Surveys of Constraint Systems [1-8] Complexity of Constraint Satisfaction (including Phase Transition) [1-9] Benchmarks for Constraint Satisfaction Problems [1-10] Constraints for Natural Language Processing [1-11] N-Ary CSPs (N > 2) [1-12] Constraint Libraries for C and LISP programs [1-13] Constraints and Rule-Based (Production) Systems [1-14] Interval Constraints and Newton's Approximation [1-15] Dynamic CSPs (Constraint Satisfaction Problems) [1-16] Glossary: definitions of some terms [1-17] Explanation of value ordering heuristics [1-18] Explanation of constraint entailment [1-19] Explanation of Don't Know / Don't Care nondeterminism [1-20] Survey of CLP with Non-Linear Constraints (architectures) [1-21] TOC: The management "Theory of Constraints" [1-22] Global, specific, structural, continuous & symbolic constraints [1-23] CLP(R) and analog circuit diagnosis [1-24] Constraint Abstraction In the second part of this FAQ: [2-1] Introduction (same as in part1) [2-2] Introduction to Systems for Non-Linear Constraints [2-3] Free and Commercial Constraint Systems Search for [#] to get to topic number # quickly. In newsreaders which support digests (such as rn), [CTRL]-G will page through the answers. ---------------------------------------------------------------- Subject: [1-1] Introduction This guide lists constraint-related resources: archives, newsgroups, books, magazines, compilers and interpreters (in part 2), and anything else you can think of. Also included is a list of suppliers of products and a list of publishers. This guide is regularly posted in two parts to comp.constraints, usually on the 17th or 18th of each month. It may also be obtained by anonymous ftp from City University: ftp.cs.city.ac.uk [138.40.91.9], using username "anonymous" and password "name@host". The files part1 and part2 are located in the directory pub/constraints/constraints-faq/ [The ftp site will also contain other items on constraints.] WWW (World Wide Web) address: http://web.cs.city.ac.uk/archive/constraints/constraints.html This is also a jumping-off point giving access to most of the ftp sites mentioned in section [1-5]. The articles posted to the newsgroup are archived by month in the same location as this FAQ, in subdirectory ftp.cs.city.ac.uk:/pub/constraints/archive/comp.constraints The FAQ postings are also archived in the periodic posting archive on rtfm.mit.edu. Look in the anonymous ftp directory /pub/usenet/news.answers/constraints-faq in the files part1 and part2. If you do not have anonymous ftp access, you can access the archive by mail server as well. Send an E-mail message to mail-server@rtfm.mit.edu with "help" and "index" in the body on separate lines for more information. FAQs and Resource Guides for other newsgroups will usually be available on rtfm.mit.edu too. Disclaimer: We are not responsible for anything at all. Ever. So there. Copyright Michael Jampel 1994, 1995, 1996. Permission to do reasonable things not for profit is given to anyone. Anything else, ask me. ---------------------------------------------------------------- Subject: [1-2] Definitions, scope of the word `constraint' ``Constraint programming techniques can be more declarative and elegant (hence maintainable) than standard imperative languages, without sacrificing efficiency.'' Areas of interest include: [suggestions welcome] constraint satisfaction problem (eg Travelling Salesman) constraint satisfaction in AI constraint logic programming concurrent constraint programming complexity of constraint satisfaction dynamic (dynamically changing) constraint satisfaction problems partial constraint satisfaction hierarchical CLP object-oriented constraints deductive databases applications links to linear programming heterogeneous systems (e.g. mixtures of constraints with C (see [1-12]), expert system shells, constraint imperative programming etc). ---------------------------------------------------------------- Subject: [1-3] Sources of Information about constraints The newsgroups comp.lang.prolog, comp.ai, and (to a lesser extent) sci.op-research and comp.theory are a source of information and discussion on constraints. See also [1-4] and [1-5]. ---------------------------------------------------------------- Subject: [1-4] Mailing Lists and Journals Constraint Logic Programming clp-request@cis.ohio-state.edu For those interested in the CLP(R) Language: clpr-users-request@cis.ohio-state.edu Both the above lists are maintained by Spiro Michaylov . E-mail the given addresses for more info. The list clp-request.All_Areas@xerox.com, aimed at Concurrent Logic Programming, no longer exists, according to Vijay Saraswat (information via David Joslin). Constraint Satisfaction Problem (CSP) To subscribe, send e-mail to listserver@saturne.cert.fr in the form "SUB CSP-LIST ". (Send submissions to .) List maintained by Thomas Schiex . Previous articles are archived at the same place as this FAQ; availble via WWW or ftp from ftp.cs.city.ac.uk:/pub/constraints/archive/csp-list Intelligent Decision Support System Mailing List [not completely relevant, but to some extent related to applications of constraints] To post to the list e-mail . Subscription requests should be sent to The Journal of Functional and Logic Programming (JFLP) is a new electronic journal that covers a broad scope of topics from functional and logic programming. It is specially concerned with the integration of the functional and logic paradigm as well as their common foundations. The Journal expects articles ranging from the theoretical foundations of functional and logic programming up to the application of such languages ``in the real world''. The Journal is published by The MIT Press. See either of the following URL's for more details http://mitpress.mit.edu/jrnls-catalog/jflp.html http://www.cs.tu-berlin.de/~chak/jflp/ Various AI and Logic Programming journals are likely to have articles on constraints, including `AI Journal'. There is now a new journal called CONSTRAINTS, pulished by Kluwer: Editor-in-Chief: Eugene C. Freuder, University of New Hampshire (ecf@cs.unh.edu) with web page CONSTRAINTS will be available both as a conventional paper journal and in electronic form. Publication will commence in the second half of 1996. Aims and Scope: The journal seeks to provide a common forum for the many disciplines interested in constraint satisfaction and optimization, and the many application domains interested in employing constraint technology. It will cover all aspects of computing with constraints: theory and practice, algorithms and systems, reasoning and programming, logics and languages. Relevant disciplines and application domains include, but are not limited to: Disciplines Artificial Intelligence Programming Languages Operations Research Combinatorial Algorithms Discrete Mathematics Databases Computational Logic Symbolic Computation Parallel/Distributed Computing Neural Networks Domains Scheduling, Planning, Resource Allocation Design and Configuration Graphics, Visualization, Interfaces Hardware Verification and Software Engineering Robotics, Machine Vision and Computational Linguistics Temporal and Spatial Reasoning Qualitative and Diagnostic Reasoning Human-Computer Interaction and Decision Support Real-Time Systems Molecular Biology Papers that cut across disciplinary lines, or that combine theory and practice, are especially welcome. The journal will also consider tutorial and survey papers. The Instructions for Authors can be obtained from Miss Kelly Riddle via e-mail: krkluwer@world.std.com. ---------------------------------------------------------------- Subject: [1-5] FTP Archives, WWW pages, and Other Resources The following are archives that contain constraint-related material. Most of the archives are anonymous ftp sites. Mark_Kantrowitz@cs.cmu.edu has created an AI ftp repository. ftp.cs.cmu.edu:/user/ai See also PTF below. Constraint Programming Paper Archive: Aarhus University, Denmark, has established an anonymous ftp archive for papers on "Constraint Programming" at ftp.daimi.aau.dk:/pub/CLP/ For further information, contact Brian H. Mayoh . Original Constraint Logic Programming Bibliography: [A more recent, larger, version is available on the ftp site for this FAQ: ftp.cs.city.ac.uk:/pub/constraints/bibliography/] ftp archive.cis.ohio-state.edu:/pub/clp (128.146.8.52) cd pub/clp or cd pub/clp/{bib,papers} Originally maintained by Spiro Michaylov Constraints Bibliography: ftp ??? [any offers?] ??? Maintained by ??? Manfred Meyer's constraints bibliography may be made available soon. It, and other useful items concerning constraints, may be found on the City University ftp site where this FAQ is stored. See topic [1-1]. ECRC tech reports are available by anonymous ftp from ftp.ecrc.de or http://www.ecrc.de/ on WWW. FAQs on Linear and Non-Linear programming written by John Gregory for the sci.op-research newsgroup are posted there and are available from rtfm.mit.edu directory /pub/usenet/sci.answers/ in files linear-programming-faq and nonlinear-programming-faq. ICOT: Japan's Institute for New Generation Computer Technology (ICOT) has made their software available to the public free of charge. The collection includes a variety of prolog-based programs in symbol processing, knowledge representation, reasoning and problem solving, natural language processing. All programs are available by anonymous ftp from ftp.icot.or.jp. Note that most of the programs are written for the PSI machines, and very few have been ported to Unix-based emulators. Some languages are discussed in section [2-1] in part2 of this FAQ; for further information, send email to ifs@icot.or.jp, or write to ICOT Free Software Desk, Institute for New Generation Computer Technology, 21st Floor, Mita Kokusai Bldg., 4-28, Mita 1-chome, Minato-ku, Tokyo 108, Japan, fax +81-3-4456-1618. See also PTF. PTF: The Prime Time Freeware CD-ROM series contains various items mentioned in this FAQ including Mark Kantrowitz's AI Repository, some ICOT material, BERTRAND, GARNET, and LIFE. Prime Time Freeware for UNIX sells for $60 US, list, and is issued twice each year. E-mail for more details. University of Washington (Seattle): Constraint-related papers and solvers/implementations including ThingLabII, CoolDraw (a constraint-based drawing system), and the DeltaBlue and SkyBlue algorithms. All public domain. Contact Alan Borning for details. ftp.cs.washington.edu:/pub/constraints or, on WWW, http://www.cs.washington.edu/research/constraints.html WWW sites: http://web.cs.city.ac.uk/archive/constraints/constraints.html http://ps-www.dfki.uni-sb.de/ http://www.ecrc.de/ http://www.cis.upenn.edu/~screamer-tools/home.html/ http://www.sics.se/ccp/ccp.html/ http://www.cs.washington.edu/research/constraints.html ---------------------------------------------------------------- Subject: [1-6] Books and Journal Articles This is not intended to be a complete bibliography. See ftp sites above for the location of longer bibliographies. Please suggest additions etc. F. Benhamou and A. Colmerauer, eds. "Constraint Logic Programming: Selected Research" MIT Press, 1993. J. Cohen, "Constraint Logic Programming Languages", Communications of the ACM 33(7):52-68, 1992. [Good introduction to CLP and includes a historical overview.] B. Freeman-Benson, J. Maloney, and A. Borning, "An Incremental Constraint Solver", Communications of the ACM 33(1):54-63, 1990. [Includes a good reading list on the history and applications of constraints.] E. Freuder, "Synthesizing Constraint Expressions", Communications of the ACM 21(11):24-32, 1978. T. Fruehwirth et al, "Constraint Logic Programming: An Informal Introduction", in Logic Programming in Action, 1992, Springer-Verlag, LNCS 636, (Also available as Technical Report ECRC-93-5. ECRC tech reports are available from ftp.ecrc.de:/pub/ECRC_tech_reports) J. Jaffar and J-L. Lassez, "Constraint Logic Programming", in Proceedings of the 14th ACM Symposium on Principles of Programming Languages (POPL), Munich, pp. 111-119, 1987. J. Jaffar and M. Maher, "Constraint Logic Programming: A Survey", Journal of Logic Programming, 1994, (To appear). V. Kumar, "Algorithms for Constraint-Satisfaction Problems: A Survey", AI Magazine 13(1):32-44, 1992. E. Lawler, J. Lenstra, A. Rinnooy Kan and D. Shmoys, "The Traveling Salesman Problem", Wiley, 1985/1992. W. Leler, "Constraint Programming Languages", Addison-Wesley, 1988, 0-201-06243-7. (See entry on `BERTRAND' in section [2-1] of part2 of this FAQ.) A. Mackworth, "Consistency in Networks of Relations", Artificial Intelligence 8(1):99-118, 1977. P. Meseguer, "Constraint Satisfaction Problems: An Overview", AICOM 2(1):3-17, 1989. U. Montanari, "Networks of Constraints: Fundamental Properties and Applications to Picture Processing", Information Science 7(2):95-132, 1974. G. Nemhasuer, A. Rinnooy Kan, M. Todd, "Optimization", North-Holland, 1989. J. Pearl, "Heuristics: Intelligent Search Strategies for Computer Problem Solving", 1984, Addison-Wesley, 0-201-05594-5. V. Saraswat, "Concurrent Constraint Programming", MIT Press, 1993. G. Steele, "The Definition and Implementation of A Computer Programming Language Based on Constraints", PhD thesis, MIT, 1980. E. Tsang, "Foundations of Constraint Satisfaction", Academic Press, 1993. ISBN 0-12-701610-4. P. Van Hentenryck, "Constraint Logic Programming", Knowledge Engineering Review, 6(3):151-194, September 1991. P. Van Hentenryck, "Constraint Satisfaction in Logic Programming", MIT Press, Cambridge, MA, 1989, ISBN 0-262-08181-4. [See also the articles on Constraint Networks (pages 276-285) and Constraint Satisfaction (pages 285-293) in Shapiro's Encyclopedia of Artificial Intelligence.] The Journal "Artificial Intelligence" has articles on the Constraint Satisfaction Problem (CSP), as do other AI journals. Magazines related to Prolog will have articles on Constraint Logic programming (CLP). AI Communications (4 issues/yr) "The European Journal on Artificial Intelligence" ISSN 0921-7126, European Coordinating Committee for Artificial Intelligence. AI Expert (issued monthly) ISSN 0888-3785, Miller Freeman Publishers On CompuServe: GO AIEXPERT. Reviews Prolog-related products. Expert Systems (4 issues/yr) ISSN 0266-4720, Learned Information (Europe) Ltd. IEEE Expert (issued bimonthly) ISSN 0885-9000, IEEE Computer Society The Journal of Logic Programming (issued bimonthly), (North-Holland), Elsevier Publishing Company, ISSN 0743-1066 New Generation Computing, Springer-Verlag. (Prolog-related articles) ---------------------------------------------------------------- Subject: [1-7] Reviews and Surveys of Constraint Systems The WWW address http://www.aiai.ed.ac.uk/~timd/constraints/csptools/ contains an Overview of CSP tools, including CHIP, CHARME, and ILOG SOLVER by Tim Duncan. ---------------------------------------------------------------- Subject: [1-8] Complexity of Constraint Satisfaction (including Phase Transition) Standard papers on this area include: Alan Mackworth and Eugene Freuder, "The Complexity of Some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems", in Artificial Intelligence, 1985, 25:65-73 Alan Mackworth and Eugene Freuder, "The Complexity of Constraint Satisfaction Revisited", in Artificial Intelligence, February 1993, 59 (1-2): 57-62, Also Tsang's book as mentioned previously. Phase Transitions in Constraint Satisfaction Problems ----------------------------------------------------- The search difficulty of constraint satisfaction problems can be determined, on average, from knowledge of easily computed structural properties of the problems. In fact, hard problem instances are concentrated near an abrupt transition between under- and over- constrained problems. This transition is analogous to phase transitions in physical systems and offers a way to estimate the likely difficulty of a constraint problem before attempting to solve it with search. For more information and pointers to related work, see the web page: ftp://parcftp.xerox.com/pub/dynamics/constraints.html Information kindly supplied by Tad Hogg . ---------------------------------------------------------------- Subject: [1-9] Benchmarks for Constraint Satisfaction Problems Some benchmarks are available from the same ftp archive and WWW page as this FAQ: ftp.cs.city.ac.uk:/pub/constraints/csp-benchmarks including a Radio Link Frequency Assignment Problem ---------------------------------------------------------------- Subject: [1-10] Constraints for Natural Language Processing [This entry reprinted by kind permission of the author: Philippe Blache , University of Nice-Sophia Antipolis] Current linguistics theories often describe syntactic relations as constraints on linguistic structures. It is in particular the case of unification-based theories. But linguistic constraints are generally far from the CLP ones and the question remains: is NLP a constraint satisfaction problem ? [[MBJ adds an editorial note: Micha Meier feels that NLP _is_ a typical CSP.]] It is still difficult to say what could be the actual advantages of a CLP approach for natural language processing in general. But if we don't have a global answer, several works propose CLP representation of particular problems such as linear precedence (cf Patrick Saint- Dizier), disjunctive values (cf Franz Guenthner), subcategorization, etc ... I'm currently working on the interpretation of HPSG's principles with boolean constraints. The problem in this case comes from the fact that the instantiation principles of this theory can be seen as constraints on feature structures, but using actual active constraints need a very rigid (and heavy) representation of these structures. A compromise between a pure CLP and a pure linguistic approach is still inevitable. I would be deeply interested in other approaches to this problem. Franz Guenthner (1988) "Features and Values 1988" CIS-BERICHT-90-2, University of Munich Patrick Saint-Dizier (1994) Advanced Logic Programming for Natural Language Processing, Academic Press, London Philippe Blache (1992) "Using Active Constraints to Parse GPSGs" in proceedings of COLING'92 ---------------------------------------------------------------- Subject: [1-11] N-Ary CSPs (N > 2) [This entry reprinted by kind permission of the author: Sunil Mohan , Rutgers University] N-ary CSPs have constraints with arbitrary arity, including some with arity > 2. There are some problems with solving CSPs that appear only when encountering constraints with higher arities. Constraints with maximum arity are also called global constraints. Selecting a suitable Variable-Constraint Ordering (Control Sequence) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Some of the popular variable ordering heuristics for generating a "good" control sequence fail on N-ary CSPs: - Ordering based on variable domain size. Many such heuristics fail because of their very localized view of the problem. Consider the CSP: { | T1(x1 x2) T2(x1 x2 x3) T3(x4 x5)} After first selecting (x1 x2 T1), a variable-domain-size based heuristic could proceed to pick x4 as the next variable to bind, when x3 could have been a better choice because it allows T3 to be tested. Or, in Forward-Check, (x1 T1 x2 T3..) is probably a better choice than (x1 T1 x4 T5 x2 T3..), but this heuristic does not have a way of recognizing the presence of higher-arity constraints. This is not a problem with Binary CSPs, particularly in FwdChk, because after binding each variable, a binary constraint on that variable can be tested. - Ordering based on variable connectivity. In a CSP with a global constraint, every variable is connected to n-1 other variables. The same happens with heuristics based on minimizing Constraint Bandwidth [Ramin Zabih, 8th NCAI 1990]. Some Ordering Heuristics for N-ary CSPs ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ I have experimented with the following ordering heuristics: - Minimizing Constraint Bandwidth Sum - Minimizing Constraint Depth Sum (Constr Depth is distance of constr from beginning of sequence) - Ordering variables based on nbr of constraints on it. In general, to generate a good control sequence for N-ary CSPs, a global view of the problem is needed. Binding a variable that allows a (n-ary) constraint that already has the rest of its argument variables bound, should get higher priority than another variable, all other things being equal. Sometimes it is better to view the problem as one of ordering constraints rather than variables. I like to think of testing constraints as early as possible in the search tree. Hence the Constraint BandWidth Sum and Depth Sum heuristics. Of course, variable domain size is also a factor. Decomposing the CSP ~~~~~~~~~~~~~~~~~~~ Freuder [JACM, Jan 1981] showed that tree-shaped CSPs can be solved (find first solution) without backtracking after some consistency processing. Consequently some techniques have been developed to get non-tree problems into that form. Some techniques decompose a CSP into variable clusters such that the shape of the constraint network on these clusters is tree shaped [Dechter & Pearl, AIJ 1989; Gyssens, Jeavons, Cohen, 1992; etc.]. Each variable cluster includes some cluster-local constraints. The complexity of the problem is reduced to the complexity of the largest cluster. With a global constraint in the CSP, this kind of decomposition is not possible. Cycle-cutset based techniques stumble in the same way. ---------------------------------------------------------------- Subject: [1-12] Constraint Libraries for C and LISP Programs Patrick Prosser discusses various standard algorithms in the journal Computational Intelligence vol 9(3), 1993. Scheme versions available from Pat on request; Lisp implementations are available from ftp://ftp.cs.strath.ac.uk/local/pat/csp-lab. Peter Van Beek has written a set of libraries for C. This package is available from ftp://ftp.cs.ualberta.ca/pub/ai/csp where you will find a README and also csplib.tar.Z. Also available from the archive site for this FAQ (see section [1-1]). ---------------------------------------------------------------- Subject: [1-13] Constraints and Rule-Based (Production) Systems Milind Tambe writes: Many researchers have explored the possible integration of constraint satisfaction techniques/methods and production (rule-based) systems. The integration has been explored in the context of both backward chaining[1] and forward-chaining systems (see below). This short note focuses on one aspect of this integration: constraints and forward-chaining production systems. These forward chaining systems execute tasks by going through recognize-act cycles: in the recognize or match phase, productions or rules match with working memory (a database of facts) and in the act phase, the matched productions are fired, causing changes to working memory, in turn causing the system to execute the next recognize act cycle. Integration of constraints with such systems is possible at multiple levels. At a higher level, the integration with constraints may involve a shift in the recognize-act cycle. For instance, constraint-satisfaction techniques may be used in addition to the recognize-act cycle to define values in working memory[2]. At this higher level, constraints do not change the recognize-act cycle itself. At a lower level, however, the integration with constraints may involve a change in the recognition procedure, i.e., the procedure used to match productions with working memory. More specifically, the problem of matching conditions of productions with working memory can be mapped over onto constraint satisfaction problems. Techniques such as arc-consistency, path-consistency or others may then be used either to reduce the match cost of productions by quickly eliminating easily detectably inconsistencies, or alternatively even to substitute for the matching procedure[3]. 1. "Concurrent constraint programming languages", V. Saraswat, PhD Thesis, 1989, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA. 2. "Constrained heuristic search" M. Fox, N. Zadeh & C. Baykan, IJCAI-89, pp 309-315. 3. "Investigation production system representations for non- combinatorial match" M. Tambe & P. Rosenbloom, Artificial Intel., Volume 68, Number 1, 1994. ---------------------------------------------------------------- Subject: [1-14] Interval Constraints and Newton's Approximation Michael Jampel asked: Would anyone like to comment on the integration of Newton's approximation method with interval constraint solvers? Pascal Van Hentenryck replied: You may want to look at our recent technical report CS-94-18: CLP(Intervals) Revisited F. Benhamou, D. McAllester, and P. Van Hentenryck which describes precisely a smooth integration of Newton method into a CLP(Intervals) language. The language, called Newton, was applied to some traditional benchmarks in this area and compared with specific tools. You may get a copy of the report by anonymous ftp from wilma.cs.brown.edu:/pub/techreports/94/cs94-18.ps.Z ---------------------------------------------------------------- Subject: [1-15] Dynamic CSPs (Constraint Satisfaction Problems) Thomas Schiex writes: A definition: A dynamic constraint satisfaction problem P is a sequence P_0 ... P_alpha of static CSPs each one resulting from a change in the preceding one [1]. This change may be a _restriction_ (a new constraint is imposed on a subset of variables) or a _relaxation_ (a constraint is removed from the CSP). [2] and [3] contain many references to other papers in the field. [1] Rina Dechter and Avi Dechter, ``Belief Maintenance in Dynamic Constraint Networks'', Proceedings AAAI, 1988, pp 37-42. [2] Gerard Verfaillie and Thomas Schiex, ``Solution reuse in dynamic CSPS'', Proceedings AAAI, August 1994. [3] Christian Bessiere, ``Arc-Consistency in Dynamic CSPs'', Proceedings AAAI, 1991, pp 221-226. ---------------------------------------------------------------- Subject: [1-16] Glossary: definitions of some terms Thanks to Patrick Prosser, Thomas Schiex, Berthe Choueiry, Alan Borning, Warwick Harvey, Thom Fruehwirth. Please inform me of additions. AC Arc-Consistency: a method for reducing the amount of back-tracking in CSPs AC-n Different algorithms for enforcing arc consistency: AC-3, AC-4 (Mackworth), AC-5 (van Hentenryck), AC-6+, AC6++ (Bessiere and Regin), AC-7 (Freuder). Also Hierarchical AC: HAC (Mackworth) and HAC-6 (Kokeny) AKL Agent Kernel Language: object-oriented concurrent constraints (previously called Andorra Kernel Language) AND- AND-PARALLEL means doing all the atomic goals in one clause (or query) of a logic program in parallel (all the nodes of one branch of the search tree). OR-PARALLEL means doing all the clauses in parallel (all the branches of the search tree). ATMS Assumption-Based Truth-Maintenance System BJ Backjumping (*) BM Backmarking (*) BMJ Backmarking with backjumping (*) CBJ Conflict-Directed Back-Jumping (*) DB Dynamic Backtracking (*) CC(FD) Concurrent Constraint Programming over Finite Domains CCP Concurrent Constraint Programming CHR Constraint Handling Rules (Fruehwirth) CIP Constraint Imperative Programming CLP Constraint Logic Programming CLP(FD) Constraint Logic Programming over finite domains CLP(R) Constraint Logic Programming over the domain of Real numbers CLP(X) Constraint Logic Programming over some domain X COP Constrained Optimization Problem CSP Constraint Satisfaction Problem DBT Dynamic backtracking DCSP Dynamic CSP DnAC Dynamic arc-consistency DVO Dynamic Variable Ordering heuristic (*) FC Forward-checking (*) FF First Fail principle: choose the variable with the smallest domain as the next instantiation (*) FLA Full Look Ahead FOF Factor Out Failure FSL Full Shallow learning (*) GBJ Graph based Backjumping (*) GSAT Selman's GSAT HAC Hierarchical Arc Consistency. See AC-n. HCLP Hierarchical CLP IB Intelligent Backtracking (*) IDA* Iterative Deepening A* ILP Integer Linear Programming IP Integer Programming LC Local changes LP Logic Programming or Linear Programming MAC Maintaining Arc-Consistency NC Node consistency (see AC). Not much used NLP Non-Linear Programming. (Natural Language Processing elsewhere) NR Nogood recording (*) OR Operations Research. see newsgroup sci.op-research OR- See AND- PC Path-Consistency. Not much used PCSP Partial CSP PLA Partial Look Ahead RFLA Real Full Look Ahead SAT The problem of deciding if a given logical formula is SATisfiable. TMS Truth-Maintenance System TSP Travelling Salesman Problem; a typical very hard problem (*) All these are different techniques/heuristics for improving the efficiency of constraint satisfaction ---------------------------------------------------------------- Subject: [1-17] Explanation of value ordering heuristics > Can someone tell me what is the definition of VALUE ORDERING > and what is its purpose, and are there any rules to follow > when doing value ordering or is it domain dependent? In Constraint Satisfaction Problems, once you have decided which _variable_ to instantiate next, say V, if V has more than one possible value, you might ask which _value_ to choose first. The simplest is to go systematically through the domain of V from smallest to largest. But if V has domain [1,2,...10] and (by some magic) you know that some/all the solutions to your CSP have V=10, then it would be nice if you could try V=10 first, before wasting a lot of work on 1,2,... One well-known heuristic is to choose that value for V which is consistent with the _greatest_ number of the constraints on V. If V is only involved in constraints with X, and the possible values for (V,X) are (1,2), (1,3), (2,3), then you should choose V=1 before trying V=2. Unfortunately, it is quite expensive to keep on checking which is the most popular value in this sense. (And there is no point doing it if you want all solutions, as you will have to try V=1 and V=2 anyway.) It is so expensive that it is usually not worth doing. Of course, if you have problem-specific knowledge it might suggest a different heuristic, which might be good in your particular circumstances. In contrast, the first-fail heuristic for choosing which _variable_ to instantiate next by choosing the one with smallest domain size, is (a) very cheap (b) often gives good benefits. ---------------------------------------------------------------- Subject: [1-18] Explanation of constraint entailment > Could anybody give me the definition of constraint entailment? If we already have `X = 8' in the constraint store, we can ask three questions about some other constraint C: a) Is C entailed by the store? If C is, say, `X > 5' then the answer is `yes' -- X > 5 does not give you any extra information if you already know that X = 8. b) Is the negation of C entailed by the store? (Is C `disentailed') If C is `X > 5' the answer is `no', but if C was, say, X < 2, it would be false in the context provided by the store c) Is C neither entailed nor disentailed? The constraint `Y = 4' is consistent with the store, and so is its negation, but it is not entailed by it. In the language of Concurrent Constraints, we can `ask' if a constraint is entailed, and get `yes', `no' or `suspend' (i.e. the ask goes to sleep until enough extra information is added to the store to give a definite answer). If we want to add information to the store, we can do a `tell' which only works if the constraint to be told is not inconsistent with the store. ---------------------------------------------------------------- Subject: [1-19] Explanation of Don't Know / Don't Care nondeterminism > Could anybody give me the definitions of committed choice, don't > know, and don't care nondeterminism, please? Don't know/don't care nondeterminism: If I say to a class of students ``Write all your names on this piece of paper'' then I know that I want ALL the names, but I don't KNOW which ORDER they will be written in. If I say to a class of students ``One of you must clean the board before the lesson'' then I only want ONE of them to do it, and I don't CARE who. Or, in an operating system, when I save a file in the editor, I don't care which particular block of the disk the file is written on. But once the OS has started writing the file to one block, I don't want it to change its mind half-way through -- I want it to COMMIT to the CHOICE it has made. So don't know nondeterminism is what you get from Prolog's search rule whereas don't care nondeterminism (sometimes called `indeterminism') is what you would expect from an OS, or from ``Committed choice parallel logic languages'' such as Parlog or FGHC. Committed choice is linked to the idea of a `guard' or `commit' operator which is like the `cut' in Prolog (but imagine having to have a cut at the begining of every clause, so once you have selected it, you are committed to it and there is no back-tracking). Committed-choice and don't care --> you lose the link between declarative (model-theoretic) and operational semantics which is one of the nice things about Prolog. ---------------------------------------------------------------- Subject: [1-20] Survey of CLP with Non-Linear Constraints by Olga Caprotti Systems (discussed individually in Part 2 of this FAQ): CAL CLP(F) GDCC ILOG Solver Newton QUAD-CLP(R) RISC-CLP(Real) Architectures (discussed here): Cooperative Constraint Solvers Symbolic Representation Scheme ---------------------------------------------------------------- Cooperative Constraint Solvers ------------------------------ Michel Rueher For solving constraints over the reals, we have defined a cooperating architecture based on an asynchronous communication between heterogeneous solvers. It enables to put together both symbolic and numerical solvers for tackling systems of constraints that none of them could solve alone. Solutions provided by such a cooperating system are always at least as accurate than the one which could individually be computed by the different solvers. A prototype for a cooperative system including a solver of linear equations and inequalities, a solver of polynomial equalities, and a solver based on interval propagation is under development. References: [1] Michel Rueher. An Architecture for Cooperating Constraint Solvers on Reals. In "Constraint Programming: Basics and Trends". LNCS 910, 231-250, March 1995. [2] P. Marti and M. Rueher. A Distributed Cooperating Constraints Solving System. Special issue of IJAIT (International Journal on Artificial Intelligence Tools), 4(1-2):93--113, June 1995. (ps available from: http://wwwi3s.unice.fr/~rueher/IJAIT.ps) ---------------------------------------------------------------- Symbolic Representation Scheme ------------------------------ Leon Sterling This paper describes experience in using constraint logic programming to reason about mechanical parts. A prototype program was written in the language CLP(R) which verified whether a part met specific tolerances in its dimensions. The program is interesting in that the same code can be used with any mixture of symbolic and numeric values. A symbolic representation scheme, underlying the program, which allows both symbolic and numeric values, is described. Examples are given of defining generic parts and toleranced parts, and checking whether a part meets its tolerances. Finally, a design rule checker is sketched to show how the logical representation of logic representation languages facilitates higher level reasoning. Reference: [1] L.S. Sterling. Of Using Constraint Logic Programming for Design of Mechanical Parts. Intelligent Systems - Concepts and Applications, (ed. L. Sterling), 107-116, Plenum Press, 1993 ---------------------------------------------------------------- Subject: [1-21] TOC: The management "Theory of Constraints" The "Theory of Constraints" has got nothing to do with CLP, CSP, or comp.constraints. However, for those who want to find out a little bit more about it, there is a file containing some email from Thomas McMullen <75564.310@compuserve.com> (also mentions the 1995 APICS Symposium): ftp://ftp.cs.city.ac.uk/pub/constraints/management-theory-of-constraints.Z There is also a WWW page at http://www.rudy.org.il/toc/index.html ---------------------------------------------------------------- Subject: [1-22] Global, specific, structural, continuous & symbolic constraints [questions and answers edited by MBJ; delimited by `>>>>>>'] From: Peter.Schotman@USERS.INFO.WAU.NL Newsgroups: comp.constraints Subject: Question: constraint terminology Date: Fri, 30 Jun 95 10:37:51 Organization: Wageningen Agricultural University Question: Could somebody explain the following terms: - Global constraints (the FAQ says: "constraints with maximum arity", does that mean that if the problem contains N variables only N-ary constraints are considered global?) - Specific and structural constraints (in: CHIC lessons on CLP methodology, ECRC-report) A lot of applications (I think) contain both a set of reasonably stable (permament) constraints as well as constraints that change from problem to problem instance, is that what is ment here? Also I would appriciate pointers to papers that explicitly deal with problem solving systems for a combination of continuous and symbolic constraints. Thanks in advance, Peter Schotman >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Newsgroups: comp.constraints From: leconte@ilog.fr (Michel Leconte) Subject: Re: Question: constraint terminology Organization: ILOG S.A., France Date: Mon, 3 Jul 95 12:44:52 GMT |> Question: Could somebody explain the following terms: |> - Global constraints The term "global constraint" is related with the level of consistency achieved by the propagation engine. A classical example is the "alldiff" constraint: alldiff(x1,...xi,...xn) setting that, in any solution, all the values of the xi must be pairwise distinct. The traditionnal (local) handling of this constraint ensures that, each time a variable is instantiated to a value, this value does not appear in the domains of the other variables. More formally, the following holds: forall xi, forall xj != xi, forall u belonging to the domain of xi, there exists a value v in the domain of xj such that u != v. The global handling of this constraint should maintain the following property: forall xi, forall u in the domain of xi, there exist values from domains of {x1,...,xj,...xn | xj != xi} such that u and these values are pairwise distinct. In other words, the global consistency of a constraint is: any value in the domain of a variable belongs to a solution. The global consistency of the alldiff constraint has been shown by J-C Regin in: "A filtering algorithm for constraint of difference in CSPs. Jean-Charles Regin, AAAI 94, Seattle, Washington". The paper "Beyond the Glass Box: Constraints as Objects. Jean-Francois Puget, Michel Leconte, ILPS'95", discusses what kind of constructs are needed to implement global constraints. Experimental results are also given, demonstrating significant speedups vs local propagation implementations. |> - Specific and structural constraints |> (in: CHIC lessons on CLP methodology, ECRC-report) The CHIC project (Constraint Handling in Industry and Commerce, Esprit project number 5291) was finished at the end of 1994. One of its result concerns the CLP methodology, with a big emphasis on the qualification phase: given a (instance of a) problem, (try to) predict if: - it is feasible, - it needs the coding of new constraints (e.g. the cooperation of OR [operations research] algorithms and propagations). One of the first phases of the methodology is to differentiate specific and structural constraints: Structural constraints deals with global properties of the problem and act on variables playing similar roles (the sub-problem is homogeneous). For example, you can easily encode a flow transportation problem in a CLP using elementary arithmetic constraint. Netherless, there is a more global structure (a graph) that represents the problem together with a _structural_ constraint (flow conservation) to express it. At the opposite, specific constraints depends on the instance of the application. |> Also I would appreciate pointers to papers that explicitly deal with |> problem solving systems for a combination of continuous and symbolic |> constraints. You could have a look at "H. Beringer and B. De Backer. Combinatorial Problem Solving in Constraint Logic Programming with cooperating Solvers. In C. Beierle and L. Plumers Editors, Logic Programming: Formal methods and Practical Applications, Elsevier Science B.V. 1995" ---------------------------------------------------------- Michel Leconte net : leconte@ilog.fr ILOG S.A. tel : +33 1 49 08 35 00 9, rue de Verdun - BP 85 fax : +33 1 49 08 35 10 F-94253 Gentilly Cedex url : http://www.ilog.com FRANCE url : http://www.ilog.fr ---------------------------------------------------------- >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Newsgroups: comp.constraints From: micha@ecrc.de (Micha Meier) Subject: Re: Question: constraint terminology Organization: European Computer-Industry Research Centre Date: Tue, 4 Jul 1995 08:10:44 GMT The term 'global constraints' has been used in CHIP to actually denote constraints that subsume a set of other constraints. It does not necessarily mean that complete global consistency is being achieved, but just the fact that more consistency is being achieved than by considering each constraint in this set separately. This concerns mainly finite domain constraints where global consistency is hard to obtain. The term 'global constraints' is quite misleading, and it should be replaced by something more appropriate like e.g. 'composite constraints'. Note that you can have several global constraints with the same declarative reading, but with different algoritm being used and thus different levels of consistency being achieved. --- Micha Meier ------------------------------------------------ ECRC, Arabellastr. 17 The opinions expressed above are private D-81925 Munich 81 and may not reflect those of my employer. micha@ecrc.de, Tel. +49-89-92699-108, Fax +49-89-92699-170 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> From: walter@wolf.uni-koblenz.de (Walter Hower) Newsgroups: comp.constraints Subject: Re: Question: constraint terminology Date: 03 Jul 1995 09:27:39 GMT Organization: University Koblenz / Germany @Article{David:95, author = "Philippe David", title = "{Using Pivot Consistency to Decompose and Solve Functional CSPs}", journal = "Journal of Artificial Intelligence Research", year = 1995, volume = 2, pages = "447--474", month = "May", note = "AI Access Foundation and Morgan Kaufmann Publishers" } @InProceedings{Dechter:vanBeek:95, author = "Rina Dechter and Peter {van Beek}", title = "{Local and Global Relational Consistency---Summary of Recent Results}", editor = "Ugo Montanari", series = "Lecture Notes in Computer Science", booktitle = "Principles and Practice of Con\-straint Programming", year = "1995", publisher = "Proceedings, Springer-Verlag, Berlin/Heidel\-berg", month = "September 19-22,", note = "CP95, First International Conference, Cassis, France", } @InProceedings{Haroud:Faltings:PPCP94, author = "Djamila Haroud and Boi Faltings", title = "{Global Consistency for Continuous Constraints}", editor = "Alan Borning", volume = "874", series = "Lecture Notes in Computer Science", pages = "40--50", booktitle = "Principles and Practice of Con\-straint Programming", year = "1994", publisher = "Proceedings, Springer-Verlag, Berlin/Heidel\-berg", month = "May 2-4,", note = "Second International Workshop, PPCP '94, Rosario, Orcas Island, WA, USA", } @InProceedings{Jeavons:et:al:95, author = "Peter Jeavons and David Cohen and Marc Gyssens", title = "{A Unifying Framework for Tractable Constraints}", editor = "Ugo Montanari", series = "Lecture Notes in Computer Science", booktitle = "Principles and Practice of Con\-straint Programming", year = "1995", publisher = "Proceedings, Springer-Verlag, Berlin/Heidel\-berg", month = "September 19-22,", note = "CP95, First International Conference, Cassis, France", } @InProceedings{Liu:95, author = "Bing Liu", title = "{Increasing Functional Constraints Need to Be Checked Only Once}", booktitle = "{IJCAI-95, Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence}", year = "1995", editor = "Chris Mellish", organization = "IJCAII", address = "Montr{\'{e}}al, Qu{\'{e}}bec, Canada", month = "August 20--25,", note = "Distributed by Morgan Kaufmann Publishers, Inc., San Francisco, California, USA" } >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Abderrahmane Aggoun (aggoun@cosytec.fr) sent the following references by email to Peter, concerning global constraints in CHIP: @Article{Aggoun:Beldiceanu:93, author = "Abderrahmane Aggoun and Nicolas Beldiceanu", title = "{Extending CHIP in order to solve complex scheduling and placement problems}", journal = "Mathl. Comput. Modelling", year = 1993, volume = 17, month = "no. 7", pages = "57--73", } @Article{Beldiceanu:Contejean:94, author = "N. Beldiceanu and E. Contejean", title = "{Introducing global constraints in CHIP}", journal = "Mathl. Comput. Modelling", year = 1994, volume = 20, month = "no. 12", pages = "97--123", } ---------------------------------------------------------------- Subject: [1-23] CLP(R) and analog circuit diagnosis Entry by Franc Novak, Jozef Stefan Institute, Ljubljana, Slovenia franc.novak@ijs.si http://martin.ijs.si/novak/novak.html F.Novak, I.Mozetic, M.Santo-Zarnik, A.Biasizzo. Enhancing design-for-test for active analog filters using CLP(R). Journal of Electronic Testing: Theory and Applications, Kluwer Ac. Publ. Vol.4, No. 4, 1993, pp.315-329. We describe a computer-aided approach to automatic fault isolation in active analog filters which enhances the design-for-test (DFT) methodology proposed by Soma (1990). His primary concern was in increased controllability and observability while the fault isolation procedure was sketched only in general terms. We operationalize and extend the DFT methodology by using CLP(R) to model analog circuits and by a model-based diagnosis approach to implement a diagnostic algorithm. CLP(R) is a logic programming language which combines symbolic and numeric computation. The diagnostic algorithm uses different DFT test modes and results of voltage measurements for different frequencies and computes a set of suspected components. Ranking of suspected components is based on a measure of (normalized) standard deviations from predicted mean values of component parameters. The diagnosis is performed incrementally, in each step reducing the set of potential candidates for the detected fault. Presented case studies show encouraging results in isolation of soft faults of a given low pass biquad filter. ---------------------------------------------------------------- Subject: [1-24] Constraint Abstraction by Chris Beck (chris@{cs,ie}.utoronto.ca) Given CSP C to solve, we would like to know how to transform it into CSP C' such that: 1) C' is more easily solved than C. 2) Solving C' provides knowledge that makes the subsequent search for a solution to C easier. 3) The transformation from C to C' can be efficiently achieved. The transformation of C to C' is the "abstraction" of C to the "higher-level" C'. Berthe Y. Choueiry (choueiry@liasun1.epfl.ch) notes: } Since a CSP has the following components: } - a set of variables } - a set of values per variable } - a set of constraints } } Abstraction techniques could potentially be applied to any of these } components. Here follows a *NON-EXHAUSTIVE* list of *examples*: } } Abstracting variables: } - good old techniques of graph reduction } - various strategies clustering (aggregations etc..) } } Abstracting values: } - (heuristic) domain reduction } - more formally, interchangeability (defined by Freuder, also } studied by Haselboeck, and applied to resource allocation } by myself). } } Constraint abstraction: } - such as scoping, localization, decomposition, conflict } isolation. etc.. } - generalization (mainly for explanation purposes..) } } These techniques could be probabilistic, heuristic, exact, etc.. } There is a trend to formally evaluate these techniques or the problems } they are being applied to, in terms of computational complexity. The following references provide a starting point: @InProceedings{ellman-ijcaij93, author = "Ellman, Thomas", title = "Abstraction by Approximate Symmetry", pages = "916-921", booktitle = "IJCAI'93: Proceedings of the 13th International Joint Conference on Artificial Intelligence", year = 1993 } @InProceedings{ellman-ml93, author = "Ellman, Thomas", title = "Synthesis of Abstraction Hierarchies for Constraint Satisfaction by Clustering Approximately Equivalent Objects", pages = "104-111", booktitle = "Proceedings of International Conference on Machine Learning", year = 1993 } @InProceedings{dalal-ccai92, author = "Dalal, M and Etherington, D.", title = "Tractable Approximate Deduction Using Limited Vocabularies", pages = "206-212", booktitle = "Proceedings of the 9th Canadian Conference on Artificial Intelligence", year = 1992 } @InProceedingsimiel-ijcaij87, author = "Imielinski, T.", title = "Domain Abstraction and Limited Reasoning", pages = "997-1003", booktitle = "IJCAI'87: Proceedings of the 10th International Joint Conference on Artificial Intelligence", year = 1987 } @Article{giunch-ai92, author = "Giunchiglia, F. and Walsh, T.", title = "A Theory of Abstraction", journal = "Artificial Intelligence", year = 1992, volume = 57, pages = "323-389" } @Article{schaerf-ai95, author = "Schaerf, M. and Cadoli, M.", title = "Tractable Reasoning via Approximation", journal = "Artificial Intelligence", year = 1995, volume = 74, number = 2, pages = "249-310" } @InProceedings{schrag-sara95, author = "Schrag, R. and Miranker, D.", title = "An Evaluation of Domain Reduction: Abstraction for Unstructured CSPs", pages = "126-133", booktitle = "Proceedings of the Symposium on Abstraction, Reformulation, and Approximation", year = 1992, note = "http://www.cs.utexas.edu/users/schrag/SARA.ps" } @InProceedings{schrag-saim95, author = "Schrag, R. and Miranker, D.", title = "Abstraction and the CSP Phase Transition Boundary", pages = "126-133", booktitle = "Proceedings of the 4th International Symposium on Artificial Intelligence and Mathematics", year = 1995, note = "http://www.cs.utexas.edu/users/schrag" } @InProceedings{freuder-sabin-sara95, author = "Freuder, E. C. and Sabin, D", title = "Interchangeability Supports Abstraction and Reformulation for Constraint Satisfaction ", booktitle = "Proceedings of Symposium on Abstraction, Reformulation and Approximation (SARA'95)", year = 1995, note = "http://www.cs.unh.edu/csprojects/csp/csp.html" } ---------------------------------------------------------------- ;;; *EOF*