Consider this distance matrix of an asymmetric TSP instance: $$ \begin{matrix} & c_0 & c_1 & c_2\\ c_0 & 0 & 1 & 2\\ c_1 & 2 & 0 & 1\\ c_2 & 1 & 2 & 0 \end{matrix} $$
One optimal tour (with a total distance of 3) is clearly: $$ c_0 \rightarrow c_1 \rightarrow c_2 \rightarrow c_0$$
Now we can reformulate this as an ILP. Let $e_{i,j}\in\{0,1\}$ denote the presence or absence of the directed edge from $c_i$ to $c_j$ in the tour (0 - edge is not in the tour, 1 - edge is in the tour). Then we obtain the ILP by:
- setting the objective $$\text{minimize}\;\;\; 1\cdot e_{0,1} + 2\cdot e_{0,2} + 2\cdot e_{1,0} + 1\cdot e_{1,2} + 1\cdot e_{2,0} + 2\cdot e_{2,1}$$
- ensure that we arrive at city $c_i$ from exactly one other city and depart from $c_i$ to exactly one other city $$\begin{align*} e_{0,1} + e_{0,2} = 1\\ e_{1,0} + e_{1,2} = 1\\ e_{2,0} + e_{2,1} = 1\\ e_{1,0} + e_{2,0} = 1\\ e_{0,1} + e_{2,1} = 1\\ e_{0,2} + e_{1,2} = 1 \end{align*}$$
- ensure we do not find a set of minor tours (we want a complete tour through all 3 cities) by enforcing the following constraints for the artificial variables $u_i$ (Miller-Tucker-Zemlin subtour elimination constraints): $$\begin{align*} u_1 - u_2 + 2\cdot e_{1,2} \leq 1\\ u_2 - u_1 + 2\cdot e_{2,1} \leq 1\\ \end{align*}$$
Is this transformation correct? Its probably not because when I try to use a Solver it says that the ILP is infeasible.
I tried to follow the steps on Wikipedia: https://en.wikipedia.org/wiki/Travelling_salesman_problem#Integer_linear_programming_formulation
Edit 1
We can verify that there must be a solution to the ILP by the following considerations:
There are exactly 2 solutions to the equation system under 2. $$\begin{align*} \text{(1)}\;\;\;e_{0,1} = e_{1,2} = e_{2,0} = 1 \land e_{1,0} = e_{2,1} = e_{0,2} = 0\\ \text{(2)}\;\;\;e_{0,1} = e_{1,2} = e_{2,0} = 0 \land e_{1,0} = e_{2,1} = e_{0,2} = 1\\ \end{align*}$$
Since there are 6 variables and each variable can have only 2 values, we can easily verify this by testing all $2^6$ variable assignments.
Now we can observe that either $e_{1,2} = 0 \land e_{2,1} = 1$ or $e_{1,2} = 1 \land e_{2,1} = 0$ holds for the solutions.
In the first case we can satisfy the inequations under 3. by $u_1 = 2 \land u_2 = 1$ in the latter case by $u_1 = 1 \land u_2 = 2$.
Edit 2
This is annoying. I used another tool (LPSolve) to solve the exact same ILP and got the solution instantly. Seems that my transformation was correct and the tool is buggy.