Path: news1.ucsd.edu!ihnp4.ucsd.edu!swrinde!newsfeed.internetmci.com!bloom-beacon.mit.edu!senator-bedfellow.mit.edu!faqserv From: jampel@cs.city.ac.uk (Michael Jampel) Newsgroups: comp.constraints,comp.answers,news.answers Subject: comp.constraints FAQ 1/2 Frequently Asked Questions [Monthly posting] Supersedes: Followup-To: comp.constraints Date: 16 Nov 1995 23:22:22 GMT Organization: Department of Computer Science, City University Lines: 1171 Approved: news-answers-request@MIT.Edu Expires: 30 Dec 1995 23:20:30 GMT Message-ID: Reply-To: jampel@cs.city.ac.uk (Michael Jampel) NNTP-Posting-Host: bloom-picayune.mit.edu Summary: Frequently asked questions about constraints X-Last-Updated: 1995/10/02 Originator: faqserv@bloom-picayune.MIT.EDU Xref: news1.ucsd.edu comp.constraints:734 comp.answers:12785 news.answers:49443 Archive-name: constraints-faq/part1 Last-Modified: Mon Oct 2 15:40:00 1995 by Michael Jampel Version: 1.79 Important Changes (since last posting): CLP(R) and analog circuits. Additional info on TOC: Theory of Constraints 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 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. 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 will soon be a new journal called CONSTRAINTS, pulished by Kluwer: Editor-in-Chief: Eugene C. Freuder, University of New Hampshire (ecf@cs.unh.edu) 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.html 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] Philippe Marti and Michel Rueher. A Distributed Cooperating Constraints Solving System, Research Report I3S, Bat. 4, 250 av. A. Einstein, 06560 Valbonne, France, March 1995 ---------------------------------------------------------------- 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. ---------------------------------------------------------------- ;;; *EOF* ---------------------------------------------------------------------- Path: news1.ucsd.edu!ihnp4.ucsd.edu!swrinde!newsfeed.internetmci.com!bloom-beacon.mit.edu!senator-bedfellow.mit.edu!faqserv From: jampel@cs.city.ac.uk (Michael Jampel) Newsgroups: comp.constraints,comp.answers,news.answers Subject: comp.constraints FAQ 2/2 Frequently Asked Questions [Monthly posting] Supersedes: Followup-To: comp.constraints Date: 16 Nov 1995 23:23:49 GMT Organization: Department of Computer Science, City University Lines: 1092 Approved: news-answers-request@MIT.Edu Expires: 30 Dec 1995 23:20:30 GMT Message-ID: References: Reply-To: jampel@cs.city.ac.uk (Michael Jampel) NNTP-Posting-Host: bloom-picayune.mit.edu Summary: Free and Commercial Constraint Systems X-Last-Updated: 1995/10/12 Originator: faqserv@bloom-picayune.MIT.EDU Xref: news1.ucsd.edu comp.constraints:735 comp.answers:12789 news.answers:49469 Archive-name: constraints-faq/part2 Last-Modified: Thu Oct 12 11:50:00 1995 by Michael Jampel Version: 2.21 Important Changes (since last posting): Ilog France address change. QUAD CLP(R) ftp address change. 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: In this part of the FAQ: [2-1] Introduction (same as in part 1) [2-2] Introduction to Systems for Non-Linear Constraints [2-3] Free and Commercial Constraint Systems In the other (first) part of this FAQ there are definitions, glossaries, explanations, a short bibliography, pointers to FTP and WWW archives and other resources, reviews and surveys of constraint systems, and basically everything else which is not in this part. Search for [#] to get to topic number # quickly. In newsreaders which support digests (such as rn), [CTRL]-G will page through the answers. ---------------------------------------------------------------- Subject: [2-1] Introduction This guide lists constraint-related resources: compilers and interpreters (in this part), archives, newsgroups, books, magazines, and anything else you can think of (all in part 1). 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. Permission to do reasonable things not for profit is given to anyone. Anything else, ask me. ---------------------------------------------------------------- Subject: [2-2] Introduction to Systems for Non-Linear Constraints A survey by Olga Caprotti Systems (discussed individually in this part): CAL CLP(F) GDCC ILOG Solver Newton QUAD-CLP(R) RISC-CLP(Real) The information has been added to the end of the entry for each individual system. Search for the phrase NON-LINEAR. Architectures (discussed in Part 1 of the FAQ): Cooperative Constraint Solvers Symbolic Representation Scheme ---------------------------------------------------------------- Subject: [2-3] Free and Commercial Constraint Systems See the comp.lang.prolog, comp.lang.lisp, comp.ai and comp.lang.scheme FAQs and Resource Guides for possibly more up-to-date and complete information. Note on costs: there is a difference between FREE software (which may have restrictions attached), Public Domain software (FREE-PD), CHEAP software (arbitrarily and approximately: less than 100 pounds or 200 dollars or 300 deutschmarks), shareware (CHEAP-SH), and software which is COMMERCIAL [to avoid calling it non-cheap or expensive]. Some software may not be available for commercial use, although commercial enterprises may be able to use it for their own research. These are labelled C=N/A. Costs may also vary depending on whether the customer is (A) academic, (E) Eastern European, or (C) a commercial enterprise. So each section here will have a header of the following form: [COST A=CHEAP,E=FREE,C=PRICE]. If something has the same cost for all groups, I abbreviate the entry to e.g. [COST FREE-PD]. Warning: there is no guarantee that this information is correct and it should not be treated as implying some kind of contract either on my part (FAQ maintainer) or on the part of the supplier. Please notify me of errors. AKL: [COST A=E=FREE,C=N/A] AKL (previously Andorra Kernel Language, now Agent Kernel Language) is a concurrent constraint programming language that supports both Prolog-style programming and committed choice programming. Its control of don't-know nondeterminism is based on the Andorra model, which has been generalised to also deal with nondeterminism encapsulated in guards and aggregates (such as bagof) in a concurrent setting. See, for example, Sverker Janson and Seif Haridi, "Programming Paradigms of the Andorra Kernel Language", in Proceedings of ILPS'91. MIT Press, 1991. Torkel Franzen, "Logical Aspects of the Andorra Kernel Language", SICS Research Report R91:12, Swedish Institute of Computer Science, 1991. Torkel Franzen, Seif Haridi, and Sverker Janson, "An Overview of the Andorra Kernel Language", In LNAI (LNCS) 596, Springer-Verlag, 1992. Sverker Janson, Johan Montelius, and Seif Haridi, "Ports for Objects in Concurrent Logic Programs", in Research Directions in Concurrent Object-Oriented Programming, MIT Press, 1993 (forthcoming). The above papers on AKL are available from . An (as yet non-released) prototype implementation of AKL is available for research purposes (contact sverker@sics.se). ALE: [COST FREE-PD] ALE (Attribute Logic Engine), a public domain system written in Prolog, integrates phrase structure parsing and constraint logic programming with typed feature structures as terms. Types are arranged in an inheritance hierarchy and specified for the features and value types for which they are appropriate. Grammars may also interleave unification steps with logic program goal calls (as can be done in DCGs), thus allowing parsing to be interleaved with other system components. While ALE was developed to handle HPSG grammars, it can also execute PATR-II grammars, DCG grammars, Prolog, Prolog-II, and LOGIN programs, etc. Grammars and programs are specified with a version of Rounds-Kasper Attribute Value Logic with macros and variables. ALE supports lexical rules and empty categories for grammars, using a bottom-up, breadth-first dynamic chart parser. ALE supports last call optimization, negation by failure and cuts in definite clauses, which may be used independently or integrated into grammars. The system is available free for research purposes, from Bob Carpenter . BERTRAND: [COST CHEAP-SH] Bertrand is the language described by Leler in his book (see section [1-6]). See [1-5] PTF for more details. BULL SOLVER: [COST COMMERCIAL] See ILOG SOLVER. CFSQP: [COST A=E=FREE,C=FREEish] See FSQP. CHARME: [COST COMMERCIAL] CHARME was a commercial product from Bull. The latest version is called BULL SOLVER, but see also ILOG SOLVER. CHIP: [COST COMMERCIAL] CHIP V4 (Constraint Handling In Prolog) is designed as an extension to Prolog offering three constraint solving domains: Integers, Rationals and Booleans. The system was originally developed at ECRC in Munich and now extended by the same team at COSYTEC in Paris. CHIP V4 includes extensions to the three domains: symbolic constraints, update demons and cumulative constraints. The system is available with optional interfaces for X11 and DOS graphics (XGIP), Oracle or Ingres database connection (QUIC), C language interface (CLIC) and embedded application interface (EMC). CHIP V4 is written completely in C, and is available on a range of workstations including SunSparc IBM RS6000, HP 9000/700, Decstations and PC386/486 (Dos 5.0). An academic discount is offered for educational and research purposes. For more information contact COSYTEC, Parc Club Orsay Universite 4 rue Jean Rostand, 91893 Orsay Cedex, France, phone +33-1-60-19-37-38, fax +33-1-60-19-36-20 or email . CHR: [COST FREE with ECLIPSE] Constraint Handling Rules (CHRs) is a library of ECLiPSe [see separate entry] for writing custom constraint systems in a high-level language. CHRs is essentially a committed-choice language consisting of guarded rules that rewrite constraints into simpler ones until they are solved. The usual formalisms to describe a constraint theory, i.e. inference rules, rewrite rules, sequents, first-order axioms, can be expressed as CHR programs in a straightforward way. The CHR release includes a full colour demo involving geometric constraints, a compiler (into ECLiPSe), two debuggers, a runtime system and 18 constraint solvers. There are solvers for lists, sets, trees, terms, finite and infinite domains, booleans, linear polynomials over reals and rationals, for incremental path consistency, and for terminological and temporal reasoning. CHR documentation is available by anonymous ftp from ftp.ecrc.de:/pub/eclipse/doc in the extensions-manual. You can also ftp a technical report describing constraint handling rules (file ECRC-92-18.ps.Z in directory pub/ECRC_tech_reports/reports) and their application to temporal and terminological reasoning (files ECRC-94-05.ps.Z and ECRC-94-06.ps.Z). For more information on CHRs contact Thom Fruehwirth (thom@ecrc.de). CIAL 1.0 (Beta) [COST FREE] CIAL is an interval constraint logic programming language. The main difference between CIAL and other CLP(Interval) languages is that a linear constraint solver, which is based on preconditioned interval Gauss-Seidel method, is embedded in CIAL in addition to the interval narrowing solver. The main motivations for a linear solver are: * Pure interval narrowing fails to narrow the intervals to any useful width even for such simple systems as {X+Y=5, X-Y=6}. Interval splitting may help but is costly. * Pure interval narrowing cannot always detect inconsistency or halt (in a reasonable time). A simple example is {A+1=D, A+B=D, A>0, B<0}. * Efficient linear constraint solver is also important to the study of efficient non-linear constraint-solving. Recent results show that interval Newton method works better than pure interval narrowing for solving non-linear constraints, but may require to solve many linear constraints in order to give the best results. This version of CIAL prototype is implemented as an extension to CLP(R) v1.2 and tested on Sun Sparc machines. You should have obtained CLP(R) from IBM prior to installing CIAL. Our distribution is in the form of patches to the CLP(R) sources. [See entry on CLP(R) below]. E-mail cial@cs.cuhk.hk to request CIAL, and for more details. [FAQ maintainer's note: I have deleted most of the references provided, for space reasons, if they are in well-known journals and conferences; the CIAL team have not simply cited only their own work. MBJ.] C.K. Chiu and J.H.M. Lee. Towards practical interval constraint solving in logic programming. (To appear) In Proceedings of the Eleventh International Logic Programming Symposium, Ithaca, USA, Nov.1994. J.H.M. Lee and T.W. Lee. A WAM-based abstract machine for interval constraint logic programming and the multiple-trailing problem. Proceedings Sixth IEEE International Conference on Tools with Artificial Intelligence, New Orleans, Nov 1994. CLP(BNR): [COST ???] CLP(BNR) [Constraint Logic Programming with Booleans Naturals and Reals] is an experimental CLP Language developed at the Bell-Northern Research Computing Research Lab. CLP(BNR) is a Prolog-based language that incorporates an arc-consistency propagation algorithm on interval-bounded constraints which handles general algebraic constraints over continuous, integer and boolean variables. This allows programmers to express systems of non-linear equations on real intervals that can be arbitrarily mixed with integer and boolean constraints equations. For more information on CLP(BNR) contact Andre' Vellino (613)763-7513, fax (613)763-4222 Bell-Northern Research, Box 3511, Station C, Ottawa, CANADA K1Y 4H7 See also section [1-6] for papers by Benhamou/ Older/ Vellino. CLP(F): NON-LINEAR [unavailable] This extension of CLP(Intervals) has an underlying domain that consists of boolean, integers, reals, real-valued functions of one variable, and vectors of domain elements. Function variables are constrained by functional equations and by putting interval constraints on the values of their derivatives at points and intervals. The system can be used to solve constraint problems involving ordinary differential equations. Contact Tim Hickey Reference: [1] T. Hickey. CLP(F) and Constrained ODE's, T. Proceedings of the 1994 Workshop on Constraints and Modelling, Ithica, NY, November, 1994. Available at: ftp://ftp.ecrc.de/pub/faculty/tim/Papers/islp94.ps CLP(FD): [COST FREE] CLP(FD) 2.2 is a constraint logic programming language over Finite Domains. It is based on the wamcc Prolog compiler which translates Prolog to C. It provides several constraints "a la CHIP" on Finite Domains and Booleans and some facilities to build new constraints. clp(FD) is 4 times faster than CHIP v3.2 on average. Available from ftp.inria.fr:/INRIA/Projects/ChLoE/LOGIC_PROGRAMMING/clp_fd Requires GNU C (gcc) version 2.4.5 or higher. Ported to Sparc workstations, PC under linux, sony mews, dec ultrix, portable generally to 32-bit machines with gcc. See also under WAMCC, below. For more details, contact the author Daniel Diaz INRIA Rocquencourt, FRANCE. CLP(R): [COST A=FREE,E=FREE,C=N/A] [Commercial users: see next section] CLP(R) is a constraint logic programming language with real-arithmetic constraints. The implementation contains a built-in constraint solver which deals with linear arithmetic and contains a mechanism for delaying nonlinear constraints until they become linear. Since CLP(R) subsumes PROLOG, the system is also usable as a general-purpose logic programming language. It includes facilities for meta-programming with constraints. The system consists of a compiler, byte-code emulator, and constraint solver. CLP(R) is written entirely in C and runs on Suns, Vaxen, MIPS-based machines (Decstations, Silicon Graphics), IBM RS6000s and PS2s. Includes MS-DOS support. It is available free from IBM for academic and research purposes only. For more information, write to Joxan Jaffar, H1-D48, IBM Thomas J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, or send email to joxan@watson.ibm.com or joxan@yktvmh.bitnet. Current version 1.2. CLP(R): [COST CHEAP] CLP(R) is a constraint system from Monash University for VAX, Sun, and Pyramid (Unix). Costs $150. For more information, write to Monash University, CLP(R) Distribution, Department of Computer Science, Clayton, Victoria 3168, Australia, or send email to clp@moncsbruce.oz.au. [Although the system is still available, it has not been maintained or supported for about 5 years, and it will remain that way.] COOLDRAW: [COST FREE-PD] A constraint-based drawing package from the same stable as ThingLabII. See information on the Seattle ftp site in section [1-5]. CONTAX: [COST FREE-PD] Public domain constraint system written by Manfred Meyer . [More details soon.] CU-PROLOG: [COST FREE] cu-Prolog is an experimental constraint logic programming language available free from Japan's Institute for New Generation Computer Technology (ICOT). Unlike most conventional CLP systems, cu-Prolog allows user-defined predicates as constraints and is suitable for implementing a natural language processing system based on the unification-based grammar. For example, the cu-Prolog developers implemented a JPSG (Japanese Phrase Structure Grammar) parser in cu-Prolog with the JPSG Working Group (the chairman is Prof. GUNJI, Takao of Osaka University) at ICOT. cu-Prolog is a complete implementation of Constraint Unification (cu), hence the name. cu-Prolog is implemented in C for BSD UNIX 4.2/3. Professor Sirai of Chukyo-University has also implemented cu-Prolog for the Apple Macintosh and DJ's GPP (80386/486 MS-DOS machine with the DOS extender). Available free by anonymous ftp: see section [1-5]. DELTABLUE: [COST FREE-PD] A constraint-solving algorithm. See information on the Seattle ftp site in section [1-5]. See paper by Freeman-Benson et al in section [1-6]. ECHIDNA: [COST FREE] Echidna is an object oriented constraint logic programming language developed by the Intelligent Systems Lab at Simon Fraser University between 1990 and 1993. Constraints in Echidna include finite domain constraints (as in CHIP) and disjoint real interval domain constraints. Real domains are implemented by interval hierarchies which allow for the representation of domains with disjoint sets of intervals. Hierarchical domains also allow control of the precision of constraint processing. Since complete search procedures exist for all levels of precision, it is possible to quickly search through regions with no solutions at low precision. Where low precision constraint processing indicates a possible solution, precision can be increased to ensure convergence on a real solution. Echidna supports a form of incremental intelligent backtracking for multiple user queries which provides an effective interactive mixed-initiative control regime. Users can issue and selectively retract queries to arrive at a solution to their problem. Development and support for Echidna v1.0 were halted in 1993. For more information, go to or or contact Bill Havens . See: [1] W.S. Havens: Intelligent Backtracking in the Echidna CLP Reasoning System, International Journal of Expert Systems: Research and Applications 5(4), 1992, M. Harandi (ed.), Jai Press, London, 21-45. [2] Greg Sidebottom and W.S. Havens: Hierarchical Arc Consistency for Disjoint Real Intervals in Constraint Logic Programming. Computational Intelligence 8(4), 1992. 601-623. Also available as . ECLIPSE: [COST A=CHEAP,E=FREE,C=see below] ECLiPSe (ECRC Logic Programming System) combines the functionalities of several ECRC systems, including Sepia, MegaLog and CHIP. ECLiPSe includes a Prolog compiler with extended functionality that is Quintus and SICStus compatible, a tightly connected database system based on the BANG file system, a CLP system, and an interface to the Tcl/Tk X11 toolkit. The BANG database can store not only relations, but also any Prolog structures and programs. The CLP system contains several libraries with various types of constraint handling schemes, including atomic finite domains, linear rational constraints, CHR (constraint handling rules) and Propia (generalised propagation). See also the separate entry for CHR.] It also supports writing further extensions like new user-defined constraints or complete new constraint solvers. ECLiPSe also includes a profiler, user-definable syntax, metaterms as first-class citizens, coroutining, and unlimited precision integer and rational numbers. ECLiPSe is available for a nominal fee of DM 300 (~$200) to all academic and government-sponsored organizations. Commercial users may obtain ECliPSe for DM 7000, but for research purposes only. It is distributed in binary form for Sun-3, Sparc, and many other types of machine. Send orders or requests for further information to eclipse_request@ecrc.de or write to ECRC, Arabellastrasse 17, 81925 Munich, Germany. The ECLiPSe documentation (ASCII and dvi) and some shareware packages ported to ECliPSe are now available by anonymous ftp from ecrc.de:/pub/eclipse. To subscribe to the eclipse_users@ecrc.de mailing list, send mail to eclipse_request@ecrc.de. ECRC SEPIA: [COST FREE with ECLIPSE] See ECLIPSE. SEPIA is no longer delivered as a stand-alone system, but as a part of ECLiPSe. FSQP/CFSQP: [COST A=E=FREE,C=FREEish] FSQP (Feasible SQP; FORTRAN; developed by J.L. Zhou and A.L. Tits) and CFSQP (C version of same, with enhancements; port and enhancements due to C.T. Lawrence) are software packages aimed at solving constrained optimization problems, including constrained minimax problems (where the max is taken over a finite number of smooth functions). (C)FSQP's main distinguishing feature is that all the iterates it generates satisfy the constraints, except for nonlinear equality constraints, for which mere "semi-feasibility" is maintained (given a scalar constraint h(x)=0, if h(x0)<=0 (resp. >=0), then h(xk)<=0 (resp. >=0) for all k.) This is of value in many engineering related problems. Extensive numerical tests show that FSQP's efficiency is comparable to that of the most popular (non-"feasible") codes. Detailed User's Manuals are available. (C)FSQP is available free of charge to academic and other non-profit organizations (as well as, for an evaluation period, to for-profit organizations) but may not be redistributed without the authors' approval. To obtain FSQP or CFSQP, please contact Andre Tits (andre@eng.umd.edu). GARNET: [COST FREE] The Garnet system is a fully functional user interface development environment and toolkit implemented on top of a comprehensive one-way constraint system. It is in CommonLisp for X/11. All widgets and other user interface elements are implemented using the constraint. The constraints are implemented as part of the object system, and the object system with constraints can be used independently of the user-interface components, if desired. Garnet is available for free by anonymous FTP from a.gp.cs.cmu.edu (128.2.242.7). Retrieve /usr/garnet/garnet/README. More information on Garnet is available from http://www.cs.cmu.edu:8001/Web/Groups/garnet/garnet-home.html or in the newsgroup comp.windows.garnet or e-mail garnet@cs.cmu.edu. See also [1-5] PTF for more details. See also Multi-GArnet, below. GOEDEL: [COST FREE] Goedel is intended to be a declarative successor to Prolog. It is defined as supporting certain constraint domains, but these are not yet implemented. See the comp.lang.prolog FAQ for more details. ICOT language CU-PROLOG: See entry CU-PROLOG. ICOT language CAL in ESP: [COST FREE] To execute this system, SIMPOS Ver.7 must be running on your PSI. CAL is a sequential constraint logic programming language which can deal with various constraints including non-linear polynomial equations. In the CAL system, you can use Context. A context is a constraint set. A new context is created whenever the constraint set is changed. The history of changing contexts is manipulated by the Context Tree, and Current Context is the target of the context manipulation. You can set a context on the context tree arbitrarily as the current context. Functions include finding real roots: The query "find" computes real roots of the univariate equations and returns one solution. The user can obtain other solutions by backtrack, and branches of the context tree are created. The CAL system has 4 constraint solvers, (1) Algebraic constraint solver (2) Boolean constraint solver (3) Linear constraint solver (4) Set constraint solver Available free by anonymous ftp: see section [1-5]. A. Aiba, K. Sakai, Y. Sato, D. J. Hawley, and R. Hasegawa: Constraint Logic Programming Language CAL. In Proceedings of the International Conference on Fifth Generation Computer Systems 1988, November 1988. Contrainte Avec Logique version 2.12 User's manual Institute for New Generation Computer Technology, in preparation. ICOT language CAL Common ESP version written in CESP: [COST FREE] Same as CAL in ESP, but can run on Unix, needing: UNIX machine, Emacs CESP, C language compiler, GNU MP, 50Mbyte disk, 16Mbyte memory Available free by anonymous ftp: see section [1-5]. CAL: NON-LINEAR CAL was developed at ICOT (Institute for New Generation Computer Technology) in a Japanese national project, Fifth Generation Computer Project. CAL utilizes Buchberger algorithm to deal with linear and non-linear algebraic equation constraints. See previous entries for more details or contact Akira Aiba References: [1] Ko Sakai, Akira Aiba. CAL : A Theoretical Background of Constraint Logic Programming and Its Application. Journal of Symbolic Computation (1989) 8, pp. 589 -- 603 ICOT language Hierarchical CLP Language CHAL: [COST FREE] You need the SIMPOS/ESP environment to run CHAL. Hierarchical Constraint Logic Programming Language: CHAL A hierarchical constraint logic programming language processor which introduces hierarchy in terms of strength of constraints. Hierarchical constraint logic programming language CHAL consists of constraint hierarchy solver which manipulates various strength of constraints in various domains and constraint language processor. An Extension of Constraint Logic Programming Language Usual constraint logic programming languages output nothing if there is no solution for given constraints. On the other hand, by introducing hierarchy of strength in constraints, CHAL ignores some weak constraints in order to output some better solutions. This function is important in planning and design problems. Available free by anonymous ftp: see section [1-5]. ICOT language PCHAL: [COST FREE] Hierarchical Constraint Parallel Solver: P-CHAL Similar to CHAL, above. Parallel Solving of Constraint Hierarchy: P-CHAL reduces computational costs by a bottom-up calculation of maximal consistent sets and parallel processing of GDCC. Available free by anonymous ftp: see section [1-5]. ICOT language Knowledge Representation Language Quixote: [COST FREE] Main documentation in Japanese. Quixote is a DOOD (Deductive Object-Oriented Database) system developed at ICOT. The following are outstanding Quixote features. 1. Object identity defined over extended terms (object terms). 2. Constraints in terms of subsumption relation among object terms. 3. Property inheritance among objects. 4. Modularized and hierarchical knowledge bases defined by modules and rule inheritance between them. 5. Queries having additional assertions to knowledge bases, and answers with assumed constraints. Available free by anonymous ftp: see section [1-5]. Kazumasa Yokota, Deductive Object-Oriented Databases, Computer Software, Vol.9, No.4, pp3--18, 1992 (in Japanese). Hideki Yasukawa, Hiroshi Tsuda, and Kazumasa Yokota, Object, Properties, and Modules in QUIXOTE, Proc. of FGCS92, pp257--268, 1992. Quixote Ver.III consists of (1) Quixote client on UNIX with C, X-Window(X11R5), and GNU-Emacs, and (2) Quixote server on PIM/PIMOS with KL1. Both UNIX workstation (such as SS2) and PIM/PSI are required to run this version of Quixote. ICOT language Micro Quixote (Version 0.5): [COST FREE] Micro Quixote is another implementation of the language Quixote. It is implemented with C. It eliminates many features of Quixote, and only implements core feature of Quixote. However, it's small, and easy to install. And more, it is expected that Micro Quixote could run on other operating systems apart from Unix. Available free by anonymous ftp: see section [1-5]. ICOT language GDCC (Guarded Definite Clauses with Constraints): [COST FREE] GDCC is the parallel constraint logic programming experimental system. GDCC has been developed on PIMOS and runs only on PIMOS. Therefore, PIMOS needs to be installed on your machine before GDCC is installed. Includes linear constraints, boolean constraints, and the find utility (Algebraic constraint solver) which is used to find approximate real roots from the results of solving algebraic constraints. Available free by anonymous ftp: see section [1-5]. GDCC: NON-LINEAR GDCC was developed at ICOT in a Japanese national project, Fifth Generation Computer Project. GDCC utilizes Buchberger algorithm to deal with linear and non-linear algebraic equation constraints. Different from CAL, GDCC is a parallel CLP language based on cc paradigm. There are two versions of GDCC, one is a system written in KL1, a parallel logic programming language, that runs on a parallel inference machine called PIM developed in the project, and the other is a system written in KLIC that is a KL1 language processor for UNIX workstations. See previous entry or contact Akira Aiba References: [1] Satoshi Terasaki, David J. Hawley, Hiroyuki Sawada, Ken Satoh, Satoshi Menju, Tarou Kawagishi, Noboru Iwayama, and Akira Aiba. Parallel Constraint Logic Programming Language GDCC and Its Parallel Constraint Solvers. International Conference on Fifth Generation Computer Systems 1922, Tokyo [2] Hiroyuki Sawada, Satoshi Terasaki, and Akira Aiba. Parallel Computation of Groebner Bases on Distributed Memory Machines. Journal of Symbolic Computation, Vol.18, No.3, pp.207--222, September 1994. IF/Prolog 5.0 [COST COMMERCIAL] IF/Prolog 5.0 is a full ISO-compliant Prolog which incorporates constraint solving technology. IF/Prolog is available on ALL UNIX systems, VMS, OSF/1, MS-Windows and Mainframes. Constraint domains include Boolean constraints, Rational terms, Linear terms, Equations and Inequations, Finite Domain Constraints and Co-routines. Interfaces to standard software packages and other programming languages including C, C++ and FORTRAN, SQL (Ingres, Oracle and Informix) and X11 (Motif and Athena widgetsets). IF/Prolog has full screen X11 and Windows based debuggers and online hypertext help and quick reference guide. IF/Prolog 5.0 is available on ALL UNIX, OSF/1, VMS and MS-Windows, OS/2 platforms. There is a 50% accademic discount and demo licences are avilaible. Further information contact: Annette Kolb (marketing) or Dr. Andrew Verden (technical) at IF Computer GmbH, Ludwig-Thoma-Weg 11a, D-82065 Baierbrunn, tel +49 89 7936 0037, fax +49 89 7936 0039. E-mail prolog@mch.sni.de ILOG SCHEDULE: [COST COMMERCIAL] ILOG SCHEDULE is an add-on to ILOG SOLVER, used to develop finite capacity scheduling applications. ILOG SCHEDULE includes a natural object model for representing schedules in terms of activities and resources used and shared by these activities. Three categories of constraints are predefined: - TEMPORAL CONSTRAINTS. Users may link any two activities together by any type of precedence constraint. Minimum and maximum delays between activities can be imposed. - CAPACITY CONSTRAINTS. Unary resources represent resources of capacity one. Volumetric resources represent resource pools of non-differentiated resources. State resources represent situations where an activity uses a resource only under specific conditions. The capacity of a resource can be constrained either at each time unit or over given time periods. - RESOURCE UTILIZATION CONSTRAINTS. An activity may require, consume, provide and produce resources, in an amount represented either as a constant or as an ILOG SOLVER variable. This allows the representation of the case where the duration of the activity varies with the amount of resources assigned to the activity. ILOG SCHEDULE is available on the same platforms as ILOG SOLVER. For further information and contact addresses, see entry on ILOG SOLVER. ILOG SOLVER: [COST COMMERCIAL] [Ilog and Bull have agreed to sell the same thing under different names. Charme Object and Ilog Solver have been merged. M Jampel.] ILOG SOLVER (formerly called PECOS) is a highly efficient C++ class library that implements constraint programming. SOLVER has been used to develop fielded applications handling large problems in areas such as job shop scheduling, timetabling, configuration, transport, logistic planning, network routing, and frequency allocation. SOLVER implements integer variables, floating point variables, Boolean variables, and set variables. Constraints include =, <=, >=, <, >, +, -, *, /, subset, superset, union, intersection, member, Boolean or, Boolean and, Boolean not, Boolean xor, cardinality, element, generic constraints, and meta constraints (conjunction and disjunction of constraints, order among constraints). Non-linear constraints can be solver by interval approximation methods. You can add new constraints to SOLVER by deriving new C++ classes. SOLVER provides a backtracking search and a branch-and-bound algorithm together with a large number of search strategies. SOLVER also provides C++ classes and functions that implement non-deterministic programming. SOLVER is available on most Unix platforms and on MS-Windows. For further information, please contact: - In the USA and Canada: - Outside the USA: ILOG, Inc. ILOG SA 2005 Landings Drive 9, rue de Verdun, BP 85, Mountain View, CA 94303. 94253 Gentilly Cedex, France Phone: +415 390-9000 Phone: +33 1 4908 3500 e-mail: info@ilog.com e-mail: info@ilog.fr URL: http://www.ilog.com URL: http://www.ilog.fr LIFE: [COST FREE] LIFE (Logic, Inheritance, Functions, and Equations) is an experimental programming language with a powerful facility for structured type inheritance. It reconciles styles from functional programming, logic programming, and object-oriented programming. It subsumes the functionality of its precursor languages LOGIN and Le_Fun, and may be seen as an extension of Prolog. The syntax of Wild_LIFE has been kept as close as possible to that of the Edinburgh standard for Prolog. LIFE offers natively high-level abstraction facilities and convenient data and control structures particularly well-suited for AI programming. LIFE implements a constraint logic programming language with equality (unification) and entailment (matching) constraints over order-sorted feature terms. The interplay of unification and matching provides an implicit coroutining facility thanks to an automatic suspension mechanism. This allows interleaving interpretation of relational and functional expressions which specify structural dependencies on objects. The Wild_LIFE interpreter is the first implementation of the LIFE language available to the general public. It is a product of the Paradise project at Digital Equipment Corporation's Paris Research Laboratory (DEC PRL). Wild_LIFE runs on DECstations (Ultrix), SparcStations and RS/6000 systems and should be portable to other Unix workstations. It is implemented in C, and includes an interface to X Windows. Wild_LIFE is available by anonymous ftp from gatekeeper.dec.com:/pub/plan as the file Life.tar.Z. To be added to the mailing list (life-users@prl.dec.com), send mail to life-request@prl.dec.com. Send bug reports to life-bugs@prl.dec.com. See also [1-5] PTF for more details. NEWTON: NON-LINEAR [unavailable] The constraint group at Brown University has developed a CLP language called Newton to solve - systems of nonlinear equations and inequalities - unconstrained optimization - constrained optimization The language uses interval arithmetic and is based on a box-consistency on various interval extensions. It is competitive with continuation methods on their benchmarks, outperforms all interval methods we know of, and has solved traditional benchmarks from numerical analysis containing hundreds of variables. Contact Pascal Van Hentenryck References: [1] F. Benhamou, D. McAllister, P. Van Hentenryck. CLP(Interval) Revisited, in ILPS'94, Ithaca, NY, November 1994. [2] P. Van Hentenryck, D. McAllister, D. Kapur. Solving Polynomial System using A branch and Prune Approach. Forthcoming. [3] P. Van Hentenryck, L. Michel. The Design and Implementation of Newton. In CCP'95, Venice, Italy, May 1995. NICOLOG: [COST FREE] Nicolog is a CLP language with the capabilities of CLP(BNR) and most of the capabilities of cc(FD). Constraints in Nicolog are compiled into a generalization the indexical constraints found in cc(FD) and clp(FD). This generalization of indexical constraints is called projection constraints. Projection constraints add conditional operators which allow the implementation of the cardinality, blocking implication, and constructive disjunction constraints found in cc(FD). Nicolog has a very simple implementation (5000 lines of Prolog for the compiler and 5000 lines of C++ for the extended WAM emulator) and yet runs as fast as emulator based CLP languages such as cc(FD) and CLP(BNR). Moreover, the possibility of programming directly in projection constraints makes Nicolog more flexible than other CLP systems. For more information, go to or or contact Greg Sidebottom or see . OPBDP: [COST FREE] opbdp is an implicit enumeration algorithm for solving linear 0-1 optimization problems, including a bunch of heuristics for selecting a branching literal. Several preprocessing techniques (coefficient reduction, fixing, equation detection). Preprocessed problem can written to a file readable by CPLEX and lp_solve. Technical report included. If your favorite linear-programming based solver fails on your problem you might give opbdp a chance. Needs a C++ compiler which supports templates. Contact Peter Barth (barth@mpi-sb.mpg.de). ftp://ftp.mpi-sb.mpg.de/pub/guide/staff/barth/opbdp/ http://www.mpi-sb.mpg.de/~barth OMEGA: [COST FREE] Version 0.90 of the Omega Calculator and Omega Library is now available, including source code. The Omega library/calculator manipulates sets of integer tuples and relations between integer tuples. Some examples include: { [i,j] : 1 <= i,j <= 10}; { [i] ->[i,j] : 1 <= i < j <= 10}; { [i,j] ->[j,j'] : 1 <= i < j < j' <= n}; The conditions describing a set or tuple can be an formulas can described by an arbitrary Presburger formula. Relations and sets can be combined using functions such as composition, intersection, union and difference. It also provides routines to generate code to iterate over the points in an integer tuple set. The Omega library provides a high-level, C++ interface to our routines. The Omega calculator is a text-based interface to the Omega library. Omega is available for anonymous ftp from ftp.cs.umd.edu:pub/omega/omega_library. More information is available by email from omega@cs.umd.edu on the www at http://www.cs.umd.edu/projects/omega/. OZ: [COST FREE] Oz is a concurrent constraint programming language designed for applications that require complex symbolic computations, organization into multiple agents, and soft real-time control. It is based on a new computation model providing a uniform foundation for higher-order functional programming, constraint logic programming, and concurrent objects with multiple inheritance. From functional languages Oz inherits full compositionality, and from logic languages Oz inherits logic variables and constraints (including feature and finite domain constraints). Search in Oz is encapsulated (no backtracking) and includes one, best and all solution strategies. DFKI Oz is an interactive implementation of Oz featuring a programming interface based on GNU Emacs, a concurrent browser, an object-oriented interface to Tcl/Tk, powerful interoperability features (sockets, C, C++), an incremental compiler, a garbage collector, and support for stand-alone applications. Performance is competitive with commercial Prolog and Lisp systems. DFKI Oz is available for many platforms running Unix/X, including Sparcs and 486 PCs. Applications DFKI Oz has already been used for include simulations, multi-agent systems, natural language processing, virtual reality, graphical user interfaces, scheduling, placement problems, and configuration. Version 1.0 of DFKI Oz (January 23, 1995) is available by anonymous ftp from ps-ftp.dfki.uni-sb.de:/pub/oz, or through the WWW from http://ps-www.dfki.uni-sb.de/ Tutorials, reference manuals, and research papers are available from the same sources. You may start with "A Survey of Oz" (8 pages) and continue with "An Oz Primer" (110 pages). For specific questions mail oz@dfki.uni-sb.de. To join the Oz users mailing list, contact oz-users-request@dfki.uni-sb.de. PROFIT: [COST FREE] ProFIT (Prolog with Features Inheritance and Templates) is an extension of Prolog with sorted feature structures (including multi-dimensional inheritance), finite domains, feature search, cyclic terms, and templates. ProFIT works as a pre-processor, which takes a file containing a ProFIT program as input, and gives a file with a Prolog program as output. Sorted feature terms and finite domains are compiled into a Prolog term representation, and the usual Prolog term unification is used at runtime, so that there is no slowdown through a unification algorithm, and no meta-interpreter is needed. ProFIT uses the same techniques for compiling sorted feature terms and finite domains into Prolog terms as the Core Langauge Engine of SRI Cambridge and the Advanced Linguistic Engineering Platform (ALEP 2.2) by the European Community, BIM, and Cray Systems. ProFIT is not a grammar formalism (although it is motivated by NLP), although it provides some ingredients that are considered typical of grammar formalisms. The goal of ProFIT is to provide these datatypes without enforcing any particular theory of grammar, parsing or generation. ProFIT can be used to extend your favourite Prolog-based grammar formalism, parser and generator with the expressive power of sorted feature terms. Cyclic terms can be printed out and a user-configurable pretty-printer for feature terms is provided. ProFIT is available free of charge by anonymous ftp from coli.uni-sb.de:/pub/profit Implemented in Sicstus Prolog (2.1 #9) by Gregor Erbach, Univ. Saarlandes, Saarbruecken, Germany PROLOG III: [COST COMMERCIAL] Prolog III was the first commercial Constraint Logic Programming language. It incorporates all the main features of PROLOG II+, but also gives the user the ability to express constraints over various different domains. In particular the fundamental concept of constraint resolution allows for numerical processing and also a complete treatment of Boolean algebra, in a logic programming style. Version 1.5 of PROLOG III is available on wide range of platforms including PC, MAC, UNIX, ULTRIX, VMS, NeXTSTEP, ALPHA OSF1. For more information, write to PrologIA, Luminy - case 919 - 13288 MARSEILLE cedex 09 - FRANCE or contact Fabienne LELEU : ph (33) 91 26 86 36 fax (33) 91 41 96 37 e-mail prologia@prologianet.univ-mrs.fr PROLOG IV: NON-LINEAR ? [COST COMMERCIAL] Prolog IV is an ISO-compliant replacement for the Prolog III language. It incorporates all the main features of Prolog III with some important changes. Prolog IV allows programmers to express a wide variety of constraints over real and rationnal numbers, integers (finite domains), booleans and lists. In addition to expressing classical linear programming problems on discrete and continuous quantities this permits among other things the adressing of mixed real/integers problems and the use of boolean operations to formalize constraint disjunctions. The algorithms include a non-optimised algorithm for lists (different from Prolog III), Gauss and Simplex algorithms for equations and linear inequalities over rationals, and an interval method for approximate solving of non-linear constraints over reals. The compiler is integrated into a complete graphic programming environnment featuring the following tools: project editor, multi-window text editor, grapher, debugger, and on-line help. Prolog IV is available on Unix Platforms (for about $11400) and PC's with Windows (about $6400). These prices include two days of training. For sales, contact Fabienne LELEU, Case 919 - Luminy 13288 Marseille cedex 09, France. Phone +33 91 26 86 36 - Fax +33 91 41 96 37. Email: prologia@prologianet.univ-mrs.fr For more information, you can contact Andre Touraivane, Prologia Director of Research at the same address, or email touraivane@prologianet.univ-mrs.fr QUAD-CLP(R): NON-LINEAR [COST FREE] QUAD-CLP(R) is an experimental constraint logic programming system developed in the course of PhD research by Gilles Pesant. The CLP(R) version 1.1 source code was used as a platform for the implementation. The system provides a further treatment of non-linear _arithmetic_ constraints over the reals as opposed to delaying them unconditionally. It concentrates on quadratic constraints, rewriting them so that they can actually be decided upon or generating a conservative approximation of them (while still delaying them), potentially improving control over the computation. In both cases the idea is to fall back on linear constraints, more easily handled. QUAD-CLP(R)'s incomplete solver for non-linear constraints caters for problems of respectable size which require a certain amount of reasoning on these constraints but cannot afford the prohibitive cost of a complete treatment. Contact Gilles Pesant ftp://ftp.iro.umontreal.ca/pub/incognito/Logiciels/QUAD_CLP_R/ The file "qclpr_tar.Z" contains the whole package: executable file (for Sparc/SunOS and Sparc/Solaris platforms), some rudimentary pages information and a directory containing examples. Reference: [1] G. Pesant, M. Boyer. QUAD-CLP(R): Adding the Power of Quadratic Constraints. Principles and Practice of Constraint Programming: Proceedings of the Second International Workshop (Rosario, Orcas Island, Washington, USA) (Alan Borning, ed.), Lecture Notes in Computer Science, vol. 874, Springer-Verlag, Rosario, Orcas Island, Washington, USA, 1994, pp. 95--108. QUANTUM LEAP: [COST COMMERCIAL or CHEAP] [See last paragraph] The Quantum Leap Problem Solving Engine (PSE) works like a community of competing and cooperating experts - each one using a different methodology to obtain the best solution to a problem. Users employ the Problem Representation Facility (PRF), an object based, graphical interface, to build statements of their problems. Quantum Leap employs a coordinated team of optimization methods, including: Linear Programming, Quadratic Programming, Generalized Reduced Gradient, Conjugate Direction, Evolutionary Programming, Simulated Annealing, Zoomed Enumeration, Logical Reduction, Pseudo Boltzman, and Heuristic Search. It also offers an object-oriented, tabular, multidimensional representation, with inheritance and self-reference, both numeric and symbolic constructs, an English-like language, internal and external (C) user defined functions, and many built-in aggregates and numeric functions. It has a Client-Server Architecture, with the PSE implemented locally, on another LAN node, or remotely. A multi-PSE version finds faster solutions to many problems via parallel processing. Users can define multiple objectives, and priorities among goals. The system finds "Best Balanced" points for infeasible problems, and multiple solutions to some problems. APIs are available that allow a compiled model to be used as a stand-alone application. Quantum Development wants you to solve your problem, then grant the right to publish your approach! In return, you become a member of the LEAPER program, use Quantum Leap for only shipping and materials cost. Leapers will receive the LEAPER LETTER, a moderated news-list for exchange of technical information. To receive more information, send email to leapers@qdc.com. The body of the note should contain, as the first line: GET . Or contact Joseph Elad (President) jelad@qdc.com or Wenming Kuai wkuai@qdc.com. Phone USA (302) 798-0899, fax (302) 798-6813. RISC-CLP(REAL): NON-LINEAR [unavailable] RISC-CLP(Real) is a logic programming language with constraints over the real numbers and exact arithmetic. The core-solver of the language is the partial Quantifier Elimination Algorithm for real closed fields. This is an improvement of the original quantifier elimination algorithm due to Collins'. RISC-CLP also employs the Groebner Basis algorithm of Buchberger. The system was intended as a study of a CLP solver based on purely algebraic methods, generally too slow for such an application, and is not meant for distribution. The interpreter and the solver are implemented on top of the computer algebra system SACLIB in C language. Contact Hoon Hong (SACLIB and GROEBNER are available at ftp://ftp.risc.uni-linz.ac.at and http://www.risc.uni-linz.ac.at) References: [1] H. Hong. Non-linear real Constrains in Constraint Logic Programming. International Conference on Algebraic and Logic Programming, Springer Lecture Notes in Computer Science 632, 201-212. 1992. [2] H. Hong. RISC-CLP(Real): Constraint Logic Programming over Real Numbers. Constraint Logic Programming: Selected Research. Eds. F. Benhamou and A. Colmerauer. MIT Press. 1993. SCREAMER: [COST FREE] Screamer is an extension of Common Lisp that adds support for nondeterministic programming. Screamer consists of two levels. The basic nondeterministic level adds support for backtracking and undoable side effects. On top of this nondeterministic substrate, Screamer provides a comprehensive constraint programming language in which one can formulate and solve mixed systems of numeric and symbolic constraints. Together, these two levels augment Common Lisp with practically all of the functionality of both Prolog and constraint logic programming languages such as CHiP and CLP(R). Furthermore, Screamer is fully integrated with Common Lisp. Screamer programs can coexist and interoperate with other extensions to Common Lisp such as CLOS, CLIM and Iterate. In several ways Screamer is more efficient than other implementations of backtracking languages. The overhead to support backtracking is only paid for those portions of the program which use the backtracking primitives. Deterministic portions of user programs pass through the Screamer to Common Lisp transformation unchanged. If only small portions of your programs utilize the backtracking primitives, Screamer can produce more efficient code than compilers for languages in which backtracking is more pervasive. Screamer is fairly portable across most Common Lisp implementations. Screamer is available from ftp.ai.mit.edu:/pub/screamer.tar.Z. Contact Jeffrey Mark Siskind for further information. SCREAMER TOOL REPOSITORY [COST FREE] There is a tools repository (ftp site) for user-contributed Screamer code: ftp.cis.upenn.edu:/pub/screamer-tools. The repository is also accessible at http://www.cis.upenn.edu/~screamer-tools/home.html Questions about the repository to screamer-repository@cis.upenn.edu. SEL: [COST FREE] SEL is a declarative set processing language. Its main features are subset and equational program clauses, pattern matching over sets, support for efficient iteration and point-wise/incremental computation over sets, the ability to define transitive closures through circular constraints, meta-programming and simple higher-order programming, and a modest user-interface including tracing. The language seems well-suited to a number of problems in graph theory, program analysis, and discrete mathematics. The SEL compiler is written in Quintus Prolog and the run-time system is written in C. It generates WAM-like code, extended to deal with set-matching, memoization, and the novel control structure of the language. SEL is available by anonymous FTP from ftp.cs.buffalo.edu:/users/bharat/SEL2/. The FTP release comes with a user manual, bibliography of papers (including .dvi files), several sample programs, and source code. For further information, write to Bharat Jayaraman . SEPIA: [COST FREE with ECLIPSE] See ECLIPSE (also see 'ECRC SEPIA'). SICSTUS PROLOG: [COST A=CHEAP,E=??,C=COMMERCIAL] SICStus Prolog is a Unix prolog by SICS. It is portable to most UNIX machines (Berkeley UNIX is preferred over System V). SICS Aurora and Echo is a parallel emulator for Sequent Balance, Sequent Symmetry, Encore Multimax, and BBN Butterfly (Unix). For more information, write to SICS, Swedish Institute of Computer Science, P.O. Box 1263, S-164 28 KISTA, Sweden, call +46 8 752 15 02, fax +46 8 751 72 30, or send email to sicstus-request@sics.se or sicstus@sics.se. Bug reports and tech support questions should be sent to sicstus-bug@sics.se. To subscribe to the users group and implementors mailing list, send email to sicstus-users-request@sics.se. SKYBLUE: [COST FREE-PD] A constraint-solving algorithm. See information on the Seattle ftp site in section [1-5]. See paper by Freeman-Benson et al in section [1-6]. STEELE'S CONSTRAINT SYSTEM: [COST FREE] Chris Hanson's implementation of Steele's constraint system is available by ftp from martigny.ai.mit.edu:/archive/cph/constraint.tar or nexus.yorku.ca:/pub/scheme/new/constraint.tar.Z. A compressed version is also stored there. The software is source code for MIT Scheme. It should run in release 7.1.3. Most of the MIT Scheme dependencies could be eliminated, but it also uses the following procedures which aren't in standard Scheme: error, bkpt, macros, dynamic binding, and string output ports. The code corresponds pretty closely to Guy Steele's PhD thesis implementation, which you can obtain in printed form from the MIT AI Lab publications office as AI-TR-595 for $15.00 (email publications@ai.mit.edu for more information). For more information, send email to Chris Hanson . THINGLABII [COST FREE-PD] ThingLabII is a constraint-based package. See information on the Seattle ftp site in section [1-5]. TOUPIE: [COST FREE] Toupie is a finite domain $\mu$-calculus interpreter designed by A. Rauzy . It uses Decision Diagrams to represent relations and formulas. Decision Diagrams are an extension of the BDD first introduced by Bryant. The original propositional $\mu$-calculus interpreter was designed to express properties of finite states machines. In addition to classical connectives of the propositional calculus, it provides the two quantifications and the possibility to define relations as least or greatest fixpoints of equations. Toupie is a $\mu(\cal FD)$ interpreter, i.e. an extension to finite domains handling numerical linear constraints. This language has been successfuly used for abstract interpretation of Prolog, analysis of mutual exclusion algorithms, classical logic puzzles and model-checking a recent presentation can be found in ESOP'94 "Symbolic Model Checking and Constraint Logic Programming: a Cross- Fertilization". [Information kindly supplied by Marc-Michel Corsini .] TRILOGY: [COST CHEAP] Trilogy is a constraint system developed by Complete Logic Systems. It costs $100. For more information, write to Complete Logic Systems, Inc, 741 Blueridge Avenue, V7R 2J5, North Vancouver BC, Canada, or call 604-986-3234. [Does the company still exist?] VS TRILOGY: [COST COMMERCIAL] VS Trilogy is a Prolog compiler available from Vertical Software for $395. For more information, write to Vertical Software Ltd., 14-636 Clyde Ave, W. Vancouver, BC, V7T 1E1, Canada, call 604-925-0321, or fax 604-688-8479. WAMCC: [COST FREE] WAMCC 2.2 is a WAM-based Prolog to C compiler. It conforms more or less to the Edinburgh standard, and includes most of the usual built-in predicates, a top-level, a Prolog debugger and a WAM debugger. It is designed to be easily extended (for example see clp(FD)). WAMCC's speed is halfway between SICStus emulated and SICStus native code on a Sparc (1.5 times faster and 1.5 times slower, respectively). It requires GCC 2.4.5 or higher and has been tested on Sparc workstations. It should be easily ported to 32-bit machines with GCC. WAMCC is available free by anonymous ftp from ftp.inria.fr:/INRIA/Projects/ChLoE/LOGIC_PROGRAMMING/wamcc/ For more information, write to Daniel Diaz , INRIA Rocquencourt, FRANCE. ---------------------------------------------------------------- ;;; *EOF* .