
From:  Tawny Owl 
Subject:  [Helpglpk] FW: Bridge And Torch Problem 
Date:  Tue, 15 Sep 2009 06:41:47 +0100 
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: address@hidden To: address@hidden 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/SC9527.ps.Z (from KonradZuseZentrum 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. New! Receive and respond to mail from other email accounts from within Hotmail Find out how. 
[Prev in Thread]  Current Thread  [Next in Thread] 