Find No-intersecting Paths (intersec)

Problem

This simple problem is from the preface written by Ian Stewart in [1]. Suppose you have to solve the following problem. Connect the small square A with F, then B with D, and finally C with E within the rectangle by lines inside the plane of Figure 1 in such a way that they do not intersect (cross).

Figure 1: The Intersection Problem

At first glance, it seems that the problem is unsolvable, because if we connect A with F by a straight line, it partitions the rectangle into two parts, where B and C are in one side and D and E in the other. There is no way then to connect B with D and C with E, without intersecting the line between A and F. Well, we were not asked to connect A and F with a straight line. So let us connect A with F by a curved line passing between say, B and C. But, then again we have the same problem. The rectangle is partitioned into two parts, B being isolated. The same problem arises when the line from A to F is drawn between D and E. However, the problem can be presented a little bit differently: Imagine that the rectangles surface is built of elastic materials. So pick D and C and distort the rubber in a continuous way such that the places of C and D are interchanged (see Figure 2).

Figure 2: Topological Deformation

Now the problem is easily solvable. Connect the squares as prescribed by straight lines. After this operation, return the rubber to the initial state again and we get Figure 3.

Figure 3: A Solution of the Intersection Problem (I)

The solution is now so obvious that we can immediately see it. The problem is a nice exercise in topology.

As an exercise, suppose now that the problem is to be formulated as a mathematical model.

Modeling Steps

How could this innocent looking problem be formulated as a mathematical model? First, we subdivide the rectangle into a grid of 7x7 squared cells, the squares A, B, C, D, E, and F being six of them. Where does the 7 come from? Well, it is an arbitrary number, and could be bigger but not smaller (see below). (We will see that if it is smaller, the corresponding mathematical model cannot be solved, because there would be no solution. If it is bigger the model could not be solved, because the problem is too difficult.)

To express the fact that each of the six square has to be connected to another one, the six characters are assigned to numbers 1, 2, and 3, defining which belong together – 1 is assigned to cell A and F, 2 is assigned to B and D, and 3 is assigned to cells C and E. (We might also imagine that these three numbers represent three different colors, defining the three lines colored differently.)
We introduce two definitions. A path between two squares, say A and F, is defined as a sequence of squares (cells) < s₁,s₂,…,s_i,s_i+1 > in such a way that s_i and s_i+1 are neighbors for all i ∈{1…n - 1}. Two squares are neighbors, if and only if they have a side or a corner in common.
Using these two definitions of path and neighbors, the intersection problem can be formulated as follows: Find three paths – each path consisting of cells with the same number (color) assigned – in such a way that the paths do not cross each other. They cross each other if the same square is used by at least two paths, or if two paths cross at a corner, i.e. if two diagonal neighbors have the same number (color) and the two other diagonal neighbors have both another number (color).
Now, we introduce a binary variable x_k,i,j which is 1 if the grid square (i,j) has color k otherwise it is 0. Five constraints are sufficient to formulate the problem.
The first constraint is to fix the six variables corresponding to the initial assignment to one (the paths begins at these points). (for example x_1,3,1 = 1 – meaning that the grid point (3, 1) has color 1).
If a path begins (or ends) at a square, then it must have exactly one neighbor of the same color. That is:
$x + x + x + x + x + x k,i,j+1 k,i- 1,j+1 k,i-1,j k,i-1,j-1 k,i,j- 1 k,i+1,j-1 +xk,i+1,j + xk,i+1,j+1 = 1 forall k, (i,j)|ai,j = k$
If a square (other then specified just before) belongs to a path, then it must have exactly two neighbors with the same color. Hence:
$xk,i,j → (xk,i,j+1 + xk,i-1,j+1 + xk,i-1,j + xk,i-1,j-1 + xk,i,j- 1 + xk,i+1,j-1 +xk,i+1,j + xk,i+1,j+1 = 2) forall k, (i,j)|ai,j ⁄= k$
A square can only belong to at most one path. That is
$∑ x ≤ 1 forall (i,j) k,i,j k$
Two paths must not cross at a corner:
$xk1,i,j ∧ xk1,i+1,j+1 ∧ xk2,i+1,j → ¬xk2,i,j+1 forall (i,j), i < #i, j < #j, k1, k2 ∈ k, k1 ⁄= k2$
The goal is to find a solution where the total length of all paths is as small as possible, that is :
$∑ min xk,i,j k,i,j$

