How to formulate Traveling Salesman Problem (TSP) as Integer Linear Program (ILP)?

Question

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:

1. 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}$$
2. 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*}$$
3. 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.

Answer 1

You must have entered your ILP program into the ILP solver wrong. It's easy to verify that the ILP program is feasible, using the procedure I outlined in the comments. In particular, from the tour $c_0 \to c_1 \to c_2 \to c_0$ we get the assignment $e_{0,1}=e_{1,2}=e_{2,0}=1$ and $e_{1,0}=e_{2,1}=e_{0,2}=0$. Setting $u_1=0$ and $u_2=1$, we find a feasible solution: you can easily check by hand that every one of your equations is satisfied. So, you've done something wrong in entering it into the tool.

In the future, you should do that kind of sanity check on your own before asking here.