# Boat riddle as a combinatorial optimization problem?

I remember a riddle about a bunch of people on a river bank, and a boat with limited capacity (lets say the boat can transport 2 people at a time). There are various relations between the people like: person $x_m$ and $x_n$ cannot sail together and cannot even stay on the same bank of the river or $x_m$ and $x_n$ always have to be together.

When I remembered this riddle, I thought whether it could be represented as an optimization problem. The criterial function would be $\min(\text{numberOfSails})$ and the conditions will be my limitations, but I am not sure whether I can model my problem like this (and I am not sure how to model all my conditions).

Could you tell me or give me a hint, how such an approach for modelling this program would look like?

At first I thought it could look something like this:

min i // i = number of sails
x_i1 + ... + x_i2 <= 2 // i-th sail can contain max 2 people
x_im + x_in <= 1 // x_m and x_n cant sail together
etc.

But there is so much wrong with this model (like considering the people left on the first bank or the people already transported) and so on, so I am not sure how to tackle this problem.

• There is a nice paper: Alcuin's Transportation Problems and Integer Programing by Börndorfer et al., that solves the river crossing problem using integer programming. – Gaste Mar 3 '14 at 15:06
• @Gaste Turn into an answer? You could add a few more details. – Yuval Filmus Mar 3 '14 at 18:47
• Yeah, I would accept it :-) I did not know that this riddle has its own name :-) – Smajl Mar 3 '14 at 20:16
• You can model the state space (who is on which side) as graph and connect two states with (directed) edges iff you can get from one to the other with one trip. Remove all states and transitions that are illegal. Find a (shortest) path from start to end state in the graph. – Raphael Jun 29 '15 at 12:36