Solving LinkedIn Zip by Linear Optimization

How to Play Zip¶

The Zip game board consists of a grid with some numbered squares. Both the grid’s dimensions and the total of numbered squares can vary from game to game. The objective is to trace a path that runs through all the squares on the board, moving through numbered squares in ascending order, starting from square number 1 to the one with the highest number.

Problem Modeling¶

The best way I thought of to solve the game is to consider the squares as nodes in a directed graph (digraph), where each node has a set of pairs of edges that arrive at and depart from the nodes, as shown in the following figure.

Considering this model, enacted the Abstract LO Model by defining its following components:

• Ranges

• Sets

• Decision Variables

• Parameter

• Objective Function

• Constraints

Ranges¶

To properly formulate the LO model, we will start from the premise that the squares on the board will be the Cartesian product of the ranges $I$ of rows and $J$ of columns present on the board. In addition, it is necessary to have defined an interval $K$ for the set of numbered squares.

$I = \{1, \cdots, n\}$

The row range, where $n$ is the total number of rows (in this case, $n = 6$)

$J = \{1, \cdots, m\}$

The column range, where $m$ is the total number of columns (in this case, $m = 6$ as well).

Sets¶

This time, the definition of sets will be more than fundamental to reducing the complexity of the model, as we will avoid having to deal with numerous exceptions. From the ranges determined previously, we can define the set of vertices ($V$) and edges ($E$) existing in the network logic. In addition to these, it is also necessary to consider the subsets of numbered vertices ($N$) and blocked edges ($W$), since, in some instances of Zip game, there may be walls between two squares that prevent the path from being traced between them.

$V = \{(i,j) \mid \forall i \in I, \forall j \in J \}$

Set of all squares (vertices). There must be at least 2 vertices in the grid, as it is only possible to trace a path with an initial and a final square. Therefore, $|V| \ge 2$

$E = \begin{array}{lr} \{((i,j), (i+1,j)) \mid (i,j) \in V, i + 1 \in I \} & \cup \\ \{((i,j), (i-1,j)) \mid (i,j) \in V, i - 1 \in I \} & \cup \\ \{((i,j), (i,j+1)) \mid (i,j) \in V, j + 1 \in J \} & \cup \\ \{((i,j), (i,j-1)) \mid (i,j) \in V, j - 1 \in J \} & \end{array}$

Set of all edges present in the graph. Its definition is a bit more complex as it is necessary to clarify that, for each vertex, there will only be edges between neighbors immediately to the left, immediately to the right, immediately above, and immediately below it, if they exist.

$K \subseteq V$

Set of numbered squares, which will consist of a set of all vertices indexed by a number on board game.

$W \subset E$

Set of blocked edges (walls) that may appear on the grid.

Decision Variables¶

By using the network logic already presented, it is possible to define the edges as binary decision variables $x_{ijrs}$, which again makes our LOP a BLOP. In addition to $x_{ijrs}$, variables $u_{ij}$ will also be considered, representing the absolute ordinal position of the square $(i,j)$ within the path (these variables will be better explained later).

$x_{ijrs} \in \{0,1\}$

$x_{ijrs}=1$, if the edge that starts from square $(i,j)$ and arrives at square $(r,s)$ is part of the path

$x_{ijrs}=0$, otherwise

$u_{ij} \in \mathbb{N}$

Absolute ordinal positions of the squares $(i,j)$ within the path.

Parameters¶

$k_{ij} \in \{1, \cdots, |K|\}, \forall (i,j) \in K$

For each numbered board square in $K$ set, it’ll be defined a integer $k_{ij}$ that matches its number displayed on game board.

Objective Function¶

Once again, just as in the Queens and Tango games, our problem does not have a function to be optimized, since we only want to find a solution that fulfills all the rules of the game. Therefore, Zip’s BLOP is a feasibility problem, and the objective function of the model consists of maximizing (or minimizing) an arbitrary constant.

Constraints¶

Decision variables domain constraints

First, let’s not forget to define our variables $x_{ijrs}$ as binary and the variables $u_{ij}$ as non-negative real numbers. To simplify, whenever possible, we can replace the notation $x_{ijrs}$ with $x_{vw}$ and $u_{ij}$ with just $u_v$, since the sequence $(i,j) = v$ always refers to some vertex belonging to $V$ set.

