From: Warwick Harvey <wh_at_icparc.ic.ac.uk>

Date: Fri 27 Oct 2000 06:30:54 PM GMT

Message-ID: <39F9C9DE.B666643A@icparc.ic.ac.uk>

Date: Fri 27 Oct 2000 06:30:54 PM GMT

Message-ID: <39F9C9DE.B666643A@icparc.ic.ac.uk>

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).Received on Fri Oct 27 19:33:56 2000

*
This archive was generated by hypermail 2.1.8
: Wed 16 Nov 2005 06:07:06 PM GMT GMT
*