3
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Gaste Mar 3 '14 at 15:06
  • $\begingroup$ @Gaste Turn into an answer? You could add a few more details. $\endgroup$ – Yuval Filmus Mar 3 '14 at 18:47
  • $\begingroup$ Yeah, I would accept it :-) I did not know that this riddle has its own name :-) $\endgroup$ – Smajl Mar 3 '14 at 20:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael♦ Jun 29 '15 at 12:36
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This was posted as an answer from the comments to the original question. It would be appreciated if someone at some point would add a few more details. $\endgroup$ – Juho Jun 29 '15 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.