My question is about an old transportation problem -- carrying three items across a river with a boat only capable of tranferring one item at a time. A constraint is certain items cannot be left together, such as the cabbage with the goat, wolf with the goat etc. This problem should be solveable using Integer programming, or another optimization approach. The cost function is all items being on the other side of the river, and the trips required to get there could be the output from Simplex (?) that tries out different feasible solutions. I was wondering if anyone has the Integer Programming (or Linear Programming) formulation of this problem, and / or Matlab, Octave, Python based code that can offer the solution programmatically, including a trace of Simplex trying out all paths -- our boat rides.
There was some interesting stuff here
http://www.zib.de/Publications/Reports/SC-95-27.pdf
Thanks,
I recommend using binary variables x_i,t to model the positions of your items, i.e. they are zero if the item is located on the left shore after trip t and one otherwise. At most one of these variables can change during a trip. This can be modeled by
x_wolf,1 + x_cabbage,1 + x_goat,1 <= 1 + x_wolf,0 + x_cabbage,0 + x_goat,0 and
x_wolf,1 >= x_wolf,0
x_cabbage,1 >= x_cabbage,0
x_goat,1 >= x_goat,0
Similar constraints are required for trips in the other direction.
Furthermore, after an odd number of trips you nedd constraints to check the items on the left shore, and similarily you have to check the right shore. For instance:
x_wolf,1 + x_goat,1 >= 0 and
x_wolf,2 + x_goat,2 <= 1 ...
Use an upper bound for t, such that a solution is surely possible.
Finally, introduce the binary variable z_t and let
z_t <= 1/3 (x_wolf,t + x_cabbage,t + x_goat,t)
and maximize sum_t (z_t).
(Most probably sum_t (x_wolf,t + x_cabbage,t + x_goat,t) shold work too.)