Graph Theory and Constraint Programming
Exercise 1

Aim

This exercise is a brief exposure to constraint logic programming

Setting Up

In this course, we will be using the constraint logic programming languages ECLiPse, CLP(R), and perhaps SICStus prolog. Follow the links to find out how to set them up.

Task 1

Consider the problem of computing compound interest. In some programming language with which you are familiar, imagine writing a program to answer the question:

What will be the final balance if I borrow $P for T years, at an interest rate of I%, and annual repayments R?

Repeat this with the question:

If I can afford to make annual repayments R over a period T, and the interest rates are I%, how much can I borrow?

Finally, imagine a program which can give meaningful answers to the question:

In general, if I'm looking at a T year loan with I% interest rates, what is the relationship between the principal sum, the repayments, and the final balance?

Now take a look at a simple CLP(R) program (here's a commented version). Copy and paste this program into a file in your own area called "mort". Now load up CLP(R), and input the program mort:


sealion_246 %clpr

CLP(R) Version 1.2a
(c) Copyright International Business Machines Corporation
1989 (1991, 1992) All Rights Reserved

1 ?-  [mort].

(Note that you will get a message regarding poor style in the program - ignore it, this is an issue for later).

Run the program to answer the first question above for a $1000 principal borrowed at 10% interest over 10 years, with $150 annual repayments:
```
2 ?- mortgage(1000,10,10/100,150,B).

B = 203.129

*** Retry? ;

*** No
```
indicating that the balance is $203.13 (the "retry" asks clpr if there is any other balance that satisfies the requirements).
Run the program to anwer the second question above for a 10 year loan at 10% interest, final balance of zero and annual repayments of $150:
```
3 ?- mortgage(P,10,10/100,150,0).

P = 921.685

*** Retry? ;

*** No
```

Last, run the program to answer the third question above for a 10 year loan at 10%:

4 ?- mortgage(P,10,10/100,R,B).

P = 0.385543*B + 6.14457*R

*** Retry? ;

*** No

Conclusions

The "mort" program is as simple as, or simpler than, programs in other languages
The one program can handle multiple tasks
CLP(R) programs are in effect runnable specifications, reducing the risk of programming errors
Constraint logic programs can produce general answers, not just specific answers

Task 2

CLP(R) is especially aimed at problems involving real constraints; The ECLiPSe system, by contrast, is mainly aimed at combinatorial constraint problems, or problems involving both arithmetic and combinatorial constraints.

You may have come across cryptarithms, for example


 SEND
+MORE
-----
MONEY

The idea is that

Each letter stands for a single decimal digit (the same letter in different places stands for the same digit)
Different letters stand for different digits
Leading digits cannot be zero

The aim is to solve the cryptarithm; it is often assumed that there is only a single solution.

Try solving the program for yourself.

Try to design a program to solve it, in a language you're familiar with

Finally, try out ECLiPSe:

Take a look at an ECLiPSe program for this. Copy and paste this into a program in your own area called "sendmore". Start up ECLiPSe and load the program:


sealion_251 %eclipse
ECLiPSe Constraint Logic Programming System [sepia parallel mps]
Version 4.0.2, Copyright ECRC GmbH and ICL/IC-Parc, Fri Jul 28 15:30 1998
[eclipse 1]: [sendmore].
structures.pl compiled traceable 3984 bytes in 0.00 seconds
lists.pl   compiled traceable 6436 bytes in 0.01 seconds
sorts.pl   compiled traceable 1292 bytes in 0.00 seconds
fd_domain.sd loaded traceable 27392 bytes in 0.06 seconds
fd_arith.sd loaded traceable 72912 bytes in 0.15 seconds
fd_util.pl compiled traceable 2116 bytes in 0.01 seconds
fd_chip.pl compiled traceable 4744 bytes in 0.02 seconds
fd_elipsys.pl compiled traceable 10836 bytes in 0.02 seconds
fd.sd      loaded traceable 19300 bytes in 0.21 seconds
sendmore   compiled traceable 1352 bytes in 0.22 seconds

yes.

Now ask ECLiPSe to solve the problem:

[eclipse 2]: smm(S,E,N,D,M,O,R,Y).

S = 9
E = 5
N = 6
D = 7
M = 1
O = 0
R = 8
Y = 2     More? (;)

no (more) solution.

(like CLP(R), ECLiPSe gives you the option of finding more than one answer; typing ";" leads to further searching - in this case unsuccessful, ie there is only one solution). You may find it interesting to trace what ECLiPSe is doing:


[eclipse 4]: trace(smm(S,E,N,D,M,O,R,Y)).

You may find ECLiPSe's approach is somewhat similar to your human approach!

Further Conclusions

Relatively simple constraint logic programms can solve fairly complex combinatorial problems
The search process involved are fairly similar to those humans would use, at least in some cases