$$\begin{array}{} x_{v,w} \in \{0,1\}, \forall (v,w) \in E \\ u_v \ge 0, \forall v \in V \end{array}$$

(2)

Blocked edges constraints

If there is a wall between a pair of squares, then the sum of the edges connecting those ones must be equal to 0.

$$x_{v,w} + x_{w,v} = 0, \forall (v,w) \in W$$

(3)

Continuity constraints

Since it is only possible to enter and exit a node once (except for the initial and destination nodes), then we will have the following:

Outgoing-Edges Constraints

The sum of the edges emanating from a node must equal 1 (except for the destination square).

$$\sum_{w \in V}{x_{vw}} = 1, \forall v \in V \backslash \{v:k_v=|K|\}: (v,w) \in E$$

(4)

Incoming-Edges Constraints

The sum of the edges arriving at a node must equal 1 (except for the initial square).

$$\sum_{v \in V}{x_{vw}} = 1, \forall w \in V \backslash \{w:k_w=1\}: (v,w) \in E$$

(5)

Arrival Square Constraint

The sum of the edges emanating from the destination node must be 0.

$$\sum_{w \in V}{x_{vw}} = 0, (v,w) \in E, k_v = |K|$$

(6)

Starting Square Constraint

The sum of the edges arriving at the initial node must be 0.

$$\sum_{v \in V}{x_{vw}} = 0, (v,w) \in E, k_w = 1$$

(7)

Subroute Elimination Constraints

The advantage of the MTZ formulation is that the number of constraints to be included to guarantee subroute elimination is equal to $|E| = 4nm - 2n - 2m$, that is, the number of edges in the graph. Thus, the number of constraints grows linearly as a function of the number of edges, instead of exponentially as a function of the number of vertices. For it to work, it requires the addition of more decision variables (the previously mentioned $u_{ij}$), which represent the absolute ordinal position of square $(i,j)$ within the path.

Position of Starting Square Constraint

First, the position of the starting square must be equal to 1, since it will always be the first position on the path.

$$u_v = 1: k_v = 1$$

(8)

MTZ Constraints

Then, the positions of the remaining squares on the board should be given as follows.

$$u_w \ge u_v + 1 - M(1 - x_{vw}), \forall (v,w) \in E: w \in V \backslash \{w:k_w=1\}$$

(9)

Positon of Arrival Square Constraint

Although not necessary, one can restrict the position of the arrival square to be equal to the number of squares on the board, just to make the $u_v$ range from 1 to 36.

$$u_v = |V|: k_v = |K|$$

(10)

Order of Precedence Constraints

In order for the path to traverse the numbered squares in ascending numerical order, it is necessary to impose the constraint that the position of a numbered square $i$ must be at least equal to the position subsequent to the last numbered square.

$$u_v \ge u_w + 1, \forall v, w \in K : k_v = k_w + 1$$

(11)

Abstract Model¶

With all the formulas elaborated, we have the complete abstract model for the Zip minigame.

Concrete Model¶

The game selected to be solved is the Zip No. 166, published on LinkedIn on August 29^th, 2025

Based on this specific case, we have the following concrete model:

S.t.:

Outgoing edges constraints

$x_{1112} + x_{1121} = 1$ _{(Square (1,1))}

$x_{1211} + x_{1222} + x_{1213} = 1$ _{(Square (1,2))}

$x_{1312} + x_{1323} + x_{1314} = 1$ _{(Square (1,3))}

$x_{1413} + x_{1424} + x_{1415} = 1$ _{(Square (1,4))}

$x_{1514} + x_{1525} + x_{1516} = 1$ _{(Square (1,5))}

$x_{1615} + x_{1626} = 1$ _{(Square (1,6))}

$x_{2111} + x_{2122} + x_{2131} = 1$ _{(Square (2,1))}

$x_{2212} + x_{2221} + x_{2223} + x_{2232} = 1$ _{(Square (2,2))}

$x_{2313} + x_{2322} + x_{2324} + x_{2333} = 1$ _{(Square (2,3))}

$x_{2414} + x_{2423} + x_{2425} + x_{2434} = 1$ _{(Square (2,4))}

