MatMod logo

Wolf-Goat-Cabbage (alcuin)

Run LPL Code  ,  PDF Document

Problem

“A man had to take a wolf, a goat and a bunch of cabbages across the river. The only boat he could find can only take the man and of them at a time. But he had been ordered to transfer all of these to the other side in good condition. How could this be done?”

Some historical notes of this problem and similar problems have been given in [1]. The paper is also a very comprehensive summary of the mixed integer approach of such combinatorial problems, explaining the fundamental concepts of problem space translated into linear equations and inequalities, its lp-relaxation and the generation of cuts using this problem.

Modeling Steps

Of course a little thinking shows you that the solution is obvious: The man must transport the goat first, then the cabbage, but takes the goat back, leaves the goat on the left bank and takes the wolf. Finally, he picks up the goat. Hence, to solve the problem we do not need any Mathematics. However, the formulation as a mathematical model is a interesting exercise.

The mathematical formulation here is from the mentioned paper [1]. We introduce a sequence of states at different time points t ∈{0,,T}, reflecting the different journey over the river. Initially, at time point 0, the man and all objects are on the left bank of the river. Every odd time point represents a journey for the left to the right bank, and every even time point represents a journey back for the right to the left bank. The set of the objects to be transported is: i ∈{wolf, goat, cabbage}.

  1. At each time point, we want to specify where the objects are: on the left (initial) river bank, on the river, or on the right bank.

  2. We define three binary variables to this end: xt,i = 1 and zt,i = 1, if object i is on the left/right bank after the t-th-shipment has been completed. yt,i = 1 records the boat configuration at the t-shipment.

  3. Initially (t = 0) all i are on the left bank:

    x   =  1 , y  = 0 , z  =  0 ,   forall i   0,i    0,i  0,i
  4. The final state (at t = T), all objects must be on the right bank:

    zT,i = 1 ,   forall i
  5. The state transitions at even time points t (left-to-right shipments) are given by the two constraints:

    xt+1,i = xt,i - yt+1,i , zt+1,i = zt,i + yt+1,i
  6. The state transitions at odd time points t(right-to-left shipments) are given by:

    xt+1,i = xt,i + yt+1,i , zt+1,i = zt,i - yt+1,i
  7. (For example, consider the first shipment for the goat: at t = 0 the goat is on the left bank, at t = 1 it is on the boat and then at the right side, hence we have: x0,2 = 1,y1,2 = 1,z1,2 = 1. If the goat were not transported at t = 0, we had: x0,2 = 1,y1,2 = 0,z1,2 = 0. In both cases the equations hold.)

  8. We also require that only one object can be transported at the same time:

    ∑  y  ≤  1   forall t   t,i   i
  9. Wolf and goat, as well as goat and cabbage cannot be together on the left bank at any odd time:

    xt,1 + xt,2 ≤ 1 ,  xt,2 + xt,3 ≤ 1 ,   forall tisodd
  10. Wolf and goat, as well as goat and cabbage cannot be together on the right bank at any even time:

    - z  +  z  + z   ≤ 1  ,  z  + z   - z   ≤ 1 ,   forall tiseven t,1 t,2   t,3    t,1   t,2 t,3
  11. The goal is to remove all items from the left bank as soon as possible:

       ∑ min   xt,i  t,i
  12. How many shipments are there maximally? Note that in all time points t > 0 we have at most 5 configurations on the left bank (each item alone, wolf together with the cabbage, or none). Furthermore, if the same configuration occurs in two time points s > t then all shipments between t and s can be removed. That means there are at most 5 left-to-right shipments, and hence T = 2 5 1 shipments (or time points) in total.

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

