Re: Question

Hi Farouk,

Thanks for your explanation.  I now understand what you are trying to do
much better!  :)

It seems that the crux of your problem is that you want a
two-dimensional equivalent to the `element' constraint.  You want to be
able to relate the variable representing the arc you've just traversed,
the variable representing the arc you wish to traverse next, and the
cost of travelling between them.  That way you can get your Tij's, in
the same way as your Ci's, and you can compute your total cost just
fine.

Unfortunately, there is no two-dimensional `element' constraint.  There
are a couple of ways around this.  One is to map the two variables
you're interested in onto a single variable and use that with the
element constraint.  For instance:

	A12 #= 7 * A1 + A2,
	element(A12, [...], T12),
	etc.

The main drawback with this approach is that it won't propagate very
well (the equality constraint will only do bounds propagation, whereas
you probably want full arc consistency to get the most out of the
element constraint).

The usual tool I pull out in this kind of situation is the `propia'
library.  It's fairly heavy (high overhead), but on a complex problem
can often make up for this by substantially reducing the size of the
search tree.  Plus it's quite straightforward to use, and can often be
tried out quite quickly to see whether it helps.  Basically it allows
you to convert a predicate into a constraint.  (Read the section on
`propia' in the library manual if you're not familiar with it.)  In your
case, you can define a predicate which knows the cost of the shortest
paths between nodes:

    % 
    % shortest_path(From, To, Cost):
    %   Fact table giving the cost `Cost' of travelling from the node at
the
    %   end of arc `From' to the node at the beginning of arc `To' via
the
    %   shortest path.
    %
shortest_path(1, 2, 0).
shortest_path(1, 3, 3).
shortest_path(1, 4, 8).
shortest_path(1, 5, 3).
shortest_path(1, 6, 4).
shortest_path(1, 7, 4).
shortest_path(2, 1, 10).
...
...
shortest_path(7, 6, 6).

and then convert it into a constraint by calling it as

	shortest_path(From, To, Cost) infers fd

The `infers fd' tell Propia to try to extract as much finite domain
information as possible from the predicate, thus turning it into a
finite domain constraint.

Once you have this, it is straightforward to compute the total cost of a
tour, using the approach you've been trying.

I've attached a program to do exactly this.  (Unfortunately it's a bit
boring that the first optimal solution it finds is `[1, 2, 3, 4, 5, 6,
7, 1]', but if you change the program so that the first edge is a
different one, you can get some more interesting results.)

Note the discussion in the preamble of the program about the ambiguity
of the representation.

There were a number of other things I wanted to talk about, such as
alternative formulations and some things you want to try to avoid in
your constraint programs, but unfortunately I've run out of time, so
they'll have to wait until next week.  I think there are still some
questions of yours I haven't addressed, too (such as what the problems
were with your program).

