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.
_________________________________________________________________
Use Hotmail to send and receive mail from your different email accounts.
http://clk.atdmt.com/UKM/go/167688463/direct/01/_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