$x_{2515} + x_{2524} + x_{2526} + x_{2535} = 1$ _{(Square (2,5))}

$x_{2616} + x_{2625} + x_{2636} = 1$ _{(Square (2,6))}

$x_{3121} + x_{3132} + x_{3141} = 1$ _{(Square (3,1))}

$x_{3222} + x_{3231} + x_{3233} + x_{3242} = 1$ _{(Square (3,2))}

$x_{3323} + x_{3332} + x_{3334} + x_{3343} = 1$ _{(Square (3,3))}

$x_{3424} + x_{3433} + x_{3435} + x_{3444} = 1$ _{(Square (3,4))}

$x_{3525} + x_{3534} + x_{3536} + x_{3545} = 1$ _{(Square (3,5))}

$x_{3626} + x_{3635} + x_{3646} = 1$ _{(Square (3,6))}

$x_{4131} + x_{4142} + x_{4151} = 1$ _{(Square (4,1))}

$x_{4232} + x_{4241} + x_{4243} + x_{4252} = 1$ _{(Square (4,2))}

$x_{4333} + x_{4342} + x_{4344} + x_{4353} = 1$ _{(Square (4,3))}

$x_{4434} + x_{4443} + x_{4445} + x_{4454} = 1$ _{(Square (4,4))}

$x_{4535} + x_{4544} + x_{4546} + x_{4555} = 1$ _{(Square (4,5))}

$x_{4636} + x_{4645} + x_{4656} = 0$ _{(Square (4,6))}

$x_{5141} + x_{5152} + x_{5161} = 1$ _{(Square (5,1))}

$x_{5242} + x_{5251} + x_{5253} + x_{5262} = 1$ _{(Square (5,2))}

$x_{5343} + x_{5352} + x_{5354} + x_{5363} = 1$ _{(Square (5,3))}

$x_{5444} + x_{5453} + x_{5455} + x_{5464} = 1$ _{(Square (5,4))}

$x_{5545} + x_{5554} + x_{5556} + x_{5565} = 1$ _{(Square (5,5))}

$x_{5646} + x_{5655} + x_{5666} = 1$ _{(Square (5,6))}

$x_{6151} + x_{6162} = 1$ _{(Square (6,1))}

$x_{6252} + x_{6261} + x_{6263} = 1$ _{(Square (6,2))}

$x_{6353} + x_{6362} + x_{6364} = 1$ _{(Square (6,3))}

$x_{6454} + x_{6463} + x_{6465} = 1$ _{(Square (6,4))}

$x_{6555} + x_{6564} + x_{6566} = 1$ _{(Square (6,5))}

$x_{6656} + x_{6665} = 1$ _{(Square (6,6))}

Incoming edges cosntraints

$x_{1211} + x_{2111} = 1$ _{(Square (1,1))}

$x_{1112} + x_{2212} + x_{1312} = 1$ _{(Square (1,2))}

$x_{1213} + x_{2313} + x_{1413} = 1$ _{(Square (1,3))}

$x_{1314} + x_{2414} + x_{1514} = 1$ _{(Square (1,4))}

$x_{1415} + x_{2515} + x_{1615} = 1$ _{(Square (1,5))}

$x_{1516} + x_{2616} = 1$ _{(Square (1,6))}

$x_{1121} + x_{2221} + x_{3121} = 1$ _{(Square (2,1))}

$x_{1222} + x_{2122} + x_{2322} + x_{3222} = 1$ _{(Square (2,2))}

$x_{1323} + x_{2223} + x_{2423} + x_{3323} = 1$ _{(Square (2,3))}

$x_{1424} + x_{2324} + x_{2524} + x_{3424} = 1$ _{(Square (2,4))}

$x_{1525} + x_{2425} + x_{2625} + x_{3525} = 1$ _{(Square (2,5))}

$x_{1626} + x_{2526} + x_{3626} = 1$ _{(Square (2,6))}

$x_{2131} + x_{3231} + x_{4131} = 1$ _{(Square (3,1))}

$x_{2232} + x_{3132} + x_{3332} + x_{4232} = 1$ _{(Square (3,2))}

$x_{2333} + x_{3233} + x_{3433} + x_{4333} = 1$ _{(Square (3,3))}

