Binary Integer Programming question - what graph problem is represented

Question

I'm dealing with a BIP question, that represents a graph problem. The goal is finding the graph problem.

I've spend a lot of time trying to solving this question but I couldn't find the answer to that question.

All I'm given is the set of constraints and the objective function:

I'd really appreciate your help, no full answer needed, just a direction.

$$ \begin{align*} \min & \sum_{ijk} z_{ijk} c_{ij} \\ \text{s.t.}\; & \sum_j x_{ij} = 1 \qquad \forall i=0\ldots n-1 \\ & \sum_i x_{ij} = 1 \qquad \forall j=0\ldots n-1 \\ & z_{ijk} \geq x_{ik} + x_{j(k+1\,\mathrm{mod}\,n)} \qquad \forall i,j,k=0\ldots n-1 \\ & x_{ij},z_{ijk} \in \{0,1\} \end{align*} $$

Answer 1

This answer assumes that $c_{ij} \geq 0$.

The first two sets of equations guarantees that $x_{ij}$ is a permutation matrix. It defines a permutation $\pi$ on $\{0,\ldots,n-1\}$ in the following way: $\pi(j) = i$ if $x_{ij} = 1$.

The set of inequalities is a logical implication: if $x_{ik}=x_{j(k+1)}=1$ then $z_{ijk} = 1$. That is, if $\pi(k) = i$ and $\pi(k+1) = j$ then $z_{ijk}=1$.

Since $c_{ij} \geq 0$ and the objective is to minimize $\sum_{ijk} z_{ijk} c_{ij}$, we want to have $z_{ijk} = 0$ unless we are forced to take $z_{ijk} = 1$. Therefore $z={ijk} = x_{ik} \land x_{j(k+1)}$. This means that the objective function is $$ \min_\pi \sum_{k=0}^{n-1} c_{\pi(k)\pi(k+1)}. $$ This is the problem known as minimum directed Hamiltonian circuit.