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*} $$


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.