• Week by week
• Library including
• TD exercises and solutions
• Getting started with CHIP
• CHIP online documentation
• Project  (student repository: file:/net/i1/PROJETS/PL/)
• Prolog and Constraint Industry

Week by week

• Week 1 : November 17--21, 2003
• Week 2 : November 24--28, 2003
• Week 3 : December 1--5, 2003
• Week 4 : December 8--12, 2003
• Week 5 : December 15--19, 2003
• Week 6 : January 5--9, 2004
• Week 7 : January 12--16, 2004

Week 1 : November 17--21, 2003

Lecture 1: Beginning of: LP, introduction, functional versus relational programming, first order logic syntax and semantics, Prolog, Horn clauses, Prolog problem semantics, substitutions, pure Prolog program syntax and semantics (logical, proof tree, least model, fixed point semantics),

lp.html slides 1--11, 24--30, 21--23, 31--46.

Week 2 : November 24--28, 2003

TP 1 (on project) with G1:

• rapid reading of project specification, and CHIP 5.4 Reference Manual cycle/2 constraint (pages 196-197). See ~gloess/chip/clp/project/2003_2004/test_cycle.pl program for examples of cycle/2 involving two graph examples drawn by students explaining the notion of a graph, and cycle/2 semantics. We took a picture of first graph;
• CHIP finite domain constraint principle:
1. Declare domain variables, for example:
[X, Y]::1..5, Z::[1, 3, 7],
2. Specify problem constraints, e.g.:
X #< Y, ..., cycle(..., ...),
3. Eventually enforce domain variable enumeration (labeling), e.g.,
indomain(X), indomain(Y), indomain(Z).
or
labeling([X, Y, Z], 0, most_constrained, indomain).
• Next step (for Friday):
• read and understand cycle/2 thru cycle/11 documentation (provide additional test examples);
• understand the specific Surfn'fly company problem, and explain it in terms of a graph problem; then map it into an appropriate set of CHIP constraints;
• start writing your report!

lp.html slides 1--11, 24--30, 21--23, 31--46.
roll call Friday November 28, 2003, 9:47am, amphi B

• further analysis of problem and cycle documentation, see
• ~gloess/chip/clp/project/2003_2004/notes.txt : some notes on student ideas and work reports;
• the surfn_fly_data.pl test graph (nodes are flights, arcs are correspondances ignoring time constraints) or restricted restricted graph (crossing out some forbidden arcs);
• a test program for the above graph, using cycle/2 program, written by a group of students, and slightly improved during class: essai1.pl ;
• next step:
• start writing the report;
• find out how to take time constraints into account (read and understand cycle/11 at least);
• write the specific route planner, corresponding to surfn_fly_data.pl .

Week 3 : December 1--5, 2003

• SEND+MORE=MONEY, exercise XV from sheet (pdf | ps | doc), template file  money.pl available from ~gloess/chip/clp/exercices directory;
• if time permits, map of Yougoslavia, exercise XI from sheet (pdf | ps | doc); map.pl template file available from ~gloess/chip/clp/exercices directory;

• all groups are visited; many have written a "partial" specific route planner; some have started writing the report;
• conclusion: see ~gloess/chip/clp/project/2003_2004/notes.txt and:
• the graph we need to consider:
• nodes are flights;
• arcs correspond to geographic correspondance (landing airport of predecessor flight must match departure airport of successor flight);
• we can encode time over the whole week (from Monday midnight to Sunday midnight) by a number of time units in the range 0..24*4*7;
• cycle/9 seemed interesting for expressing time constraints (plane must land before next take off) over each route (that is, each circuit); however, it is not suitable, because there is no total order over a circuit, so that we would have to specify some nodes as "unused", but we have no way to do that until we know the solution!
• cycle/11 will be used to express these time constraints:  we shall use a matrix (c_ij) such that c_ij = 1 if there is a geographic correspondance between flights i and j, but this correspondance does not respect time constraints, 0 otherwise; in order to enforce exactly 1 time constraint violation for each circuit, we force the overall Cost to be equal to the number of circuits;
• how to make sure that the total duration of each plane route is not more than a week?
• it is not sure whether another cycle/5 or cycle/11 constraint would help: if this seems to difficult, leave it out!
• next step:
• finish the specific route planner, leaving out "route", "route_flight" and "next_flight" predicates, which may be shared by the generic and specific route planner;
• start implementing the generic planner:
• pure (or almost pure) logic programming will be used to generate constraints.