$x_{2434} + x_{3334} + x_{3534} + x_{4434} = 1$ _{(Square (3,4))}

$x_{2535} + x_{3435} + x_{3635} + x_{4535} = 1$ _{(Square (3,5))}

$x_{2636} + x_{3536} + x_{4636} = 1$ _{(Square (3,6))}

$x_{3141} + x_{4241} + x_{5141} = 1$ _{(Square (4,1))}

$x_{3242} + x_{4142} + x_{4342} + x_{5242} = 1$ _{(Square (4,2))}

$x_{3343} + x_{4243} + x_{4443} + x_{5343} = 1$ _{(Square (4,3))}

$x_{3444} + x_{4344} + x_{4544} + x_{5444} = 1$ _{(Square (4,4))}

$x_{3545} + x_{4445} + x_{4645} + x_{5545} = 1$ _{(Square (4,5))}

$x_{3646} + x_{4546} + x_{5646} = 1$ _{(Square (4,6))}

$x_{4151} + x_{5251} + x_{6151} = 1$ _{(Square (5,1))}

$x_{4252} + x_{5152} + x_{5352} + x_{6252} = 1$ _{(Square (5,2))}

$x_{4353} + x_{5253} + x_{5453} + x_{6353} = 1$ _{(Square (5,3))}

$x_{4454} + x_{5354} + x_{5554} + x_{6454} = 1$ _{(Square (5,4))}

$x_{4555} + x_{5455} + x_{5655} + x_{6555} = 1$ _{(Square (5,5))}

$x_{4656} + x_{5556} + x_{6656} = 1$ _{(Square (5,6))}

$x_{5161} + x_{6261} = 1$ _{(Square (6,1))}

$x_{5262} + x_{6162} + x_{6362} = 1$ _{(Square (6,2))}

$x_{5363} + x_{6263} + x_{6463} = 1$ _{(Square (6,3))}

$x_{5464} + x_{6364} + x_{6564} = 1$ _{(Square (6,4))}

$x_{5565} + x_{6465} + x_{6665} = 0$ _{(Square (6,5))}

$x_{5666} + x_{6566} = 1$ _{(Square (6,6))}

Ordinal position constraints

$u_{65} = 1$ _{(Square 1)}

$u_{66} \ge u_{65} + 1$ _{(Square 2)}

$u_{56} \ge u_{66} + 1$ _{(Square 3)}

$u_{64} \ge u_{56} + 1$ _{(Square 4)}

$u_{53} \ge u_{64} + 1$ _{(Square 5)}

$u_{42} \ge u_{53} + 1$ _{(Square 6)}

$u_{31} \ge u_{42} + 1$ _{(Square 7)}

$u_{21} \ge u_{31} + 1$ _{(Square 8)}

$u_{11} \ge u_{21} + 1$ _{(Square 9)}

$u_{12} \ge u_{11} + 1$ _{(Square 10)}

$u_{13} \ge u_{12} + 1$ _{(Square 11)}

$u_{35} \ge u_{13} + 1$ _{(Square 12)}

$u_{24} \ge u_{35} + 1$ _{(Square 13)}

$u_{34} \ge u_{24} + 1$ _{(Square 14)}

$u_{43} \ge u_{34} + 1$ _{(Square 15)}

$u_{46} \ge u_{43} + 1$ _{(Square 16)}

$u_{46} = 36$ _{(Square 16)}

Subroute elimination - MZT - constraints

$u_{11} \ge u_{12} + 1 - 36(1 - x_{1211})$

$u_{11} \ge u_{21} + 1 - 36(1 - x_{2111})$

$u_{12} \ge u_{11} + 1 - 36(1 - x_{1112})$

$u_{12} \ge u_{22} + 1 - 36(1 - x_{2212})$

$u_{12} \ge u_{13} + 1 - 36(1 - x_{1312})$

$u_{13} \ge u_{12} + 1 - 36(1 - x_{1213})$

$u_{13} \ge u_{23} + 1 - 36(1 - x_{2313})$

$u_{13} \ge u_{14} + 1 - 36(1 - x_{1413})$

$u_{14} \ge u_{13} + 1 - 36(1 - x_{1314})$

$u_{14} \ge u_{24} + 1 - 36(1 - x_{2414})$

