Paths in a Grid (inter)

Run LPL Code  ,  PDF Document

Problem

This problem is similar to the problem defined in file intersec. Suppose a grid of size 8 × 8 is given and one should link corresponding grid points marked by 1, 2, 3, 4, and 5 (see Figure 1) by paths along the vertical and horizontal grid points only (diagonal links between grid points are not allowed). How can this be done? The problem is from [1].

---

---

Modeling Steps

We formulate this problem as a mathematical model.

1. We define three sets: the set of grid rows i = {1,…, 8}, a set of grid columns j = {1,…, 8}, and a set k = {1,…, 5} of paths.

2. We define a parameter a_i,j ∈{1…5} with the meaning that the grid point (i,j) is the endpoint of path p ∈{1…5} if and only if a_i,j = p (otherwise a_i,j is zero or not defined).

3. Then we specify a 0-1 variable for each combination x_k,i,j, that is x_k,i,j = 1 if the grid point (i,j) is part of path k.

4. We want to minimize the total length of all paths, that is, ∑ _k,i,jx_k,i,j should be as small as possible.

5. The variables are subjected to several constraints. First, all the grid points marked by 1, 2, 3, 4, and 5 – as specified by a_i,j – must be assigned to the correct path 1 to 5. Hence, the grid points (1, 1) (top-left) and the the grid point (4, 5) , must be assigned to the path 1, hence: x_1,1,1 = 1 and x_4,5,1 = 1. A corresponding variable fixing takes place for the endpoints of path 2 to 5. Hence:

   

6. Each endpoint of a path must have exactly one neighbor grid point in the same path. That is, if (i,j) is an endpoint of path k, then exactly one of the four following variables is true (1): x_k,i–1,j, x_k,i,j–1, x_k,i+1,j, x_k,i,j+1. That is

   

7. Furthermore, for any other grid point (which is therefore not an endpoint), if it is part of path k then it must have two neighbors in the same path k. Why? If a grid point is in path k, then it is an intermediate node of path k and has an “entering” neighbor and a “leaving” neighbor. This constraint can be formulated as an implication: if grid point (i,j) is part of path k then two neighbors must be in path k, hence:

   

8. Finally, we must make sure, that every grid point can only be part of at most one single path to avoid the path to cross each other:

   

model IntersectingLines "Paths in a Grid"; 
    set i   "A set of rows"; 
        j   "A set of columns"; 
        k   "A set of paths"; 
    parameter a{i,j} "Initial assignment"; 
    binary variable x{k,i,j} "paths points"; 
    constraint 
      I{k,i,j|a[i,j]=k}: x[k,i,j]=1; 
      N{k,i,j|a=k}: x[k,i,j+1]+x[k,i-1,j] 
                   +x[k,i,j-1]+x[k,i+1,j]=1; 
      L{k,i,j|a[i,j]<>k}: x[k,i,j] -> 
        (x[k,i,j+1]+x[k,i-1,j]+x[k,i,j-1]+x[k,i+1,j]=2); 
      E{i,j}: sum{k} x <=1; 
    minimize pathL: sum{k,i,j} x[k,i,j]; 
    Write('path length = %2d' n', pathL); 
    Draw.Scale(40,40); 
    {i} Draw.Line(1,i,#j,i,9); {j} Draw.Line(j,1,j,#i,9); 
    {i,j,k|x and x[k,i+1,j]} Draw.Line(j,i,j,i+1,0,4,2); 
    {i,j,k|x and x[k,i,j+1]} Draw.Line(j,i,j+1,i,0,4,2); 
    {i,j|~a} Draw.Circle(j,i,.04); 
    {i,j|a} Draw.Circle(a&'',j,i,.2,1,0); 
    model data "A feasible layout"; 
  /*  SetRandomSeed(7);// parameter x;y; 
      i:= [1..20]; j:=[1..15]; k:=[1..5]; 
      {n in 1..5} (a[Trunc(Rnd(1,#i+1)),Trunc(Rnd(1,#j+1))]:=n, 
                   a[Trunc(Rnd(1,#i+1)),Trunc(Rnd(1,#j+1))]:=n);  */ 
      i:= [1..8]; j:=[1..8]; k:=[1..5]; 
      a{i,j}:= [(1,1)=1 (4,5)=1  (1,3)=2 (7,5)=2, (2,5)=3 
                (6,7)=3, (3,3)=4 (3,8)=4, (6,2)=5 (4,8)=5]; 
    end 
  end

Solution

The solution delivered by the model is given in Figure 2. Note that this small model instance already consists of 320 0-1-variables and 705 linear constraints.

---

---

Further Comments

In model intersec, we applied an easy trick – topological deformation of the rubber surface – to “see” the solution immediately. Since this seems to be a similar problem, one may be tempted to apply the same idea again: “Let’s connect the corresponding endpoints by a straight line, then deform the surface”. Unfortunately, when we deform the whole surface the crossings of the lines persist – that is exactly what we would like to avoid.

However, what if we do only “deform” the lines – bend them in various directions in order to avoid crossings, In Figure 3, for example, we bend line 1 left-down to avoid crossing with 4, then we may bend line 4 to the top to avoid crossing with line 3, then we bend line 5 down-right, to avoid crossing with 3, finally, line 2 is bent from top down first to the left avoiding line 4 then to the right avoiding line 1 and again to the left avoiding line 5.

---

---

With this structural layout of the paths we may construct the grid paths, if they exist. Unfortunately, there is no solution for this layout – try it!

Let’s try another sequence of bending as shown in 4.

---

---

This time it works out, we can construct the same solution found by the mathematical model.

Questions

1. Reduce the problem to 7 rows. What is the solution?

Answers

1. The model is infeasible, because there is not enough space for the paths.

References