lp.html slides 12--20, 47--59,
correctness of resolution (pdf | Adobe pdf | ps | Adobe ps | doc).
5 december 2003, 9:37am

• students give a short presentation of their work including report writing: see notes.txt;
• conclusion: most teams have completed or are close to completing the specific route planner! Some of them have found a clever way of checking the overall duration of each circuit (using a second "cycle/11" constraint in their program, with appropriate weights and matrix). It is possible (??) that the "surfn_fly_data.pl" example yields no solution with a duration of all circuits less or equal to a week: I propose to relax the constraint and accept a duration of 8 days or more if necessary (maybe 2 weeks), if one wants to enforce the duration constraint and still find solutions;
• next step:
• think pure Prolog (for generating constraints);
• start implementing the generic route planner:
• think pure Prolog (for generating constraints),
• never define a predicate with clauses before having written down (within comments) the semantics of this predicate using a natural language sentence relating the predicate parameters;
• look at gift: findall.pl and trimming.pl in ~gloess/chip/clp/project/2003_2004/;
• continue the report.

Week 4 : December 8--12, 2003

•  
• conclusion: you are on your own!
• next step:
• finish the project!

• if necessary, map of Yougoslavia, exercise XI from sheet (pdf | ps | doc); map.pl template file available from ~gloess/chip/clp/exercices directory;
• 8-queens and N-queens, exercise XVII from sheet (pdf | ps | doc) -- not done;
• generalization of Yougoslavia map coloring problem, to coloring of any map, whose topology is represented by an adjacency relation, given by a Datalog program, e.g.:
adjacent(r1, r2).
adjacent(r1, r3).
...
or by a graph:
[[r1 | r2], [r1 | r3] ...].

clp.html slides 1--20;
12 december 2003, 10:02am

Week 5 : December 15--19, 2003

• unfinished exercises from TD 4;
• gold medal, exercise IX  from sheet (pdf | ps | doc);

Wednesday December 17, 2003, 11:27am, I107

A lot more pictures ... on mystery solution (important for final!)

Lecture 5: End of: CLP, motivation and operational semantics, CLP(X) families (for X = Boolean, QLin, FD, trees), constraint satisfaction, delaying non linear constraints,

clp.html slides 1--20;
19 December 2003, 9:34am, Theater B
Note infinite tree solution to equation X=f(X) on second picture (courtesy Mathias Klockenbring)!

clp.html slides 21--42;

Week 6 : January 5--9, 2004

see revapp search tree exercise solution

• gold medal, exercise IX  from sheet (pdf | ps | doc);
• 8-queens and N-queens, exercise XVII from sheet (pdf | ps | doc);

clp.html slides 21--42;

Back to Week by Week or Top

Week 7 : January 12--16, 2004

CLP(FD) with exercises from:

• gold medal, exercise IX  from sheet (pdf | ps | doc);

8-queens and N-queens, exercise XVII from sheet (pdf | ps | doc);