But one last thing before I go: you said your problem was to find an
Euler tour?  I confess I'm not an expert in this area, so I looked up
some definitions on the net, and it seems that a tour is an Euler tour
if every edge is traversed exactly once.  Is that what you are wanting,
or are you (as I've assumed in my program) just looking for any tour
(traverse each edge at least once)?

Cheers,
Warwick
/*
Program to compute a minimal tour of a directed graph.

Written by Warwick Harvey, wh@icparc.ic.ac.uk,
based on work by Umaru Farouk Aminu, f.aminu@lancaster.ac.uk.


The graph is represented by N arcs, numbered 1 to N, where N is specified
by the `num_arcs/1' predicate.  Each arc has a cost associated with it
(see `arc_cost/2'), which is the cost of traversing the arc.  The actual
structure of the graph is implicit, and is not needed by the program.
Instead, the shortest-path cost of travelling from the node at the end
of any arc to the node at the beginning of any other arc must be provided
(see `shortest_path/3').

Tours are represented by a sequence of N+1 arcs, where the first arc and
last arc are the same, and every other arc appears exactly once.  This is
an implicit representation, since the node at the end of one arc in the
sequence may not be the same as the node at the start of the next arc.
It is assumed that in such a case, a shortest path between the two is
taken to fill out the tour.

Note that this is a somewhat ambiguous representation.  First, if the
shortest path between a pair of nodes is not unique (more than one route
of the same length), then there can be more than one tour which matches
the representation.  Second, for any given tour, there may be more than
one way of representing it.  This is because in general an arc may appear
more than once in the tour (once explicitly and other times implicitly),
and a permutation of the arcs in the representation may result in the same
tour (exchanging one or more explicit arc occurrences with implicit ones).

Despite this drawback, if all one wants is any tour which has minimal
cost, then everything's fine, since it is straightforward to construct
an explicit representation of an optimal tour from an optimal implicit one.

See `minimal_tour/2' for computing an implicit minimal tour.


Note that the predicates providing data about the graph (`num_arcs/1',
`shortest_path/3' and `arc_cost/2') should really go into a separate file to
facilitate working with multiple graphs.
*/


:- lib(fd).
:- lib(propia).
:- lib(listut).


    %
    % num_arcs(N):
    %	N is the number of arcs in the graph.
    %
num_arcs(7).

    %
    % shortest_path(From, To, Cost):
    %	Fact table giving the cost `Cost' of travelling from the node at the
    %	end of arc `From' to the node at the beginning of arc `To' via the
    %	shortest path.
    %
shortest_path(1, 2, 0).
shortest_path(1, 3, 3).
shortest_path(1, 4, 8).
shortest_path(1, 5, 3).
shortest_path(1, 6, 4).
shortest_path(1, 7, 4).

shortest_path(2, 1, 10).
shortest_path(2, 3, 0).
shortest_path(2, 4, 4).
shortest_path(2, 5, 0).
shortest_path(2, 6, 1).
shortest_path(2, 7, 1).

shortest_path(3, 1, 5).
shortest_path(3, 2, 7).
shortest_path(3, 4, 0).
shortest_path(3, 5, 13).
shortest_path(3, 6, 11).
shortest_path(3, 7, 11).

shortest_path(4, 1, 0).
shortest_path(4, 2, 2).
shortest_path(4, 3, 5).
shortest_path(4, 5, 5).
shortest_path(4, 6, 6).
shortest_path(4, 7, 6).

shortest_path(5, 1, 5).
shortest_path(5, 2, 2).
shortest_path(5, 3, 5).
shortest_path(5, 4, 10).
shortest_path(5, 6, 0).
shortest_path(5, 7, 0).

shortest_path(6, 1, 9).
shortest_path(6, 2, 0).
shortest_path(6, 3, 3).
shortest_path(6, 4, 8).
shortest_path(6, 5, 3).
shortest_path(6, 7, 4).

shortest_path(7, 1, 0).
shortest_path(7, 2, 2).
shortest_path(7, 3, 5).
shortest_path(7, 4, 10).
shortest_path(7, 5, 5).
shortest_path(7, 6, 6).


    %
    % arc_cost(Arc, Cost):
    %	Constrains `Cost' to be the cost of traversing the arc `Arc'.
    %
arc_cost(Arc, Cost) :-
	element(Arc, [2, 3, 5, 5, 1, 2, 5], Cost).


    %
    % arc2arc_cost(From, To, Cost):
    %	Constrains `Cost' to be the cost of travelling from the node at the
    %	end of the arc `From' to the node at the start of the arc `To'.
    %
arc2arc_cost(From, To, Cost) :-
	shortest_path(From, To, Cost) infers fd.


    %
    % tour_cost(Arcs, Cost):
    %	Constrains `Cost' to be the cost of traversing the list of arcs
    %	`Arcs' in the given order (including the cost of getting from one
    %	arc to the next).  It assumes the first arc in the list and the last
    %	arc in the list are the same, and so only counts the cost of
    %	traversing that arc once.
    %
tour_cost([Arc | Arcs], Cost) :-
	arc_cost(Arc, Cost0),
	walk_cost(Arc, Arcs, Cost0, Cost1),
	Cost #= Cost1 - Cost0.

walk_cost(_, [], Cost, Cost).
walk_cost(Arc1, [Arc2 | Arcs], Cost1, Cost) :-
	% Add on the cost of getting to Arc2 and then traversing it.
	arc2arc_cost(Arc1, Arc2, Cost12),
	arc_cost(Arc2, Cost2),
	SubTotal #= Cost1 + Cost12 + Cost2,
	walk_cost(Arc2, Arcs, SubTotal, Cost).

    %
    % constrain_tour(Tour, Cost):
    %	Constrain `Cost' to be the cost of a tour traversing the arcs `Tour'
    %	in order (with possible implicit arc traversals to get from one arc
    %	to the next), and finishing up back at the first arc.
    %
constrain_tour(Tour, Cost) :-
	num_arcs(N),
	N1 is N + 1,
	length(Tour, N1),
	Tour :: 1..N,

	% Make the first and last arcs the same.
	Tour = [Arc | Arcs],
	last(Arc, Arcs),

	% Make all the arcs different (except the first, since it's
	% required to be the same as the last).
	alldifferent(Arcs),

	% Constrain the cost of the tour.
	tour_cost(Tour, Cost).

    %
    % minimal_tour(Tour, Cost):
    %	Find a minimal cost tour of the graph, returning a sequence of arcs
    %	to visit `Tour', and the associated cost of the tour `Cost'.
    %
minimal_tour(Tour, Cost) :-
	% Set up the constraints.
	constrain_tour(Tour, Cost),

	% Arbitrarily choose the first arc to be 1.
	Tour = [1 | _],

	% Find a minimal solution.
	minimize(labeling(Tour), Cost).