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

Date: Mon 23 Oct 2000 04:16:27 PM GMT

Message-ID: <39F4645B.659286A2@icparc.ic.ac.uk>

Date: Mon 23 Oct 2000 04:16:27 PM GMT

Message-ID: <39F4645B.659286A2@icparc.ic.ac.uk>

FAROUK AMINU wrote: > Hi everyone! > > I have been trying to solve a problem of the following nature: > > Given [V1, V2, V3]::1..3, alldifferent([V1, V2, V3]), > > I have costs C12, C13, C21, C23, C31, C32. I wish to have final costs, > C1, C2, C3 such that, > > if V1 = 1, V2 = 2, V3 = 3, then C1 = 0 + Const, > C2 = C1 + C12, C3 = C2 + C23. > > But if V1 = 3, V2 = 1, V3 = 2 then C3 = 0 + const, C1 = C3 + C31, C2 = C1 > + C12. > > If V1 = 2, V2 = 3, V3 = 1, then C2 = 0 + const, C3 = C2 + C23, C1 = C3 + > C31. > > In essence, the additions are done based on which variable is assigned > which value. kindly help as this has been a very difficult thing for me to > do for the last three weeks. Hi Farouk, I wonder whether there is a better way of modelling your problem which avoids this variable-value dependence? I suspect using a different model would make it much easier for you to solve your problem. But it's hard to give advice on this, since you have not given us much information about the original problem --- I can't tell whether something you've specified is required to be the way it is, or whether it's just the way you've chosen to make it. It seems like you have three vertices/nodes/whatever, numbered 1, 2, and 3. You then have three variables V1, V2 & V3 which say which of those nodes is first, which is second, and which is third, respectively. C12, C13, etc. are costs of travel/flow/whatever from node 1 to 2, from 1 to 3, etc., respectively. And C1, C2 & C3 are the accumulated costs at node 1, 2 & 3, respectively. Attempting to implement your model exactly as you've presented it, I end up with something like this: [V1, V2, V3] :: 1..3, alldifferent([V1, V2, V3]), % Set up boolean variables Vij which are set to 1 iff % the i'th node visited is node j. V11 isd V1 #= 1, V12 isd V1 #= 2, V13 isd V1 #= 3, V21 isd V2 #= 1, V22 isd V2 #= 2, V23 isd V2 #= 3, V31 isd V3 #= 1, V32 isd V3 #= 2, V33 isd V3 #= 3, % Set up variables O1, O2, O3 whose values give the position in the % sequence of the nodes 1, 2, 3 (respectively). O1 #= V11 + 2 * V21 + 3 * V31, O2 #= V12 + 2 * V22 + 3 * V32, O3 #= V13 + 2 * V23 + 3 * V33, % Set up constraints for the accumulated costs, based on whether the % node is first in the sequence, or follows another. (O1 #= 1) #=> (C1 #= Const), (O1 #= O2 + 1) #=> (C1 #= C2 + C21), (O1 #= O3 + 1) #=> (C1 #= C3 + C31), (O2 #= 1) #=> (C2 #= Const), (O2 #= O1 + 1) #=> (C2 #= C1 + C12), (O2 #= O3 + 1) #=> (C2 #= C3 + C32), (O3 #= 1) #=> (C3 #= Const), (O3 #= O1 + 1) #=> (C3 #= C1 + C13), (O3 #= O2 + 1) #=> (C3 #= C2 + C23). ... not that I'd really recommend that as a solution. (If you don't understand the use of `isd/2' and `#=>/2' I suggest reading the library manual section on the finite domain constraint solver, in particular the section titled "Evaluation Constraint Predicates".) Some questions for you. Do you need all of C1, C2 & C3, or are you just interested in the overall total cost? Do you specifically need the accumulated costs at node 1, 2 & 3, or will the costs after the first, second and third nodes do (and you can figure out which nodes these are later)? Similarly, do you need V1, V2 & V3 to indicate which are the first, second, and third nodes (respectively), or could you instead have variables (say) O1, O2 & O3 which give the position in the sequence for nodes 1, 2 & 3, respectively? (I've used this in the above solution. E.g. corresponding to your V1 = 3, V2 = 1, V3 = 2 example, you would have O1 = 2, O2 = 3, O3 = 1, saying that node 1 is the second node to be visited, node 2 is the third node, and node 3 is the first.) If you don't have any other constraints on C1, C2 & C3, nor on V1, V2 & V3, you can write a much simpler set of constraints to model your problem. In the following example Bij is set to 1 if there's a "flow" from i to j, and 0 otherwise. [O1, O2, O3] :: 1..3, alldifferent([O1, O2, O3]), B12 isd (O2 #= O1 + 1), B13 isd (O3 #= O1 + 1), B21 isd (O1 #= O2 + 1), B23 isd (O3 #= O2 + 1), B31 isd (O1 #= O3 + 1), B32 isd (O2 #= O3 + 1), Cost #= Const + B12 * C12 + B13 * C13 + B21 * C21 + B23 * C23 + B31 * C31 + B32 * C32. Then once you've found your solution in terms of these variables you can work out the values of V1, V2, V3, C1, C2 & C3 (if you actually need to know these). This is a much simpler model, which achieves stronger propagation (e.g. it will give bounds on the Cost variable right away) and is more efficient. If it turns out stronger propagation is required, some or all of the following redundant constraints can be added: % Exactly two flows are active. B12 + B13 + B21 + B23 + B31 + B32 #= 2, % Flow between a pair of nodes can only be in one direction. B12 + B21 #<= 1, B13 + B31 #<= 1, B23 + B32 #<= 1, % At most one outgoing flow from a node. B12 + B13 #<= 1, B21 + B23 #<= 1, B31 + B32 #<= 1, % At most one incoming flow to a node. B21 + B31 #<= 1, B12 + B32 #<= 1, B13 + B23 #<= 1, These don't change the answers you get, but they help prune the search space (useful for larger examples). If you find yourself writing an ugly set of constraints like the first solution, you should consider having a look at your model, and seeing if you can re-cast it somehow to make it simpler. Cheers, WarwickReceived on Mon Oct 23 17:16:57 2000

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