Listing 1: The Complete Model implemented in LPL [3]

model intersec "Find No-intersecting Paths"; 
 
  set i,j     := [1..7]  "A set of columns and rows"; 
 
      k,k1,k2 := [1..3]  "Three colors (paths)"; 
 
  parameter a{i,j} "Initial assignment of colors" 
 
     := [(1,4)=1, (7,4)=1, (4,1)=2, (4,5)=2, 
 
         (4,3)=3, (4,7)=3]; 
 
  binary variable x{k,i,j}; 
 
  constraint 
 
    I{k,i,j|a=k}: x[k,i,j]=1; 
 
    N{k,i,j|a=k}: x[k,i,j+1]+x[k,i-1,j+1]+x[k,i-1,j] 
 
       +x[k,i-1,j-1]+x[k,i,j-1]+x[k,i+1,j-1] 
 
       +x[k,i+1,j]+x[k,i+1,j+1] = 1; 
 
    NN{k,i,j|a[i,j]<>k}: x[k,i,j] ->( x[k,i,j+1] 
 
      +x[k,i-1,j+1]+x[k,i-1,j]+x[k,i-1,j-1]+x[k,i,j-1] 
 
      +x[k,i+1,j-1]+x[k,i+1,j]+x[k,i+1,j+1] = 2); 
 
    E{i,j}: atmost(1){k} x[k,i,j]; 
 
    K{i,j,k1,k2|k1<>k2 and i<#i and j<#j}: 
 
      x[k1,i,j] and x[k1,i+1,j+1] and x[k2,i+1,j] 
 
        -> ~x[k2,i,j+1]; 
 
  minimize pathL: sum{k,i,j} x[k,i,j]; 
 
  Write('path length = %2d' n %3s  ' n', pathL, {i}i); 
 
  Write{i}(' %s %s  ' n', i, {j} if (x[1,i,j],'x  ', 
 
             x[2,i,j],'*  ',x[3,i,j],'+  ','   ')); 
 
  Draw.Scale(30,30); 
 
  {i,j,k} Draw.Rect(if(x,k&''),j,i,1,1,if(x,k+6,-1)); 
 
end

Solution

The optimal solution is (with the total path length = 21):

       1  2  3  4  5  6  7 
     1          x 
     2       *     x 
     3    *  x  *     x 
     4 *  x  +  x  *  x  + 
     5    x     +  x  + 
     6       x     + 
     7          x

The characters ’x’ depict the path from A to F, ’*’ gives the path from B to D, and ’+’ gives the path from C to E.

This output corresponds to the solution in Figure 4, where the three paths are shown in three different colors and digits.

Figure 4: A Solution to the Intersection Problem (II)

Further Comments

A note of caution: The mathematical model given for this problem is a nice exercise in modeling – translating a well defined problem into the language of mathematics. However, not every well stated problem needs to be translated into a model. First, it may not be solvable by any known method in reasonable time (around 1995, when this model was formulated, the best MIP solvers had difficulties to solve this small model). Second, another method may be more appropriate to solve the problem as has been shown: The problem is a nice exercise in topology and once the “rubber deformation” analogy has been seen, maybe topology would be more suitable to explore the properties of this problem.

The focus of this text is mathematical modeling, and since we “have this powerful hammer, its tempting to treat everything as a nail”, to paraphrase a proverb from Abraham H. Maslow (1962). However, be aware that sometimes various methods exist to attack a problem, and to have an open mind in all respects is part of the creative process of problem solving.

Questions

The problem was discretized into a grid of 7 × 7 small squares. Looking at the solution, can you see why this dimension was chosen?

Answers

It is the smallest possible grid for which the problem is still solvable. In a smaller grid, there would not be enough space for the paths. On the other hand, the larger the grid the larger the model in terms of variables and constraints.

References

[1] Polya G. Mathematical Discovery I. John Wiley, 1954.

[2] MatMod. Homepage for Learning Mathematical Modeling : https://matmod.ch.

[3] Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.