6
$\begingroup$

Given a n×m grid with numbered cells and forbidden cells, the objective of the Rogo puzzle is to find a loop of fixed length through the grid such that the sum of the numbers in the cells on the loop is maximized. Some cells should be avoided. ROGO Puzzle

How to add this constraint as a set of mixed integer linear constraints? We need to make sure no Banned cell (black square) is trapped in the closed route? The following red route is optimal (maxizes the total values but it contains black squares. enter image description here

Two feasible routes are shown as follows:

enter image description here

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

Introduce a dummy depot (adjacent only to the "border" cells in the first or last row or column) and send one unit of flow from the depot to each banned cell. Let nonnegative decision variable $z_{i,j}$ represent the flow along the directed arc from node $i$ to node $j$, and let binary decision variable $y_k$ indicate whether node $k$ is part of the loop. Let $B$ be the number of banned cells. To prevent trapping banned cells, you need flow balance constraints along with big-M constraint $$z_{i,j} \le B(1 - y_j) \quad \text{for all $(i,j)$},$$ which enforces $z_{i,j} > 0 \implies y_j = 0$.

For your example instance, the maximum score turns out to be $33$: enter image description here

Improve this answer
$\endgroup$
4
  • $\begingroup$ I am not sure if i was succesful in explaining the problem. Here, avoiding entering/existing the blocked cells (black squares) is easy to do The idea is to avoid creating a loop in which a black square is trapped like the foloowing one , it is not clear to me how your proposed solution avoids trapping a black square $\endgroup$
    – Optimization team
    Commented May 24, 2022 at 12:19
  • 1
    $\begingroup$ To avoid trapping a banned cell inside the loop, there must be a path from the depot (outside the loop) to the banned cell such that the path does not cross the loop. My formulation enforces such a path by sending a unit of flow from the depot to each banned cell. $\endgroup$
    – RobPratt
    Commented May 24, 2022 at 12:29
  • $\begingroup$ Great Idea. Thanks for letting me know. $\endgroup$
    – Optimization team
    Commented May 24, 2022 at 13:17
  • $\begingroup$ You could also use the parity of the number of transitions from off_path -> on_path to the left of a square to classify it as inside or outside. $\endgroup$
    – user1502040
    Commented Aug 3, 2023 at 15:26
1
$\begingroup$

Based on a hint by @robPratt the problem is solved

enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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