Using some "tactical knowledge" of the puzzle, I managed to get it to resolve
to the optimum for the given 20 people (244 minutes) by adding the following
constraints:
# slowest people cross together
s.t. slowest1{a in 1..crossings}: 2 * go[a, 20] - go[a, 19] - go[a, 18] = 0;
s.t. slowest2{a in 1..crossings}: 2 * go[a, 17] - go[a, 16] - go[a, 15] = 0;
s.t. slowest3{a in 1..crossings}: 2 * go[a, 14] - go[a, 13] - go[a, 12] = 0;
s.t. slowest4{a in 1..crossings}: 2 * go[a, 11] - go[a, 10] - go[a, 9] = 0;
# no slow returns
s.t. fastReturn{a in 1..crossings - 1}: returntime[a] <= 10;
From: [email protected]
To: [email protected]
Subject: Bridge And Torch Problem
Date: Mon, 14 Sep 2009 14:30:07 +0100
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.
_________________________________________________________________
Learn how to add other email accounts to Hotmail in 3 easy steps.
http://clk.atdmt.com/UKM/go/167688463/direct/01/_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
