[Help-glpk] Bridge And Torch Problem

[Tawny Owl]

The Bridge And Torch problem is described in full, with an example, at http://en.wikipedia.org/wiki/Bridge_and_torch_problem . The problem shown there, with 4 people who take 1, 2, 5 and 8 minutes, and who may cross two at a time, is solved almost instantaneously by the model below:

# bridge crossing
# move pieces from right to left, 1 must return.
param pieces;
param speeds {x in 1..pieces};
param maxcross;
param crossings:= ceil((pieces - 1) / (maxcross - 1));

var left {a in 1..crossings, b in 1..2, c in 1..pieces} >=0, <=1;
var right {a in 1..crossings, b in 1..2, c in 1..pieces} >=0, <=1;
var go {a in 1..crossings, b in 1..pieces} binary;
var return {a in 1..crossings - 1, b in 1..pieces} binary;
var crosstime {a in 1..crossings};
var returntime {a in 1..crossings - 1};

minimize objectiveFn: sum{a in 1..crossings}crosstime[a] + sum{b in 1..crossings - 1}returntime[b];

# initialise position
s.t. startLeft{c in 1..pieces}: left[1, 1, c] = 1;
s.t. startRight{c in 1..pieces}: right[1, 1, c] = 0;

# number of pieces that cross
s.t. restrictCross{a in 1..crossings - 1}: sum{b in 1..pieces} go[a, b] = maxcross;
s.t. finalcross: sum{a in 1..pieces} go[crossings, a] = sum{b in 1..pieces} left[crossings, 1, b];
s.t. restrictReturn{a in 1..crossings - 1}: sum{b in 1..pieces} return[a, b] = 1;

# move pieces that cross
s.t. crossMoveLeft{a in 1..crossings, b in 1..pieces}: left[a, 2, b] = left[a, 1, b] - go[a, b];
s.t. crossMoveRight{a in 1..crossings, b in 1..pieces}: right[a, 2, b] = right[a, 1, b] + go[a, b];
s.t. returnMoveLeft{a in 1..crossings - 1, b in 1..pieces}: left[a + 1, 1, b] = left[a, 2, b] + return[a, b];
s.t. returnMoveRight{a in 1..crossings - 1, b in 1..pieces}: right[a + 1, 1, b] = right[a, 2, b] - return[a, b];

# crossing times
s.t. crossingTimes{a in 1..crossings, b in 1..pieces}: crosstime[a] >= speeds[b] * go[a, b];
s.t. returnTimes{a in 1..crossings - 1, b in 1..pieces}: returntime[a] >= speeds[b] * return[a, b];

solve;

printf "*** Objective function ***\n\n%s", sum{a in 1..crossings}crosstime[a] + sum{b in 1..crossings - 1}returntime[b];

printf "\n\n*** Crossings ***";
for {a in 1..crossings}{
  printf "\n\nLeft bank:";
  for {c in 1..pieces: left[a, 1, c] > 0.5} {
    printf " %s", speeds[c];
  }
  printf "\nRight bank:";
  for {c in 1..pieces: right[a, 1, c] > 0.5} {
    printf " %s", speeds[c];
  }
  printf "\n";
  printf "\nCrossing %s:", a;
  for {b in 1..pieces: go[a, b] > 0.5}{
    printf " %s", speeds[b];
  }
  printf "\n\nLeft bank:";
  for {c in 1..pieces: left[a, 2, c] > 0.5} {
    printf " %s", speeds[c];
  }
  printf "\nRight bank:";
  for {c in 1..pieces: right[a, 2, c] > 0.5} {
    printf " %s", speeds[c];
  }
  for {d in 1..1: a < crossings} {
    printf "\n\nReturns %s:", a;
    for {b in 1..pieces: a < crossings and return[a, b] > 0.5}{
      printf " % s", speeds[b];
    }
  }
}
printf "\n\n";

data;

param pieces:= 4;
param speeds := [1] 1 [2] 2 [3] 5 [4] 8;
param maxcross := 2;

end;


If the number of pieces (people) to cross is increased to 10, and the number allowed to cross at one time is increased to 3, then GLPSOL resolves it in around a minute (longer if cuts are used). Replace the data section above with the following:

param pieces:= 10;
param speeds := [1] 1 [2] 4 [3] 6 [4] 7 [5] 10 [6] 12 [7] 14 [8] 15 [9] 20 [10] 23;
param maxcross := 3;

However - when the number of people is increased to 20, GLPSOL is no longer able to resolve the above model to the optimum:

param pieces:= 20;
param speeds := [1] 1 [2] 4 [3] 6 [4] 7 [5] 10 [6] 12 [7] 14 [8] 15 [9] 20 [10] 23 [11] 30 [12] 35 [13] 35 [14] 39 [15] 41 [16] 41 [17] 45 [18] 50 [19] 53 [20] 57;
param maxcross := 3;

I wasn't expecting this, because according to the academic paper at http://www.zib.de/Publications/Reports/SC-95-27.ps.Z (from Konrad-Zuse-Zentrum für Informationstechnik Berlin), river crossing problems can be resolved using integer programming with planar cuts. Would I be correct in thinking that to achieve the level of results described in that paper, one would have to program the planar cuts explicitly for this problem, rather than use the generalised cuts provided with GLPK, or is there something I can do to make the model resolve more quickly?

Thanks for any responses.

---

Add other email accounts to Hotmail in 3 easy steps. Find out how.