[ Post a Response | Puzzles Forum ]
Posted by Moby Dick
on 14/9/2009, 9:14 pm, in reply to "Re: The Passageway"
Good question - and well found on the web! 
I am going to say 310. Here's my model, in GNU MathProg (the part in bold is added both to help it and to ensure that the two 30s do not have to cross together):
# move pieces from left to right, 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];
# slowest people cross together + prevent fighting thirties
s.t. slowest1{a in 1..crossings}: go[a, 11] - go[a, 10] = 0;
s.t. slowest2{a in 1..crossings}: go[a, 9] - go[a, 8] = 0;
s.t. slowest3{a in 1..crossings}: go[a, 7] - go[a, 6] = 0;
# no slow returns
s.t. fastReturn{a in 1..crossings - 1}: returntime[a] <= 15;
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:= 11;
param speeds := [1] 5 [2] 10 [3] 15 [4] 20 [5] 30 [6] 30 [7] 35 [8] 45 [9] 50 [10] 55 [11] 65;
param maxcross := 2;
end;
Output
*** Objective function ***
310.000000000003
*** Crossings ***
Left bank: 5 10 15 20 30 30 35 45 50 55 65
Right bank:
Crossing 1: 5 10
Left bank: 15 20 30 30 35 45 50 55 65
Right bank: 5 10
Returns 1: 5
Left bank: 5 15 20 30 30 35 45 50 55 65
Right bank: 10
Crossing 2: 55 65
Left bank: 5 15 20 30 30 35 45 50
Right bank: 10 55 65
Returns 2: 10
Left bank: 5 10 15 20 30 30 35 45 50
Right bank: 55 65
Crossing 3: 5 10
Left bank: 15 20 30 30 35 45 50
Right bank: 5 10 55 65
Returns 3: 5
Left bank: 5 15 20 30 30 35 45 50
Right bank: 10 55 65
Crossing 4: 30 35
Left bank: 5 15 20 30 45 50
Right bank: 10 30 35 55 65
Returns 4: 10
Left bank: 5 10 15 20 30 45 50
Right bank: 30 35 55 65
Crossing 5: 5 10
Left bank: 15 20 30 45 50
Right bank: 5 10 30 35 55 65
Returns 5: 5
Left bank: 5 15 20 30 45 50
Right bank: 10 30 35 55 65
Crossing 6: 45 50
Left bank: 5 15 20 30
Right bank: 10 30 35 45 50 55 65
Returns 6: 10
Left bank: 5 10 15 20 30
Right bank: 30 35 45 50 55 65
Crossing 7: 5 10
Left bank: 15 20 30
Right bank: 5 10 30 35 45 50 55 65
Returns 7: 5
Left bank: 5 15 20 30
Right bank: 10 30 35 45 50 55 65
Crossing 8: 20 30
Left bank: 5 15
Right bank: 10 20 30 30 35 45 50 55 65
Returns 8: 10
Left bank: 5 10 15
Right bank: 20 30 30 35 45 50 55 65
Crossing 9: 5 10
Left bank: 15
Right bank: 5 10 20 30 30 35 45 50 55 65
Returns 9: 5
Left bank: 5 15
Right bank: 10 20 30 30 35 45 50 55 65
Crossing 10: 5 15
Left bank:
Right bank: 5 10 15 20 30 30 35 45 50 55 65
Model has been successfully processed
Message Thread:
« Back to thread