MatMod logo

Wolf-Goat-Cabbage (alcuin1)

Run LPL Code  ,  PDF Document

Problem

The problem has been described in alcuin. Here a different formulation is presented.

Modeling Steps

In this formulation the “man” is modeled explicitly. So, the set of “objects” is i,j ∈{man, wolf, goat, cabbage}, p ∈{xleftright} is the set of the river side, and t is the set of time periods.

  1. First, we define a relation ci,j defining all object tuples that cannot be on the same river side without the man:

    ci,j = {(wolf,goat),(goat,cabbage )}
  2. The state 0-1 variable is xi,p,t which is 1, if object i is on the river side p at the beginning of time period t.

  3. At the beginning all objects are on the left side:

    xi,1,1 = 1   forall i
  4. Any object at any time can only be on one side:

    ∑ xi,p,t = 1   forall i,t  p
  5. At least 2 objects do not move from the left side in each time period (that is, at most 2 objects can be on the boat at the same time):

    atleast(2)  (xi,1,t = xi,1,t+1 ) forall t < T    i
  6. An object can only move with the man:

    (xi,p,t ∧  ¬xi,p,t+1)  →   (x1,p,t ∧  ¬x1,p,t+1 )  forall i > 1,p,t < T
  7. Conflicting objects can only be on one side together with the man:

    (xi,p,t ∧ xj,p,t)  →   x1,p,t   forall (i,j,p,t)|ci,j
  8. We minimize the number of objects on the left side at the last period:

       ∑ min   xi,1,T  i

Listing 1: The Complete Model implemented in LPL [2]

model alcuin1 "Wolf-Goat-Cabbage"; 
  parameter T:=8; 
  set i,j := [man wolf goat cabbage]; 
      p := [left right]; 
      t := 1..T; 
      c{i,j} := [(wolf,goat), (goat,cabbage)]; 
  binary variable  x{i,p,t}; 
  constraint 
    Start{i}: x[i,1,1] = 1; 
    Side{i,t}: sum{p} x = 1; 
    Stay{t|t<#t}: atleast(2){i}(x[i,1,t]=x[i,1,t+1]); 
    Move{i,p,t|t<#t and i>1}: (x[i,p,t] and ~x[i,p,t+1]) 
                          -> (x[1,p,t] and ~x[1,p,t+1]); 
    Conf{i,j,p,t|c}: (x[i,p,t] and x[j,p,t]) -> x[1,p,t]; 
  minimize obj: sum{i}x[i,1,#t]; 
  Write{t}('%s: %s' n',t, {i,p|x}Format('%s is %-6s',i,p)); 
end

References

[1]   MatMod. Homepage for Learning Mathematical Modeling :  https://matmod.ch.

[2]   Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.