model alcuin "Wolf-Goat-Cabbage"; 
  parameter T:=9; 
  set  t := 0..T    "time slots"; 
       i := [WOLF GOAT CABBAGE]; 
  parameter 
    odd{t} :=t%2=1 and t<T; 
    even{t}:=t%2=0 and t<T; 
  binary variable 
    x{t,i}  "At time t object i is on the left bank"; 
    y{t,i}  "At time t object i is on the river"; 
    z{t,i}  "At time t object i is on the right bank"; 
  constraint 
    Start{i}: x[0,i] and ~y[0,i] and ~z[0,i]; 
    End{i}  : z[T,i]; 
    A1{t,i|even}: x[t+1,i] = x[t,i]-y[t+1,i]; 
    A2{t,i|even}: z[t+1,i] = z[t,i]+y[t+1,i]; 
    B1{t,i|odd}: x[t+1,i] = x[t,i]+y[t+1,i]; 
    B2{t,i|odd}: z[t+1,i] = z[t,i]-y[t+1,i]; 
    OneOnBoat{t}: sum{i} y <= 1; 
    C1{t|odd}: x[t,1]+x[t,2] <= 1; 
    C2{t|odd}: x[t,2]+x[t,3] <= 1; 
    D1{t|even}: -z[t,1]+z[t,2]+z[t,3] <= 1; 
    D2{t|even}:  z[t,1]+z[t,2]-z[t,3] <= 1; 
  minimize obj: sum{t,i} x; 
  Write('time trip left boat right' n'); 
  Write{t}( 
    't=%2d: %s(%s) (%s) (%s) ' n', 
    t, if(t%2=0,'left ','right '), 
    ({i} Format('%d',x[t,i])), 
    ({i} Format('%d',y[t,i])), 
    ({i} Format('%d',z[t,i])) ); 
end

A different formulation of this problem with different state spaces is given by model alcuin1.

Solution

The solution – here displayed as a list of 0-1 states – reflects the solution found manually:

     time  trip  left   boat right       -----------------------------       t=0: left  (111) (000) (000)       t=1: right (101) (010) (010)       t=2: left  (101) (000) (010)       t=3: right (001) (100) (110)       t=4: left  (011) (010) (100)       t=5: right (010) (001) (101)       t=6: left  (010) (000) (101)       t=7: right (000) (010) (111)       t=8: left  (000) (000) (111)       t=9: right (000) (000) (111)

Further Comments

The Wolf-Goat-Cabbage river crossing problem is an instructive modelling example. However, the problem itself could be treated by constructing a simple graph and so the structure of the problem becomes evident. Let us define all states as a node in a graph. A state is defined by the location of the three objects: wolf, goat, and cabbage. If an object is on the left side of the river, this is marked by an L, if it is on the right side we mark it as R. Hence, a state can be defined as a triple of these letters: for example the initial state, where all three are on the left side, can be noted as LLL. The final state then is RRR, where all three are on the right hand side of the river. Since a state consists of three letters where each letter can be L or R, there are 8 states (23).

The edges of the graph are the possible transitions from one state to another. The rule of the game says that only a single object can cross the river at the same time. Its easy to see that this produced a cube (see Figure 1, on the left). A second rule says that “Wolf-Goat” as well as “Goat-Cabbage” cannot be left together on either side of the river. This means that some edges cannot be traveled, for example, the transition LLL to RLL (where the wolf travels with the man) is not possible. It follows that certain edges in the graph can be removed altogether, which would generated the graph in Figure 1 on the right.


PIC

Figure 1: The Transition Graph of the River Crossing Puzzle


Now it becomes crystal clear how to reach the goal (RRR)) from the initial state (LLL). There are exactly two shortest paths!

Questions

  1. Generalize the problem! Suppose there are not three objects but n > 3 to be moved the the other side of the river. And an arbitrary subset are in conflict (can “eat” each-other).

Answers

  1. Build a graph with the objects as nodes and the conflicts as edges. For a feasible transportation we need a boat that can transport at least ϕ objects where ϕ is the “Alcuin number of the graph” (ϕ is either the vertex covering number or the vertex covering number plus one of the graph. see [2]. A nice video is available at The Alcuin Number of a Graph explaining the problem.

References

[1]   R. Borndoerfer, M. Groetschel, and A. Loebel. Alcuin’s Transportation Problem and Integer Programming. Konrad Zuse Zentrum for Informationstechnik, Berlin, 1995.

[2]   Woeginger G.J Csorba P., Hurkens A.J. The Alcuin Number of a Graph. Algorithms – ESA 2008 Proceedings, in: Lecture Notes in Computer Science, LNCS, Vol 5193, pp. 320–331, 2008.

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

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