I have been trying to understand the mathematical solution to the Operation Research crossing the bridge puzzle. I was reading and trying to understand the solution given in the following paper
http://page.mi.fu-berlin.de/rote/Papers/pdf/Crossing+the+bridge+at+night.pdf
But I am not able to understand what's going on in the solution. Can anyone explain in more simple terms what's happening in the mathematical solution to this problem?
So given in the solution you can solve by combinatorics- rearranging & identifying the minimum time. Other than that you can use MIP (Mixed integer programming) using optimization variables like $ d_i \in Z^+$ and binary $ s_{i,j} = 1$ if set/edge $ (i,j) \in E$ is selected pair, $0$ otherwise
Setup objective as
$ \min \sum_i d_it_i + \sum_{(i,j) \in E}z_{i,j}$:
$ z$ think of like a dummy variable
$ d_it_i$: how many times does one of the entities cross the bridge (forward/backward), refer to the examples given
subject to
(1) $ d_i \ge 1 \ \ \forall i$
Or
(1.1) $\sum_j s_{i,j} \le d_i \le N-1 \ \ \forall i$
(2) $ \sum_{(i,j) \in E}s_{i,j} = N-1$
(3) $s_{i,j}t_i \le z_{i,j} \le s_{i,j}(t_i + t_j) $
(4) $ s_{i,j}t_j \le z_{i,j} \ \ \forall (i,j) \in E$
EDIT: Added another constraint 1.1 alternative to 1 as I think $d$ needs bounds and a link to set selection variable $s$