$u_{14} \ge u_{15} + 1 - 36(1 - x_{1514})$

$u_{15} \ge u_{14} + 1 - 36(1 - x_{1415})$

$u_{15} \ge u_{25} + 1 - 36(1 - x_{2515})$

$u_{15} \ge u_{16} + 1 - 36(1 - x_{1615})$

$u_{16} \ge u_{15} + 1 - 36(1 - x_{1516})$

$u_{16} \ge u_{26} + 1 - 36(1 - x_{2616})$

$u_{21} \ge u_{11} + 1 - 36(1 - x_{1121})$

$u_{21} \ge u_{22} + 1 - 36(1 - x_{2221})$

$u_{21} \ge u_{31} + 1 - 36(1 - x_{3121})$

$u_{22} \ge u_{12} + 1 - 36(1 - x_{1222})$

$u_{22} \ge u_{21} + 1 - 36(1 - x_{2122})$

$u_{22} \ge u_{23} + 1 - 36(1 - x_{2322})$

$u_{22} \ge u_{32} + 1 - 36(1 - x_{3222})$

$u_{23} \ge u_{13} + 1 - 36(1 - x_{1323})$

$u_{23} \ge u_{22} + 1 - 36(1 - x_{2223})$

$u_{23} \ge u_{24} + 1 - 36(1 - x_{2423})$

$u_{23} \ge u_{33} + 1 - 36(1 - x_{3323})$

$u_{24} \ge u_{14} + 1 - 36(1 - x_{1424})$

$u_{24} \ge u_{23} + 1 - 36(1 - x_{2324})$

$u_{24} \ge u_{25} + 1 - 36(1 - x_{2524})$

$u_{24} \ge u_{34} + 1 - 36(1 - x_{3424})$

$u_{25} \ge u_{15} + 1 - 36(1 - x_{1525})$

$u_{25} \ge u_{24} + 1 - 36(1 - x_{2425})$

$u_{25} \ge u_{26} + 1 - 36(1 - x_{2625})$

$u_{25} \ge u_{35} + 1 - 36(1 - x_{3525})$

$u_{26} \ge u_{16} + 1 - 36(1 - x_{1626})$

$u_{26} \ge u_{25} + 1 - 36(1 - x_{2526})$

$u_{26} \ge u_{36} + 1 - 36(1 - x_{3626})$

$u_{31} \ge u_{21} + 1 - 36(1 - x_{2131})$

$u_{31} \ge u_{32} + 1 - 36(1 - x_{3231})$

$u_{31} \ge u_{41} + 1 - 36(1 - x_{4131})$

$u_{32} \ge u_{22} + 1 - 36(1 - x_{2232})$

$u_{32} \ge u_{31} + 1 - 36(1 - x_{3132})$

$u_{32} \ge u_{33} + 1 - 36(1 - x_{3332})$

$u_{32} \ge u_{42} + 1 - 36(1 - x_{4232})$

$u_{33} \ge u_{23} + 1 - 36(1 - x_{2333})$

$u_{33} \ge u_{32} + 1 - 36(1 - x_{3233})$

$u_{33} \ge u_{34} + 1 - 36(1 - x_{3433})$

$u_{33} \ge u_{43} + 1 - 36(1 - x_{4333})$

$u_{34} \ge u_{24} + 1 - 36(1 - x_{2434})$

$u_{34} \ge u_{33} + 1 - 36(1 - x_{3334})$

$u_{34} \ge u_{35} + 1 - 36(1 - x_{3534})$

$u_{34} \ge u_{44} + 1 - 36(1 - x_{4434})$

$u_{35} \ge u_{25} + 1 - 36(1 - x_{2535})$

$u_{35} \ge u_{34} + 1 - 36(1 - x_{3435})$

$u_{35} \ge u_{36} + 1 - 36(1 - x_{3635})$

$u_{35} \ge u_{45} + 1 - 36(1 - x_{4535})$

$u_{36} \ge u_{26} + 1 - 36(1 - x_{2636})$

$u_{36} \ge u_{35} + 1 - 36(1 - x_{3536})$

$u_{36} \ge u_{46} + 1 - 36(1 - x_{4636})$

$u_{41} \ge u_{31} + 1 - 36(1 - x_{3141})$

