0

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?

Akansha Banerjee
  • 31
  • 5

1 Answers1

0

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$

Sutanu Majumdar
  • 458