|
Archive-name: constraints-faq/part1
Summary: Frequently asked questions about constraints
Posting-Frequency: monthly
URL: http://www.cs.unh.edu/ccc/archive/
Version: 1999.11.23
Contributions and corrections should be sent to:
<pse@cs.unh.edu>
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:
http://www.cs.unh.edu/ccc/archive/
This guide is regularly posted to comp.constraints. It may also be
obtained from the WWW pages, and from the archive on rtfm.mit.edu 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 mail-server@rtfm.mit.edu 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 <jampel@cs.city.ac.uk>,
who was the original author and maintainer, and: Philippe Blache
<pb@llaor.unice.fr>, Mark Kantrowitz <mkant@cs.cmu.edu>, Wm Leler
<wm@concentric.net>, Manfred Meyer <meyer@dfki.uni-kl.de>, Milind
Tambe <tambe@isi.edu>, Thomas Schiex <schiex@cert.fr>, and Tad Hogg
<hogg@parc.xerox.com>, David Joslin <dj@i2.com>.
----------------------------------------------------------------
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
<http://kti.ms.mff.cuni.cz/~bartak/constraints/>
V. Kumar, "Algorithms for Constraint-Satisfaction Problems: A Survey,"
AI Magazine 13(1):32-44, 1992. (A postscript version
<http://www.cs.unh.edu/ccc/archive/constraints/archive/kumar.ps> is
available. It differs slightly from the published version.)
David McAllester's lecture notes on constraint satisfaction search
<http://www.cs.unh.edu/ccc/archive/constraints/archive/dmac.ps>
[postscript].
Constraint Logic Programming
<http://www.cs.unh.edu/ccc/archive/constraints/archive/byte.html> by Dick
Pountain.
Reproduced with permission from BYTE <http://www.byte.com/> magazine,
February 1995; converted to html by Michael Jampel. (BYTE has now put
their version <http://www.byte.com/art/9502/sec13/art3.htm>
of the article on the web.)
E. Tsang <edward@essex.ac.uk>, "Foundations of Constraint
Satisfaction", Academic Press, 1993. ISBN 0-12-701610-4.
(Out of print, but available from the author
<http://cswww.essex.ac.uk/CSP/edward/FCS.html>.)
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 <ftp://rtfm.mit.edu/pub/usenet/>. For example, the comp.constraints
FAQs are in the <ftp://rtfm.mit.edu/pub/usenet/comp.constraints/>
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
<http://www.cs.ruu.nl/cgi-bin/faqwais> at Utrecht; for example, the
comp.constraints FAQ
<http://www.cs.ruu.nl/wais/html/na-bng/comp.constraints.html>,
converted to HTML format, can be found there. You can also search the
collection of FAQs. Also see Smartpages
<http://www.smartpages.com/bngfaqs/top.html> and the Ohio State
archives
<http://www.cis.ohio-state.edu/hypertext/faq/usenet/FAQ-List.html>
maintained by Tom Fine, Infoseek <http://guide.infoseek.com/> (one of
the search options is "Usenet FAQs"), and Kent Landfield's archive
<http://www.landfield.com/faqs/>.
Here are the FAQs for comp.ai
<http://www.cs.cmu.edu/Web/Groups/AI/html/faqs/ai/ai_general/top.html>,
for AI in general
<http://www.cs.cmu.edu/Web/Groups/AI/html/faqs/ai/top.html>, for AI
programming languages
<http://www.cs.cmu.edu/Web/Groups/AI/html/faqs/lang/top.html> and for
comp.lang.prolog
<http://www.cs.cmu.edu/Web/Groups/AI/html/faqs/lang/prolog/top.html>
(with some information on CLP).
The sci.op-research newsgroup has FAQs for linear and non-linear
programming <http://www.mcs.anl.gov/home/otc/Guide/faq/> 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 <ftp://rtfm.mit.edu/pub/usenet/sci.op-research/>.
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
<http://www.cs.unh.edu/ccc/archive/constraints/search.html> 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
<http://www.wkap.nl/book.htm/0-7923-8038-X> by Martin Henz, National
University of Singapore, Kluwer Academic Publishers.
CHIC Lessons on CLP Methodolgy (html
<http://www.ecrc.de/eclipse/html/CHIC_Methodology.html>, postscript
<ftp://ftp.ecrc.de/pub/chic/>) -- a paper by Andre
Chamard, Annie Fischler, Dominique-Benoit Guinaudeau and Andre Guillard
Computational Phonology: A Constraint-Based Approach
<http://www.cogsci.ed.ac.uk/~steven/book.html> a book by Steven Bird,
Edinburgh.
Constraint Programming: Basics and Trends
<http://www.cs.unh.edu/ccc/archive/constraints/archive/podelski.html> edited
by Andreas Podelski (Chatillon-sur-Seine Spring School, France, May
1994).
CHIP hints <http://www.biochem.abdn.ac.uk/~scott/chip.html> (Scott
Fleishman <http://www.biochem.abdn.ac.uk/~scott/scott.html>,
Aberdeen).
Logic Programming: Formal Methods and Practical Applications
<http://voss.fernuni-hagen.de/gebiete/pi8/lit/lp95book.html> edited by
C. Beierle and L. Pluemer, published by Elsevier.
Abstract <http://www.cs.unh.edu/ccc/archive/constraints/archive/kondrak.html>
of "A Theoretical Evaluation of Selected Backtracking Algorithms" by
Grzegorz Kondrak, University of Alberta.
Over-Constrained Systems
<http://www.cs.unh.edu/ccc/archive/constraints/archive/ocs-book.html> 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
<ftp://agora.leeds.ac.uk/scs/doc/reports/1995/> by Stuart
Grant and Barbara Smith (Leeds)
Constraint Programming
<http://www.icparc.ic.ac.uk/papers/handbook.ps>
by Mark Wallace
Practical Applications of Constraint Programming
<http://www.icparc.ic.ac.uk/papers/practical_applications_of_constraint_pro.
ps>
by Mark Wallace
Engineering of Optimisation Projects
<http://www.icparc.ic.ac.uk/chic2/chic2_methodology/>
by the CHIC-2 Consortium
Reviews and surveys
================================================================
Overview of CSP tools
<http://www.aiai.ed.ac.uk/~timd/constraints/csptools/> including CHIP,
CHARME, and ILOG SOLVER by Tim Duncan
<http://www.aiai.ed.ac.uk/~timd/timd.html>.
CLP with Non-Linear Constraints
<http://www.risc.uni-linz.ac.at/people/ocaprott/survey.html>, a survey
by Olga Caprotti
<http://info.risc.uni-linz.ac.at:70/1/people/ocaprott>. (This
information is also in the comp.constraints FAQ, but in a slightly
different form.)
Review <http://www.cs.unh.edu/ccc/archive/constraints/archive/cras.html> by
Michael Jampel of A Review of Industrial Constraint Solving Tools by
Jean-Yves Cras
Sites with publications on constraints
================================================================
CCL project <http://ps-www.dfki.uni-sb.de/ccl> Construction of
Computational Logics (located at DFKI) -- also CCL Bibliographies
<http://ps-www.dfki.uni-sb.de/ccl/publications/index.html>
CHIC project <http://www.ecrc.de/CHIC/> Constraint Handling in Industry
and Commerce (located at ECRC)
CHIC-2 project (Creating Hybrid Solutions for Industry and Commerce)
1996-99 <http://www.icparc.ic.ac.uk/chic2/>
Computer Aided Design
<http://www-cad.eecs.berkeley.edu/Respep/Research/analog-cad/analog-group-st
uff.html>
Constraint-driven synthesis and analysis of analog and mixed-signal
integrated circuits (Berkeley).
Constraint Logic Programming ftp archive
<ftp://ftp.daimi.aau.dk/pub/CLP/index.html> (run by Brian Mayoh)
Constraints <http://www.cs.unh.edu/constraints> Journal, edited by
Eugene Freuder <http://www.cs.unh.edu:70/0h/faculty/freuder.html>.
CMU AI Repository
<http://www.cs.cmu.edu/Web/Groups/AI/html/repository.html>
DFKI Programming Systems Lab <http://ps-www.dfki.uni-sb.de> and DFKI
Constraints Research
<http://www.dfki.uni-kl.de/~hmeyer/constraints/constraints.html>
ECRC ftp archive <ftp://ftp.ecrc.de/pub/>
Essex University ftp archive <ftp://solb1.essex.ac.uk/pub/csp/> (CSPs,
partial constraints, constraints related to neural nets etc. Edward
Tsang)
IC-Parc, Imperial College Centre for Planning and Resource Control
http://www.icparc.ic.ac.uk (publications and ECLiPSe system)
The ILOG Solver and Schedule
<http://www.ilog.com/html/product_optimization_suite.html> web pages
include relevant papers
Imperial College Logic Programming Section
<http://www-lp.doc.ic.ac.uk:80/_lp/> publications ftp site
JAIR <http://www.cs.washington.edu/research/jair/home.html> (Journal of
AI Research home page)
LIA <ftp://liasun3.epfl.ch/> papers and reports (Lausanne)
Logic Programming <http://www.comlab.ox.ac.uk/archive/logic-prog.html>
(Jonathan Bowen, Oxford University)
NASA Ames Research Center
<http://fi-www.arc.nasa.gov/fia/projects/xfr/papers/> various papers
Ohio State CLP tech reports
<http://www.cis.ohio-state.edu/~spiro/clp.html> (Spiro Michaylov)
Overview of CSP tools
<http://www.aiai.ed.ac.uk/~timd/constraints/csptools/> (Tim Duncan)
Phase Transition
<ftp://parcftp.xerox.com/pub/dynamics/constraints.html> in CSPs (Tad
Hogg)
Phase Transition Behaviour of Maintaining Arc Consistency
<ftp://agora.leeds.ac.uk/scs/doc/reports/1995/> by Stuart
Grant and Barbara Smith
SICS ISL <http://www.sics.se/isl/> Intelligent Systems Laboratory at
SICS
Toronto OR <ftp://fmgmt.mgmt.utoronto.ca>: papers from the Laboratory
of Manufacturing Research
University of Washington ftp archive
<ftp://ftp.cs.washington.edu/pub/constraints> (Alan Borning etc.) ---
also WWW <http://www.cs.washington.edu/research/constraints>
Xerox PARC ftp archive <ftp://parcftp.xerox.com/pub/ccp>
Subject: [1-5] Bibliographies
Short bibliography
<http://www.cs.unh.edu/ccc/archive/constraints/archive/shortbib> covering
some key CLP and CSP papers and books. Suggestions for updating the
list are requested; email <pse@cs.unh.edu>.
CLP bibliography <ftp://archive.cis.ohio-state.edu/pub/clp> by Spiro
Michaylov <spiro@cis.ohio-state.edu> (somewhat out of date; no entries
after 1993).
An updated CLP bibliography is maintained by Peggy Eaton
<mailto:pse@cs.unh.edu>. (URL TO BE ADDED)
Abstract Interpretation Bibliography
<http://www.labri.u-bordeaux.fr/~corsini/Public/Reports/abint-biblio.ps>
(Marc-Michel Corsini)
CCL Bibliographies
<http://ps-www.dfki.uni-sb.de/ccl/publications/index.html> (Constraints
in Computational Logic project)
Combinations of Constraint Solving Techniques
<http://acsl.cs.uiuc.edu/~tinelli/papers/comb-papers.html>
Constraint Programming Paper Archive: Aarhus University, Denmark, has
established an anonymous ftp archive for papers on "Constraint
Programming" at <ftp://ftp.daimi.aau.dk//pub/CLP/> For further
information, contact Brian H. Mayoh <brian@daimi.aau.dk>.
ECRC tech reports are available at <ftp://ftp.ecrc.de> or
<http://www.ecrc.de/>
Fuzzy Scheduling bibliography <ftp://mira.dbai.tuwien.ac.at/pub/slany/>
(Wolfgang Slany <http://www.dbai.tuwien.ac.at/staff/slany.html>)
Glimpse server <http://donkey.cs.arizona.edu:1994/bib> for general
computing bibliographic searches
Logic Programming bibliographies
<http://ps-www.dfki.uni-sb.de/lp-proceedings> (Ralf Scheidhauer
<http://ps-www.dfki.uni-sb.de/~scheidhr>) -- can be searched
<http://ps-www.dfki.uni-sb.de/lp-proceedings/bibtex/ghindex.html>
Logic Programming Conferences
<http://www.informatik.uni-trier.de/~ley/db/conf/index.l.html> --
excellent WWW bibliographies (Michael Ley) --- also a page of more
general bibliographies
<http://www.informatik.uni-trier.de/~ley/db/conf/index.html>, including
databases
Theory journal <http://theory.lcs.mit.edu/~dmjones/hbp/>
bibliographies, organised by David Jones
<http://theory.lcs.mit.edu/~dmjones/>. Includes: FOCS: IEEE Symposium
on Foundations of Computer Science
<http://theory.lcs.mit.edu/~dmjones/FOCS/homepage.html>, Information
and Computation <http://theory.lcs.mit.edu/~iandc/>, Journal of the ACM
<http://theory.lcs.mit.edu/~jacm/>, LICS: IEEE Symposium on Logic in
Computer Science <http://theory.lcs.mit.edu/~dmjones/LICS/>, STOC: ACM
Symposium on Theory of Computing
<http://theory.lcs.mit.edu/~dmjones/STOC/homepage.html>.
Subject: [1-6] Journals
CONSTRAINTS is a new journal published by Kluwer. The Editor-in-Chief
is Eugene C. Freuder <ecf@cs.unh.edu>. See
<http://www.cs.unh.edu/constraints/>. CONSTRAINTS will be available
both as a conventional paper journal and in electronic form. The
Instructions for Authors can be obtained from Kelly Riddle
<krkluwer@world.std.com>.
The AI Journal <http://www.elsevier.nl/locate/artint> 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)
<http://www.cs.washington.edu/research/jair/home.html> is published
both electronically and in hard copy. Articles are announced in
comp.ai.jair.announce and published in comp.ai.jair.papers 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 <http://mitpress.mit.edu/jrnls-catalog/jflp.html> or
<http://www.cs.tu-berlin.de/~chak/jflp/> for details.
Other links
================================================================
See the journal list
<http://www.cs.cmu.edu/afs/cs.cmu.edu/project/ai-repository/ai/html/other/pu
blications.html>
at the CMU AI Repository
<http://www.cs.cmu.edu/afs/cs.cmu.edu/project/ai-repository/ai/html/air.html>.
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 <ccl-request@dfki.uni-sb.de>. The project's home page is
<http://www.ps.uni-sb.de/ccl/> where you can find an archive of the
mailing list.
Constraint Logic Programming Announcements and articles to
<clp@iscs.nus.sg>. Requests to subscribe/unsubscribe to
<clp-request@iscs.nus.sg>. Maintained by Roland Yap
<ryap@iscs.nus.sg>.
CLP(R) Users Announcements and articles to <clpr-users@iscs.nus.sg>.
Requests to subscribe/unsubscribe to <clpr-users-request@iscs.nus.sg>.
Maintained by Roland Yap <ryap@iscs.nus.sg>.
Constraint Satisfaction Problems (CSP) To subscribe, send e-mail to
<listserver@saturne.cert.fr> in the form "SUB CSP-LIST <name>". Send
submissions to <csp-list@saturne.cert.fr>. List maintained by Thomas
Schiex <schiex@cert.fr>.
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
listserver@vexpert.dbai.tuwien.ac.at <>. Maintained by Wolfgang Slany
<wsi@vexpert.dbai.tuwien.ac.at>. Archives are available for the
SCHED-L <http://www.dbai.tuwien.ac.at/marchives/sched-l/index.html>.
Subject: [1-8] Newsgroups
comp.constraints, comp.ai, and other AI newsgroups are archived at:
<http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/pubs/news/0.html>.
comp.lang.prolog is archived at:
<http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/prolog/news/prol
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="http://www.ps.uni-sb.de/~walser/acc/acc.html">, 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 <http://cdr.stanford.edu/html/people/petrie/caia.html>, the
workshop on Coordinated Design and Planning, March 1994, introduced the
"secretary's nightmare" scheduling problem.
CSP Lab (in Lisp) <ftp://ftp.cs.strath.ac.uk/local/pat/csp-lab> created
by Patrick Prosser. There is also a Scheme version
<ftp://ftp.cs.strath.ac.uk/local/pat/csp-lab.scm>. 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. <http://csplib.cs.strath.ac.uk>
<email:csplib@cs.strath.ac.uk>
ECLiPSe Code Samples
<http://www.icparc.ic.ac.uk/eclipse/examples/>
The Munich Rent Advisor
<http://www.pst.informatik.uni-muenchen.de/~fruehwir/miet-demo.html>
was written using the CHR library of Eclipse
<http://www.ecrc.de/eclipse/eclipse.html>, by Thom Fruehwirth
<http://www.pst.informatik.uni-muenchen.de/~fruehwir/>.
The Mystery Shopper benchmark
<http://www.cs.unh.edu/ccc/archive/constraints/archive/mystery-shopper-bench
mark.txt>
was developed by Jimmy Ho Man Lee <jlee@cs.cuhk.hk> and introduced at
CP'96.
Neng-Fa Zhou <zhou@mse.kyutech.ac.jp> 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
<ftp://ftp.kyutech.ac.jp/pub/Language/prolog/>.
OR-Library <http://mscmga.ms.ic.ac.uk/info.html> of test data sets
(Imperial College, J.E. Beasley)
Planning and Scheduling <http://www.NeoSoft.com/~benchmrx/> Benchmarks
(Barry Fox, Mark Ringer)
Radio Link Frequency Assignment Problem can be found
at the TU-Delft RLFAP archive <http://dutiosd.twi.tudelft.nl/~rlfap/>
and on this site at
<ftp://ftp.cs.unh.edu/pub/csp/archive/code/benchmarks/FullRLFAP/>
Scheduling Benchmarks and Resources
<http://fi-www.arc.nasa.gov/fia/projects/xfr/papers/benchmark-article.html>
(A paper by Mark Drummond, NASA Ames Research Center; also a postscript
<http://fi-www.arc.nasa.gov/fia/projects/xfr/papers/med-sigman.ps>
version)
Traffic Lights
<http://www.cs.unh.edu/ccc/archive/constraints/archive/traffic.html> example
by Walter Hower <http://yeats.ucc.ie/~walter/>
TSP
<http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html>
Travelling Salesman Problems library, maintained by Gerhard Reinelt
(Gerhard.Reinelt@IWR.Uni-Heidelberg.de)
Zebra Puzzle <http://www.ecrc.de/eclipse/html/extroot/node59.html> --
in Eclipse using CLP(Finite Domains)
Subject: [1-10] Constraint libraries for Lisp and C
Patrick Prosser <pat@cs.strath.ac.uk> 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 <vanbeek@cs.ualberta.ca> 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.
Screamer
<http://www.cs.unh.edu/ccc/archive/constraints/systems/screamer.html> 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
<ftp://ftp.cert.fr/pub/verfaillie/ijcai95.ps>). 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
<ftp://ftp.cert.fr/pub/verfaillie/rds-aaai96.ps>, and several benchmark
problems. The library is available at
<ftp://ftp.cert.fr/pub/lemaitre/LVCSP/>.
Subject: [1-11] Constraint systems
The constraints archive web page on constraint systems
<http://www.cs.unh.edu/ccc/archive/constraints/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
<http://www.cs.unh.edu/ccc/archive/constraints/search.html> also has an
option for searching just the descriptions of 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.
Also see:
Overview of CSP tools
<http://www.aiai.ed.ac.uk/~timd/constraints/csptools/> (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
<ptf@cfcl.com> for more details.
----------------------------------------------------------------
|
Comment about this article, ask questions, or add new information about this topic: