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

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.

• Welcome to CS.SE! I recommend proofreading your question to make sure the equations come out right, as Latex can be confusing -- some of yours were missing line breaks. I fixed it up, so it should be good now. – D.W. Dec 16 '15 at 0:24
• What have you tried? If you already know of an optimal tour, you should be able to plug that into your ILP formulation to get a particular value for each variable, then test by hand if it satisfies all of your equations, and check by hand whether the problem is indeed satisfiable as you have formulated it. If it violates one of the equations you can then double-check your reasoning for that equation. Basically, I recommend you do some basic trouble-shooting on your own before asking here, then edit your question to show us what sanity checks you've tried. – D.W. Dec 16 '15 at 0:25

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.