$u_{41} \ge u_{42} + 1 - 36(1 - x_{4241})$

$u_{41} \ge u_{51} + 1 - 36(1 - x_{5141})$

$u_{42} \ge u_{32} + 1 - 36(1 - x_{3242})$

$u_{42} \ge u_{41} + 1 - 36(1 - x_{4142})$

$u_{42} \ge u_{43} + 1 - 36(1 - x_{4342})$

$u_{42} \ge u_{52} + 1 - 36(1 - x_{5242})$

$u_{43} \ge u_{33} + 1 - 36(1 - x_{3343})$

$u_{43} \ge u_{42} + 1 - 36(1 - x_{4243})$

$u_{43} \ge u_{44} + 1 - 36(1 - x_{4443})$

$u_{43} \ge u_{53} + 1 - 36(1 - x_{5343})$

$u_{44} \ge u_{34} + 1 - 36(1 - x_{3444})$

$u_{44} \ge u_{43} + 1 - 36(1 - x_{4344})$

$u_{44} \ge u_{45} + 1 - 36(1 - x_{4544})$

$u_{44} \ge u_{54} + 1 - 36(1 - x_{5444})$

$u_{45} \ge u_{35} + 1 - 36(1 - x_{3545})$

$u_{45} \ge u_{44} + 1 - 36(1 - x_{4445})$

$u_{45} \ge u_{46} + 1 - 36(1 - x_{4645})$

$u_{45} \ge u_{55} + 1 - 36(1 - x_{5545})$

$u_{46} \ge u_{36} + 1 - 36(1 - x_{3646})$

$u_{46} \ge u_{45} + 1 - 36(1 - x_{4546})$

$u_{46} \ge u_{56} + 1 - 36(1 - x_{5646})$

$u_{51} \ge u_{41} + 1 - 36(1 - x_{4151})$

$u_{51} \ge u_{52} + 1 - 36(1 - x_{5251})$

$u_{51} \ge u_{61} + 1 - 36(1 - x_{6151})$

$u_{52} \ge u_{42} + 1 - 36(1 - x_{4252})$

$u_{52} \ge u_{51} + 1 - 36(1 - x_{5152})$

$u_{52} \ge u_{53} + 1 - 36(1 - x_{5352})$

$u_{52} \ge u_{62} + 1 - 36(1 - x_{6252})$

$u_{53} \ge u_{43} + 1 - 36(1 - x_{4353})$

$u_{53} \ge u_{52} + 1 - 36(1 - x_{5253})$

$u_{53} \ge u_{54} + 1 - 36(1 - x_{5453})$

$u_{53} \ge u_{63} + 1 - 36(1 - x_{6353})$

$u_{54} \ge u_{44} + 1 - 36(1 - x_{4454})$

$u_{54} \ge u_{53} + 1 - 36(1 - x_{5354})$

$u_{54} \ge u_{55} + 1 - 36(1 - x_{5554})$

$u_{54} \ge u_{64} + 1 - 36(1 - x_{6454})$

$u_{55} \ge u_{45} + 1 - 36(1 - x_{4555})$

$u_{55} \ge u_{54} + 1 - 36(1 - x_{5455})$

$u_{55} \ge u_{56} + 1 - 36(1 - x_{5655})$

$u_{55} \ge u_{65} + 1 - 36(1 - x_{6555})$

$u_{56} \ge u_{46} + 1 - 36(1 - x_{4656})$

$u_{56} \ge u_{55} + 1 - 36(1 - x_{5556})$

$u_{56} \ge u_{66} + 1 - 36(1 - x_{6656})$

$u_{61} \ge u_{51} + 1 - 36(1 - x_{5161})$

$u_{61} \ge u_{62} + 1 - 36(1 - x_{6261})$

$u_{62} \ge u_{52} + 1 - 36(1 - x_{5262})$

$u_{62} \ge u_{61} + 1 - 36(1 - x_{6162})$

$u_{62} \ge u_{63} + 1 - 36(1 - x_{6362})$

$u_{63} \ge u_{53} + 1 - 36(1 - x_{5363})$

$u_{63} \ge u_{62} + 1 - 36(1 - x_{6263})$

$u_{63} \ge u_{64} + 1 - 36(1 - x_{6463})$

