Re: Question

Hi Farouk,

I'm afraid I'm still struggling to figure out what you're trying to do
(and looking at your code hasn't really helped).

You wrote:
> To answer your questions, actually what I would like to implement is a
> case where I have n-nodes of a graph with costs Ci, i = 1,..,n
> associated with the edges of the graph. Cij are costs of going from node i
> to node j. The ordering I need to implement is just like a sequence of the
> edges such that the costs for traversing edge i (Ci) is the accumulated
> cost of all the edges traversed so far plus the cost of going from the
> second node of the previous edge to the first node of the current edge
> plus the cost of traversing the current edge itself.

This description doesn't seem to make sense.  You say you have a graph
with n nodes.  You then say that you have costs Ci corresponding to the
edges of the graph, with i ranging from 1 to n.  This implies you have
exactly the same number of edges in the graph as you do nodes.  Is this
the case?  If so, you seem to have left out some important information
about the graph.  If not, then please explain what you really mean.

You then say Cij is the cost of going from node i to node j.  How is
this different from Ci?  Are they related?

Hang on, I think I've just figured out an important piece of the
puzzle.  I was assuming you were starting with some graph, and trying to
find a path through that graph which satisfies some properties you're
interested in.  This is how it's normally formulated for this kind of
graph-based problem.  But it seems you've been thinking of it as
starting with a bunch of nodes and adding in some edges (rather than
selecting some edges from a given set).  What is still rather unclear is
how you know/record where edge `i' goes --- given you didn't specify
this, I assumed it was known because edge `i' was fixed, which is how I
came to be assuming you were selecting edges from an existing graph.


I think the main problem you have here is that you don't have a good,
solid explanation of the problem you're trying to solve, nor of how the
variables you're using relate to this problem description.  Whenever I'm
trying to solve a constraint problem where the solution is not
immediately obvious, the first thing I do is try to write down a precise
description of the problem, including what information I'm given, and
what information I'm trying to figure out.  I then think about what
variables/values/data structures I think I will need to represent that
problem, and write them down, including exactly what they represent.  I
then try to write down all the constraints I think I will need, plus any
other relevant notes or explanations I think somebody else will need to
understand what I'm trying to do.  This then gives me a precise,
concrete model I can use to start trying to implement.  Doing this often
shows up problems or flaws in the way I've decided to represent
something, and I'll go back and revise it, sometimes 3 or 4 or more
times.  It's *much* easier to fix conceptual problems at this point than
when you're in the middle of trying to code it and you're distracted by
a lot of incidental details.  It also means that if you need to ask
somebody for help down the track, you have a nice description you can
give them to help them understand what you're trying to do.


After having spent several hours on this, I believe I have figured out
just what it is you're trying to do, so I'm going to try to get you
started on such a description for your program:

We have a graph containing N nodes, labelled 1 to n.  The graph is
complete, meaning there is an arc from every node to every other node. 
The cost of traversing the arc from node i to node j is given, and may
be different from the cost of traversing the arc in the opposite
direction.  We want to find a Hamiltonian cycle [this is what you want
right?  a path that visits every node and ends up back where it
started?] that satisfies [insert your criteria here --- are we
minimising cost?  you can talk more about side constraints later].  As
well as the cost for traversing an arc, there is a cost for visiting
each node.  Note that while this does not affect which cycle(s) have
minimal cost (since all nodes are visited by all possible cycles), it
can affect whether a cycle is feasible, since there may be constraints
on the cumulative cost at various points in the cycle.
[etc.]

Flesh this out (correcting anything I've got wrong), talking about what
kinds of constraints there are, etc.  If you like, post it back to the
mailing list when you're done and I'll give you some feedback.  Then you
can move on to the next step, which is identifying which variables you
need (because you have explicit constraints on them) and just how you're
going to represent the cycle, etc., and how you're going to tie it all
together.  Once you've got that right, then we can worry about how to
express it in ECLiPSe.

Note that there is a *lot* of literature out there on Hamiltonian cycles
and the Travelling Salesman Problem (TSP).  I strongly suggest you go
have a look at some of it to see how other people have modelled this
kind of stuff --- maybe you'll get some inspiration.  I'm sure somebody
in your department can give you some pointers as to where to start
looking.


I have also attached to this email a real example of the above process
from when I was solving the "domino" puzzle Doug Edmunds posted at the
start of the year.  I include this particular example because it shows
that most of the way through, I realised I had made a poor choice of
data structure (a list of lists), and revised that choice (used an
array).

And of course, once you've gone to the trouble of producing this
description, the final version should of course be included with the
program as documentation.  :)

Cheers,
Warwick
> Message-ID: <000d01bf561a$6b3f1d20$818a41d8@daehp>
> From: "Doug Edmunds" <edmunds@pacifier.com>
> To: "eclipse-users" <eclipse-users@icparc.ic.ac.uk>
> Subject: domino puzzle
> Date: Mon, 3 Jan 2000 10:42:04 -0800
> 
> Happy New Year!
> 
> Can anyone suggest an approach to solving this type of puzzle?
> 
> There are 28 dominos 0-0 to 6-6 ( 0-0, 0-1,0-2,..., 5-5,5-6,6-6).
> 
> They are layed out randomly on a rectangular shape so that
> there are 8 numbers across and 7 down.  There is no relation 
> between adjoining tiles.  
> 
> Tiles can appear left-right or up-down: 3-5 can be positioned 
> 3-5, 5-3,
> 3 
> 5, 
> or as 
> 5
> 3. 
> 
> The object is to reconstruct the tile-boundaries, using eclipse.  
> No tile is used twice.  Each number in the grid is part on only
> one tile.
> 
> Puzzle pattern:
> 
> 3 1 2 6 6 1 2 2
> 3 4 1 5 3 0 3 6
> 5 6 6 1 2 4 5 0
> 5 6 4 1 3 3 0 0 
> 6 1 0 6 3 2 4 0
> 4 1 5 2 4 3 5 5
> 4 1 0 2 4 5 2 0 
> 
> 
> Doug Edmunds
> edmunds@pacifier.com
> 3 Jan 2000


Proposed model:

Have a set of boolean variables, one for each boundary between adjacent
squares, indicating whether or not a tile lies across that boundary.  We
then have two sets of constraints.

1)  Each square must have exactly one boundary with a tile lying across it.

