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 &lt;= 2 // i-th sail can contain max 2 people
x_im + x_in &lt;= 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.
The river crossing problem using integer programming is solved by Börndorfer et al. in [1].



[1] Borndörfer, Ralf, Martin Grötschel, and Andreas Löbel. Alcuin's transportation problems and integer programming. ZIB, 1995.