$u_{64} \ge u_{54} + 1 - 36(1 - x_{5464})$

$u_{64} \ge u_{63} + 1 - 36(1 - x_{6364})$

$u_{64} \ge u_{65} + 1 - 36(1 - x_{6564})$

$u_{65} \ge u_{55} + 1 - 36(1 - x_{5565})$

$u_{65} \ge u_{64} + 1 - 36(1 - x_{6465})$

$u_{65} \ge u_{66} + 1 - 36(1 - x_{6665})$

$u_{66} \ge u_{56} + 1 - 36(1 - x_{5666})$

$u_{66} \ge u_{65} + 1 - 36(1 - x_{6566})$

Binarity constraints for edge variables

$x_{1112} \in \{0,1\}$

$x_{1121} \in \{0,1\}$

$x_{1211} \in \{0,1\}$

$x_{1222} \in \{0,1\}$

$x_{1213} \in \{0,1\}$

$x_{1312} \in \{0,1\}$

$x_{1323} \in \{0,1\}$

$x_{1314} \in \{0,1\}$

$x_{1413} \in \{0,1\}$

$x_{1424} \in \{0,1\}$

$x_{1415} \in \{0,1\}$

$x_{1514} \in \{0,1\}$

$x_{1525} \in \{0,1\}$

$x_{1516} \in \{0,1\}$

$x_{1615} \in \{0,1\}$

$x_{1626} \in \{0,1\}$

$x_{2111} \in \{0,1\}$

$x_{2122} \in \{0,1\}$

$x_{2131} \in \{0,1\}$

$x_{2212} \in \{0,1\}$

$x_{2221} \in \{0,1\}$

$x_{2223} \in \{0,1\}$

$x_{2232} \in \{0,1\}$

$x_{2313} \in \{0,1\}$

$x_{2322} \in \{0,1\}$

$x_{2324} \in \{0,1\}$

$x_{2333} \in \{0,1\}$

$x_{2414} \in \{0,1\}$

$x_{2423} \in \{0,1\}$

$x_{2425} \in \{0,1\}$

$x_{2434} \in \{0,1\}$

$x_{2515} \in \{0,1\}$

$x_{2524} \in \{0,1\}$

$x_{2526} \in \{0,1\}$

$x_{2535} \in \{0,1\}$

$x_{2616} \in \{0,1\}$

$x_{2625} \in \{0,1\}$

$x_{2636} \in \{0,1\}$

$x_{3121} \in \{0,1\}$

$x_{3132} \in \{0,1\}$

$x_{3141} \in \{0,1\}$

$x_{3222} \in \{0,1\}$

$x_{3231} \in \{0,1\}$

$x_{3233} \in \{0,1\}$

$x_{3242} \in \{0,1\}$

$x_{3323} \in \{0,1\}$

$x_{3332} \in \{0,1\}$

$x_{3334} \in \{0,1\}$

$x_{3343} \in \{0,1\}$

$x_{3424} \in \{0,1\}$

$x_{3433} \in \{0,1\}$

$x_{3435} \in \{0,1\}$

$x_{3444} \in \{0,1\}$

$x_{3525} \in \{0,1\}$

$x_{3534} \in \{0,1\}$

$x_{3536} \in \{0,1\}$

$x_{3545} \in \{0,1\}$

$x_{3626} \in \{0,1\}$

$x_{3635} \in \{0,1\}$

$x_{3646} \in \{0,1\}$

$x_{4131} \in \{0,1\}$

$x_{4142} \in \{0,1\}$

$x_{4151} \in \{0,1\}$

$x_{4232} \in \{0,1\}$

$x_{4241} \in \{0,1\}$

$x_{4243} \in \{0,1\}$

$x_{4252} \in \{0,1\}$

$x_{4333} \in \{0,1\}$

$x_{4342} \in \{0,1\}$

$x_{4344} \in \{0,1\}$

$x_{4353} \in \{0,1\}$

$x_{4434} \in \{0,1\}$

$x_{4443} \in \{0,1\}$

$x_{4445} \in \{0,1\}$

$x_{4454} \in \{0,1\}$

$x_{4535} \in \{0,1\}$

$x_{4544} \in \{0,1\}$

$x_{4546} \in \{0,1\}$