2)  For each pair of numbers from [0..6], exactly one boundary having these
numbers on either side must have a tile lying across it.


If the squares are labelled (1,1) through (7,8), then label the boundaries
as follows:

1,1  H11  1,2  H12  1,3  H13  1,4  H14  1,5  H15  1,6  H16  1,7  H17  1,8
V11       V12       V13       V14       V15       V16       V17       V18
2,1  H21  2,2  H22  2,3  H23  2,4  H24  2,5  H25  2,6  H26  2,7  H27  2,8
V21       V22       V23       V24       V25       V26       V27       V28
3,1  H31  3,2  H32  3,3  H33  3,4  H34  3,5  H35  3,6  H36  3,7  H37  3,8
V31       V32       V33       V34       V35       V36       V37       V38
4,1  H41  4,2  H42  4,3  H43  4,4  H44  4,5  H45  4,6  H46  4,7  H47  4,8
V41       V42       V43       V44       V45       V46       V47       V48
5,1  H51  5,2  H52  5,3  H53  5,4  H54  5,5  H55  5,6  H56  5,7  H57  5,8
V51       V52       V53       V54       V55       V56       V57       V58
6,1  H61  6,2  H62  6,3  H63  6,4  H64  6,5  H65  6,6  H66  6,7  H67  6,8
V61       V62       V63       V64       V65       V66       V67       V68
7,1  H71  7,2  H72  7,3  H73  7,4  H74  7,5  H75  7,6  H76  7,7  H77  7,8

The constraint 1) for the square (i,j) is then

	Hi(j-1) + Hij + V(i-1)j + Vij = 1

where for convenience we define Hi0 = Hi8 = V0j = V7j = 0 for all i, j.

For constraint 2, we collect all horizontal and vertical boundaries between
squares matching each pair of numbers, sum them, and equate to 1.


Store Hij's and Vij's in lists of lists, where i selects the sublist and j
selects the element.  i.e.

	[[H11, H12, ..., H17], [H21, ..., H27], ..., [H71, ..., H77]]
	[[V11, V12, ..., V18], [V21, ..., V28], ..., [V61, ..., V68]]

To construct the constraints 1), iterate over i, keeping the "previous"
sublist of V(i-1)j's (initially a list of zeros).  Then iterate over j,
keeping the "previous" Hi(j-1) (initially zero).
	- have to handle the case where we run out of H's (Hi8 = 0)
	- have to handle the case where we run out of Vi's (V7j = 0)



... Actually, scrap the above and use arrays!  :-)
It would then be better if the Hs were H12 .. H78 and the Vs were V21 .. V78
so that Hi1 and V1j can be set to 0, and the array indexing works out.

This yields:

If the squares are labelled (1,1) through (7,8), then label the boundaries
as follows:

1,1  H12  1,2  H13  1,3  H14  1,4  H15  1,5  H16  1,6  H17  1,7  H18  1,8
V21       V22       V23       V24       V25       V26       V27       V28
2,1  H22  2,2  H23  2,3  H24  2,4  H25  2,5  H26  2,6  H27  2,7  H28  2,8
V31       V32       V33       V34       V35       V36       V37       V38
3,1  H32  3,2  H33  3,3  H34  3,4  H35  3,5  H36  3,6  H37  3,7  H38  3,8
V41       V42       V43       V44       V45       V46       V47       V48
4,1  H42  4,2  H43  4,3  H44  4,4  H45  4,5  H46  4,6  H47  4,7  H48  4,8
V51       V52       V53       V54       V55       V56       V57       V58
5,1  H52  5,2  H53  5,3  H54  5,4  H55  5,5  H56  5,6  H57  5,7  H58  5,8
V61       V62       V63       V64       V65       V66       V67       V68
6,1  H62  6,2  H63  6,3  H64  6,4  H65  6,5  H66  6,6  H67  6,7  H68  6,8
V71       V72       V73       V74       V75       V76       V77       V78
7,1  H72  7,2  H73  7,3  H74  7,4  H75  7,5  H76  7,6  H77  7,7  H78  7,8

The constraint 1) for the square (i,j) is then

	Hij + Hi(j+1) + Vij + V(i+1)j = 1

where for convenience we define Hi1 = Hi9 = V1j = V8j = 0 for all i, j.

For constraint 2, we collect all horizontal and vertical boundaries between
squares matching each pair of numbers, sum them, and equate to 1.