Decision variables¶
Let us consider $N\times N$ binary decision variables $q$, representing which vertex to pass and
when.
That is, a component $q_{k, i}$ of the binary decision variables corresponds to passing the vertex $i$
at
$k$-th visit ($=1$) or not ($=0$). For example, when the binary variables are as follows, it
corresponds
to a closed path $0 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 0$ in the
above
graph.
| Order \ Index of vertex |
0 |
1 |
2 |
3 |
4 |
| 1st |
1 |
0 |
0 |
0 |
0 |
| 2nd |
0 |
1 |
0 |
0 |
0 |
| 3rd |
0 |
0 |
0 |
1 |
0 |
| 4th |
0 |
0 |
0 |
0 |
1 |
| 5th |
0 |
0 |
1 |
0 |
0 |
Objective function¶
Since the Hamiltonian cycle problem is to find one that satisfies the conditions, no objective
function
is considered.
Constraints¶
For $q$ to represent a Hamiltonian cycle, we need the following:
-
The $k$-th vertex must be a single vertex. We can rephrase this condition as there being exactly
a
single $1$ in each row of the binary variable table $q$.
-
Each vertex must be passed through exactly $1$ times. We can rewrite this condition as there
being
exactly a single $1$ in each column of the binary variable table $q$.
-
No transfers are allowed between vertices that are not connected. That is, when no edge connects
between vertices $i$ and $j$, both $q_{k, i}$ and $q_{k+1, j}$ must not be $1$.
The above conditions 1-3 can be written in mathematical expressions as follows, respectively.
\begin{align*}
\sum_{i=0}^{N-1} q_{k, i} = 1 & \quad \text{for} \quad k \in \{0, 1, \ldots, N-1\} \\
\sum_{k=0}^{N-1} q_{k, i} = 1 & \quad \text{for} \quad i \in \{0, 1, \ldots, N-1\} \\
q_{k, i}q_{k+1, j} = 0 & \quad \text{for} \quad k \in \{0, 1, \ldots, N-1\}, (i, j) \notin E.
\end{align*}
Here, $E$ denotes the edge set of $G$.
Also, when the binary variables $q$ satisfy all conditions 1-3, $q$ corresponds to a Hamiltonian
cycle of
$G$.