$x_{4555} \in \{0,1\}$

$x_{4636} \in \{0,1\}$

$x_{4645} \in \{0,1\}$

$x_{4656} \in \{0,1\}$

$x_{5141} \in \{0,1\}$

$x_{5152} \in \{0,1\}$

$x_{5161} \in \{0,1\}$

$x_{5242} \in \{0,1\}$

$x_{5251} \in \{0,1\}$

$x_{5253} \in \{0,1\}$

$x_{5262} \in \{0,1\}$

$x_{5343} \in \{0,1\}$

$x_{5352} \in \{0,1\}$

$x_{5354} \in \{0,1\}$

$x_{5363} \in \{0,1\}$

$x_{5444} \in \{0,1\}$

$x_{5453} \in \{0,1\}$

$x_{5455} \in \{0,1\}$

$x_{5464} \in \{0,1\}$

$x_{5545} \in \{0,1\}$

$x_{5554} \in \{0,1\}$

$x_{5556} \in \{0,1\}$

$x_{5565} \in \{0,1\}$

$x_{5646} \in \{0,1\}$

$x_{5655} \in \{0,1\}$

$x_{5666} \in \{0,1\}$

$x_{6151} \in \{0,1\}$

$x_{6162} \in \{0,1\}$

$x_{6252} \in \{0,1\}$

$x_{6261} \in \{0,1\}$

$x_{6263} \in \{0,1\}$

$x_{6353} \in \{0,1\}$

$x_{6362} \in \{0,1\}$

$x_{6364} \in \{0,1\}$

$x_{6454} \in \{0,1\}$

$x_{6463} \in \{0,1\}$

$x_{6465} \in \{0,1\}$

$x_{6555} \in \{0,1\}$

$x_{6564} \in \{0,1\}$

$x_{6566} \in \{0,1\}$

$x_{6656} \in \{0,1\}$

$x_{6665} \in \{0,1\}$

Non-negativity constraints for positional variables

$u_{11} \ge 0$ _{(Square (1,1))}

$u_{12} \ge 0$ _{(Square (1,2))}

$u_{13} \ge 0$ _{(Square (1,3))}

$u_{14} \ge 0$ _{(Square (1,4))}

$u_{15} \ge 0$ _{(Square (1,5))}

$u_{16} \ge 0$ _{(Square (1,6))}

$u_{21} \ge 0$ _{(Square (2,1))}

$u_{22} \ge 0$ _{(Square (2,2))}

$u_{23} \ge 0$ _{(Square (2,3))}

$u_{24} \ge 0$ _{(Square (2,4))}

$u_{25} \ge 0$ _{(Square (2,5))}

$u_{26} \ge 0$ _{(Square (2,6))}

$u_{31} \ge 0$ _{(Square (3,1))}

$u_{32} \ge 0$ _{(Square (3,2))}

$u_{33} \ge 0$ _{(Square (3,3))}

$u_{34} \ge 0$ _{(Square (3,4))}

$u_{35} \ge 0$ _{(Square (3,5))}

$u_{36} \ge 0$ _{(Square (3,6))}

$u_{41} \ge 0$ _{(Square (4,1))}

$u_{42} \ge 0$ _{(Square (4,2))}

$u_{43} \ge 0$ _{(Square (4,3))}

$u_{44} \ge 0$ _{(Square (4,4))}

$u_{45} \ge 0$ _{(Square (4,5))}

$u_{46} \ge 0$ _{(Square (4,6))}

$u_{51} \ge 0$ _{(Square (5,1))}

$u_{52} \ge 0$ _{(Square (5,2))}

$u_{53} \ge 0$ _{(Square (5,3))}

$u_{54} \ge 0$ _{(Square (5,4))}

$u_{55} \ge 0$ _{(Square (5,5))}

$u_{56} \ge 0$ _{(Square (5,6))}

$u_{61} \ge 0$ _{(Square (6,1))}

$u_{62} \ge 0$ _{(Square (6,2))}

$u_{63} \ge 0$ _{(Square (6,3))}

$u_{64} \ge 0$ _{(Square (6,4))}

$u_{65} \ge 0$ _{(Square (6,5))}

$u_{66} \ge 0$ _{(Square (6,6))}