Re: Question

Hi Farouk,

Sorry it's taken so long to get back to you.  Things have been quite
busy here, particularly with the recent new ECLiPSe release.

First I want to address your concerns regarding the failure of your
program to scale to the case of a 20-arc graph.  Perhaps you're not
aware of just how difficult a problem this is.  *No* known algorithm
will scale gracefully on this kind of problem.  To give you an idea of
how difficult a problem it is, consider this.  You're wanting to find
the best order to visit 20 arcs in a graph.  If you assume you start
with a given arc, this means there are 19! = 121645100408832000 possible
different orders to choose from.  Suppose you have a naive but fast
algorithm, which simply tests all the possibilities and chooses the
best, at the rate of 1 test every millisecond.  This algorithm will take
nearly 4 million years to finish.  (By comparison, it will find the
optimal solution for your 7-arc graph in under a second.)  No doubt you
can see why your algorithm might have trouble with the larger example,
even though it works OK on the smaller one.

In order to have any hope of solving a 20-arc graph, you have to be able
to reduce the search space to something more manageable, by excluding
the vast majority of potential circuits without ever testing them.  This
is a very challenging problem, and many people have worked on it for a
long time, with some success.  But even with the best known techniques,
make the problem a couple of nodes larger, and it's (effectively)
insoluble again.

I don't think I'd be able to write you a constraint program capable of
solving the 20-arc problem in reasonable time without a significant
amount of effort (days, weeks, or even months).  This isn't my field, so
I don't know which techniques are required, and it would take me time to
find out.  It will also almost certainly require specialised constraints
to be written to achieve maximum pruning, which will take time to design
and implement.  And maybe even then it wouldn't be fast enough.

I think that in attempting to tackle this kind of problem with
constraint programming at this time, you're trying to run before you
know how to walk.  Constraint programming is great for a broad range of
things, and a short, simple constraint program can often quickly give
you answers to reasonably difficult problems.  But for a problem as
difficult as the one you seem to want to tackle, in order to achieve the
level of pruning required to make it practical, you are going to need to
understand in detail how the constraint system you're using works, which
kinds of constraints give you strong propagation and which ones don't,
which kinds of models and formulations work and which ones don't, how to
design and implement your own constraints when the provided ones are not
good enough, etc., etc.  Unfortunately, you don't have this knowledge at
this time, and until you do, it is unlikely that you will succeed in
your endeavour.  Also unfortunately, I can't just tell you what you need
to know, because I don't know all of it myself, even if I had the time
to explain it all to you, which I don't.

If you want to learn constraint programming and/or ECLiPSe, perhaps you
need to start with something a little less ambitious.  If you just want
to get this particular problem solved, and you have expertise in another
field such as OR, then perhaps your best bet is to use the techniques
you know.

If you do wish to persist with learning ECLiPSe, I strongly recommend
that you try reading some more books and papers on constraint
programming.  One book I can suggest as a good starting place would be
"Programming with Constraints: An Introduction" by Kim Marriott and
Peter Stuckey.  (Disclaimer: I haven't actually read much of the book,
but it seems to cover a lot of good material, and I owe a lot of what I
know about constraints to the authors: Peter was my PhD supervisor and
Kim was my boss at my previous job.)  You can find other reading
material in the bibliography of this book, and perhaps others on this
list will be able to recommend some stuff.  It would also be helpful if
there was somebody local to yourself who could provide advice and answer
some of your questions (unfortunately we don't have the resources here
to provide the level of support you seem to be looking for).


Best wishes,
Warwick