Re: Question

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,
Warwick