• When use "is", when use "#="?
• Answer: Never use "is", which is an obsolete construction, a little better than "assignment statement" in procedural languages. Then the question becomes: When use "#=", when use "^=", when use "="? There are indeed three equalities in CHIP because there are three constraint languages (ignoring boolean constraints that we have not really studied):
• "#=" for finite domain constraint language, e.g., [X, Y, Z]::1..100, 5*X+3 #= Y+Z.
• "^=" for linear rational constraint language, e.g., 3*X-7 ^= 7*Y+Z.
• "=" for regular tree constraint language, e.g., f(a, b(Y, Z)) = f(U, b(U, U)), which corresponds to pure Prolog unification (when restricted to finite trees). Note that pure Prolog equality may be defined with just one clause:
equals(X, X).       % definition of equality.
• What is a search tree (use "mystery" example)?
• Answer: The example was redone on the blackboard, because I could not make the video projector work!
see Mystery Search Tree for a solution done with TD group G1;
A subsidiary question was related to unification of term1=m(X, c(a, c(b, n)) and term2=m(c(E1, X1), c(E1, S1)). How do we know that substitution
{<X, c(E1, X1)>, <E1, a>, <S1, c(b,n)>}
is not a unifier of term1 and term2 whereas
{<X, c(a, X1)>, <E1, a>, <S1, c(b,n)>}
is a unifier of these terms. The answer was that if we apply the first substitution to both terms, we get two different instances; on the contrary, applying the second substitution to terl1 and term2 yields a common instance.
• What is a proof tree?
• Answer: A search tree, as seen above, contains all the possible proofs (and answers) to a query (given as a list of atoms); each branch corresponds to a proof (if it ends with the empty list of atoms), a finite failure (if it ends with a non empty list of atoms), or non termination (if it is infinite). A proof tree is just a single proof of a single ground atom (its root). A proof tree is finite. Each node is labeled with a single ground atom (there are no variables). A node in a proof tree, with each immediate successors, must correspond to a program clause instance (the node is an instance of the clause head, and the successors are instances of the clause hypotheses, by the same substitution). A leaf in a clause must be labeled by a clause instance: hence this clause must have no hypothesis (it must be a fact). I took the example of the leftmost branch in the mystery search tree, to draw a proof tree of the "m(c(a, c(b, n)), c(a, c(b, n)))" ground atom, but I forgot to take a picture ...
• Backtracking techniques?
• Answer: this was the subject of Lecture 6: I explained "GT", "SB", "FC", "LA" techniques for solving a binary constraint satisfaction problem.
• Why is CHIP sometimes rejecting instantiated queries, whereas it accepts the same queries with numbers replaced with variables?
• Answer: This occurs with finite domain constraints. They require domain declaration of each domain variable, before it is used in a finite domain constraint. For example, we declare X::1..5. If the query is such that X gets bound to 3 (through unification), then CHIP may encounter the declaration 3::1..5, which it does not like! May be CHIP is a little too strict regarding domain declaration. For example, it does not allow double declaration of the same domain variable. It is not always easy to know where to declare a variable: it is usually best to declare it from the outermost context (from the caller rather that from the callee). On the other hand, CHIP is not strict with labeling. For example, indomain(X) will not trigger an error if X is already instantiated to a number; this is fortunate, because the user has no way to know when variables get instantiated to numbers due to constraint propagation (and domain reduction).

        

Back to Week by Week or Top

Library

* Use ghostview with Landscape orientation and letter format.

Acrobat Reader: for easy access through your navigator, edit your preferences and associate "acroread %s" handler with "Portable Document Format" application.

Back to Top

---

Project

A solution will be made is now (17 December 2003) available from

~gloess/chip/clp/project/2003_2004/solution/ directory.

Tentative (unofficial) marks will be proposed to the jury and made available.

The project is to be done by teams of three students. The team list is established by Philippe Duchon, see his document entitled "Projets de première année".

Project deadline is Friday 12 December 2003. The project shall be submitted under the two following forms and conditions:

1. before 4:00pm at Ms Francoise Verdier's office for the printed version;
2. and by 11:59pm on the appropriate directory opened by Mr Michel Pallard for the electronic version.

Any delay will automatically yield a mark of 0: file last modification date will be matched against the relevant deadline.

Back to Top

Prolog and Constraint Industry

• Cosytec
• ILog
• PROLOGIA
• AFPLC (association)
• ALP (association)

© Copyright 1999-3000 Paul Y Gloess