Search the FAQ Archives

3 - A - B - C - D - E - F - G - H - I - J - K - L - M
N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Internet FAQ Archives

comp.constraints FAQ (Part 1 of 1)

( Part1 - Part2 - MultiPage )
[ Usenet FAQs | Web FAQs | Documents | RFC Index | Restaurant inspections ]
Archive-name: constraints-faq/part1
Summary: Frequently asked questions about constraints
Posting-Frequency: monthly
Version: 1999.11.23

See reader questions & answers on this topic! - Help others by sharing your knowledge
Contributions and corrections should be sent to:

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 Constraints Archive web pages contain far more information
than the FAQ, including pointers to other web pages and ftp sites:

This guide is regularly posted to comp.constraints.  It may also be
obtained from the WWW pages, and from the archive on in
the directory /pub/usenet/news.answers/constraints-faq.  You can 
access the rtfm archive by mail server as well.  Send an e-mail 
essage to with "help" and "index" in the
body on separate lines for more information.

This FAQ is Copyright Peggy Eaton, 1996, 1997, 1998, 1999.  

Contributors to this FAQ include Michael Jampel <>,
who was the original author and maintainer, and: Philippe Blache
<>, Mark Kantrowitz <>, Wm Leler
<>, Manfred Meyer <>, Milind
Tambe <>, Thomas Schiex <>, and Tad Hogg
<>, David Joslin <>.  

Table of Contents:
   [1-01] Introductory materials
   [1-02] Other related FAQs
   [1-03] Acronyms
   [1-04] Publications
   [1-05] Bibliographies
   [1-06] Journals
   [1-07] Mailing lists
   [1-08] Newsgroups
   [1-09] Benchmarks and examples
   [1-10] Constraint libraries for Lisp and C
   [1-11] 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-01] Introductory materials Roman Bartak has an On-line Guide to Constraint Programming <> V. Kumar, "Algorithms for Constraint-Satisfaction Problems: A Survey," AI Magazine 13(1):32-44, 1992. (A postscript version <> is available. It differs slightly from the published version.) David McAllester's lecture notes on constraint satisfaction search <> [postscript]. Constraint Logic Programming <> by Dick Pountain. Reproduced with permission from BYTE <> magazine, February 1995; converted to html by Michael Jampel. (BYTE has now put their version <> of the article on the web.) E. Tsang <>, "Foundations of Constraint Satisfaction", Academic Press, 1993. ISBN 0-12-701610-4. (Out of print, but available from the author <>.) Also see the articles on Constraint Networks (pages 276-285) and Constraint Satisfaction (pages 285-293) in Shapiro's Encyclopedia of Artificial Intelligence.
Subject: [1-02] Other related FAQs Many FAQs are posted to the news.answers newsgroup, and, if appropriate, to comp.answers and other groups. These FAQs are archived at <>. For example, the comp.constraints FAQs are in the <> directory. These FAQs are also automatically converted to HTML (in most cases, this just means that URLs are converted to hot links), and archived in various places such as the News.Answers Faqs Archive <> at Utrecht; for example, the comp.constraints FAQ <>, converted to HTML format, can be found there. You can also search the collection of FAQs. Also see Smartpages <> and the Ohio State archives <> maintained by Tom Fine, Infoseek <> (one of the search options is "Usenet FAQs"), and Kent Landfield's archive <>. Here are the FAQs for <>, for AI in general <>, for AI programming languages <> and for comp.lang.prolog <> (with some information on CLP). The sci.op-research newsgroup has FAQs for linear and non-linear programming <> These can be found in ascii format, along with an index of resources for numerical computation in C or C++ (including some for linear and non-linear programming), in <>.
Subject: [1-3] Acronyms This section explains what various acronyms stand for, without much detail on any of them. You can also use the search facility <> of the constraints archive to find web pages on which a term occurs. (*) Denotes techniques/heuristics for improving the efficiency of constraint satisfaction 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) ATMS -- Assumption-Based Truth-Maintenance System BJ -- Backjumping (*) BM -- Backmarking (*) BMJ -- Backmarking with backjumping (*) CBJ -- Conflict-Directed Back-Jumping (*) CC(FD) -- Concurrent Constraint Programming over Finite Domains CCP -- Concurrent Constraint Programming CDI -- Context Dependent Interchangeability CHR -- Constraint Handling Rules (Fruehwirth) CIP -- Constraint Imperative 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 CLP -- Constraint Logic Programming CNG -- Complete No-Good COP -- Constrained Optimization Problem CSP -- Constraint Satisfaction Problem DB -- Dynamic Backtracking (*) DBT -- Dynamic backtracking DCSP -- Dynamic CSP DVO -- Dynamic Variable Ordering heuristic (*) DnAC -- Dynamic arc-consistency FC -- Forward-checking (*) FF -- First Fail principle: choose the variable with the smallest domain as the next instantiation (*) FI -- full interchangeability FLA -- Full Look Ahead FOF -- Factor Out Failure FSL -- Full Shallow learning (*) GBJ -- Graph based Backjumping (*) 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 MNG -- Minimal No-Good NC -- Node consistency (see AC). Not much used NG -- No-Good NI -- neighborhood interchangeability NLP -- Non-Linear Programming. (Natural Language Processing elsewhere) NPI -- neighborhood partial interchangeability NR -- Nogood recording (*) NSUB -- Neighborhood Substitutability OR -- Operations Research. see newsgroup sci.op-research PC -- Path-Consistency. Not much used PCSP -- Partial CSP PI -- partial interchangeability PLA -- Partial Look Ahead RFLA -- Real Full Look Ahead SAT -- The problem of deciding if a given logical formula is SATisfiable. SUB -- Substitutability TMS -- Truth-Maintenance System TSP -- Travelling Salesman Problem; a typical very hard problem VAD -- value assignment delay (*) (Thanks to Michael Jampel, Patrick Prosser, Thomas Schiex, Berthe Choueiry, Alan Borning, Warwick Harvey, Thom Fruehwirth. Please inform me of additions.)
Subject: [1-4] Publications This page contains pointers to various constraints-related books, articles, reviews, etc., as well as pointers to sites that have collections of constraint-related publications. Books and articles ================================================================ Objects for Concurrent Constraint Programming <> by Martin Henz, National University of Singapore, Kluwer Academic Publishers. CHIC Lessons on CLP Methodolgy (html <>, postscript <>) -- a paper by Andre Chamard, Annie Fischler, Dominique-Benoit Guinaudeau and Andre Guillard Computational Phonology: A Constraint-Based Approach <> a book by Steven Bird, Edinburgh. Constraint Programming: Basics and Trends <> edited by Andreas Podelski (Chatillon-sur-Seine Spring School, France, May 1994). CHIP hints <> (Scott Fleishman <>, Aberdeen). Logic Programming: Formal Methods and Practical Applications <> edited by C. Beierle and L. Pluemer, published by Elsevier. Abstract <> of "A Theoretical Evaluation of Selected Backtracking Algorithms" by Grzegorz Kondrak, University of Alberta. Over-Constrained Systems <> edited by Michael Jampel, Eugene Freuder, and Michael Maher. Springer LNCS 1106, August 1996. Contains selected papers from the Workshop on Over-Constrained Systems at CP'95, and also reprints and background papers. Phase Transition Behaviour of Maintaining Arc Consistency <> by Stuart Grant and Barbara Smith (Leeds) Constraint Programming <> by Mark Wallace Practical Applications of Constraint Programming < ps> by Mark Wallace Engineering of Optimisation Projects <> by the CHIC-2 Consortium Reviews and surveys ================================================================ Overview of CSP tools <> including CHIP, CHARME, and ILOG SOLVER by Tim Duncan <>. CLP with Non-Linear Constraints <>, a survey by Olga Caprotti <>. (This information is also in the comp.constraints FAQ, but in a slightly different form.) Review <> by Michael Jampel of A Review of Industrial Constraint Solving Tools by Jean-Yves Cras Sites with publications on constraints ================================================================ CCL project <> Construction of Computational Logics (located at DFKI) -- also CCL Bibliographies <> CHIC project <> Constraint Handling in Industry and Commerce (located at ECRC) CHIC-2 project (Creating Hybrid Solutions for Industry and Commerce) 1996-99 <> Computer Aided Design < uff.html> Constraint-driven synthesis and analysis of analog and mixed-signal integrated circuits (Berkeley). Constraint Logic Programming ftp archive <> (run by Brian Mayoh) Constraints <> Journal, edited by Eugene Freuder <>. CMU AI Repository <> DFKI Programming Systems Lab <> and DFKI Constraints Research <> ECRC ftp archive <> Essex University ftp archive <> (CSPs, partial constraints, constraints related to neural nets etc. Edward Tsang) IC-Parc, Imperial College Centre for Planning and Resource Control (publications and ECLiPSe system) The ILOG Solver and Schedule <> web pages include relevant papers Imperial College Logic Programming Section <> publications ftp site JAIR <> (Journal of AI Research home page) LIA <> papers and reports (Lausanne) Logic Programming <> (Jonathan Bowen, Oxford University) NASA Ames Research Center <> various papers Ohio State CLP tech reports <> (Spiro Michaylov) Overview of CSP tools <> (Tim Duncan) Phase Transition <> in CSPs (Tad Hogg) Phase Transition Behaviour of Maintaining Arc Consistency <> by Stuart Grant and Barbara Smith SICS ISL <> Intelligent Systems Laboratory at SICS Toronto OR <>: papers from the Laboratory of Manufacturing Research University of Washington ftp archive <> (Alan Borning etc.) --- also WWW <> Xerox PARC ftp archive <>
Subject: [1-5] Bibliographies Short bibliography <> covering some key CLP and CSP papers and books. Suggestions for updating the list are requested; email <>. CLP bibliography <> by Spiro Michaylov <> (somewhat out of date; no entries after 1993). An updated CLP bibliography is maintained by Peggy Eaton <>. (URL TO BE ADDED) Abstract Interpretation Bibliography <> (Marc-Michel Corsini) CCL Bibliographies <> (Constraints in Computational Logic project) Combinations of Constraint Solving Techniques <> Constraint Programming Paper Archive: Aarhus University, Denmark, has established an anonymous ftp archive for papers on "Constraint Programming" at <> For further information, contact Brian H. Mayoh <>. ECRC tech reports are available at <> or <> Fuzzy Scheduling bibliography <> (Wolfgang Slany <>) Glimpse server <> for general computing bibliographic searches Logic Programming bibliographies <> (Ralf Scheidhauer <>) -- can be searched <> Logic Programming Conferences <> -- excellent WWW bibliographies (Michael Ley) --- also a page of more general bibliographies <>, including databases Theory journal <> bibliographies, organised by David Jones <>. Includes: FOCS: IEEE Symposium on Foundations of Computer Science <>, Information and Computation <>, Journal of the ACM <>, LICS: IEEE Symposium on Logic in Computer Science <>, STOC: ACM Symposium on Theory of Computing <>.
Subject: [1-6] Journals CONSTRAINTS is a new journal published by Kluwer. The Editor-in-Chief is Eugene C. Freuder <>. See <>. CONSTRAINTS will be available both as a conventional paper journal and in electronic form. The Instructions for Authors can be obtained from Kelly Riddle <>. The AI Journal <> publishes constraint-related articles. (Note the new electronic services available to users affiliated to institutes with a full subscription to the paper journal. Abstracts and some papers are available on-line, and can be searched.) The Journal of Artificial Intelligence Research (JAIR) <> is published both electronically and in hard copy. Articles are announced in and published in and on the web page. AI Communications (4 issues/yr) "The European Journal on Artificial Intelligence" ISSN 0921-7126, European Coordinating Committee for Artificial Intelligence. The Journal of Logic Programming (issued bimonthly), Elsevier Publishing Company, ISSN 0743-1066. (CLP-related articles.) New Generation Computing Springer-Verlag. (Prolog-related articles) 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 <> or <> for details. Other links ================================================================ See the journal list < blications.html> at the CMU AI Repository <>.
Subject: [1-7] Mailing lists CCL II mailing list This is the mailing list of the Esprit (European Union) project CCL II "Construction on Computational Logics" which focuses in particular on symbolic constraints. To subscribe, send mail to <>. The project's home page is <> where you can find an archive of the mailing list. Constraint Logic Programming Announcements and articles to <>. Requests to subscribe/unsubscribe to <>. Maintained by Roland Yap <>. CLP(R) Users Announcements and articles to <>. Requests to subscribe/unsubscribe to <>. Maintained by Roland Yap <>. Constraint Satisfaction Problems (CSP) To subscribe, send e-mail to <> in the form "SUB CSP-LIST <name>". Send submissions to <>. List maintained by Thomas Schiex <>. 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 <IDSS@socs.uts.EDU.AU>. Subscription requests should be sent to <idss-request@socs.uts.EDU.AU>. The SCHED-L Mailing list Knowledge-based scheduling. Discussion of scheduling techniques and manufacturing processes. Send "subscribe sched-l {your full name}" in the body of a message to <>. Maintained by Wolfgang Slany <>. Archives are available for the SCHED-L <>.
Subject: [1-8] Newsgroups comp.constraints,, and other AI newsgroups are archived at: <>. comp.lang.prolog is archived at: < og/0.html> Other relevant groups might include sci.op-research and comp.theory
Subject: [1-9] Benchmarks and examples ACC basketball scheduling problem <a href="">, an AMPL model and 0-1 IP instances of the original problem (presented by Nemhauser and Trick), J.P. Walser (University of Saarbruecken) Secretary's Nightmare scheduling problem CAIA-94 <>, the workshop on Coordinated Design and Planning, March 1994, introduced the "secretary's nightmare" scheduling problem. CSP Lab (in Lisp) <> created by Patrick Prosser. There is also a Scheme version <>. Algorithms include bt, bm, bj, cbj, fc, fc-cbj, and mac. CSPLib v2.0: a benchmark library for constraints compiled by Toby Walsh, Ian Gent, and Bart Selman. <> <> ECLiPSe Code Samples <> The Munich Rent Advisor <> was written using the CHR library of Eclipse <>, by Thom Fruehwirth <>. The Mystery Shopper benchmark < mark.txt> was developed by Jimmy Ho Man Lee <> and introduced at CP'96. Neng-Fa Zhou <> has developed a multi-layer channel router in CLP(FD), and hopes that the program can be used as a good benchmark for evaluating CLP(FD) systems. The program, and a number ofq other CLP benchmarks, are available from <>. OR-Library <> of test data sets (Imperial College, J.E. Beasley) Planning and Scheduling <> Benchmarks (Barry Fox, Mark Ringer) Radio Link Frequency Assignment Problem can be found at the TU-Delft RLFAP archive <> and on this site at <> Scheduling Benchmarks and Resources <> (A paper by Mark Drummond, NASA Ames Research Center; also a postscript <> version) Traffic Lights <> example by Walter Hower <> TSP <> Travelling Salesman Problems library, maintained by Gerhard Reinelt ( Zebra Puzzle <> -- in Eclipse using CLP(Finite Domains)
Subject: [1-10] Constraint libraries for Lisp and C 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 <>. Peter Van Beek <> has written a set of libraries for C. This package is available from <> where you will find a README and also csplib.tar.Z. Screamer <> is a constraint library for Common Lisp. Michel Lemaitre has written a Common Lisp library dedicated to the resolution of "Valued Constraint Satisfaction Problems" (for a description of VCSP, see <>). The library has been designed with efficiency in mind. It includes Branch and Bound extensions of the Backtrack and Forward checking algorithm as well as the "Russian Doll Search" algorithm described in <>, and several benchmark problems. The library is available at <>.
Subject: [1-11] Constraint systems The constraints archive web page on constraint systems <> has entries for the following systems: ALE Amulet and Garnet B-Prolog Bertrand CHIP CIAL CLAIRE CLP(BNR), CLP(F), CLP(FD), CLP(R), etc. CPLEX Contax Cooldraw, Deltablue, Skyblue, ThinglabII DiSCiPl ECLiPSe Echidna Euclid FSQP/CFSQP GNU-Prolog Goedel IF/Prolog ILOG Schedule, ILOG Solver LIFE Newton Nicolog Omega Oz ProFIT Prolog III, Prolog IV QUAD-CLP(R) Quantum Leap RISC-CLP(Real) SEL SICStus Screamer Steele TOY Toupie Trilogy cu-Prolog opbdp The constraints archive search page <> also has an option for searching just the descriptions of systems. See the comp.lang.prolog, comp.lang.lisp, and comp.lang.scheme FAQs and Resource Guides for possibly more up-to-date and complete information. Also see: Overview of CSP tools <> (Tim Duncan) PTF: The Prime Time Freeware CD-ROM series contains various items mentioned here 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. ----------------------------------------------------------------

User Contributions:

Comment about this article, ask questions, or add new information about this topic:

Part1 - Part2 - MultiPage

[ Usenet FAQs | Web FAQs | Documents | RFC Index ]

Send corrections/additions to the FAQ Maintainer:

Last Update March 27 2014 @ 02:11 PM