3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Dec 16, 2015 at 0:24
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Dec 16, 2015 at 0:25

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ I will :) But my actual qestion was not whether the ILP is solvable. I wanted to know if the transformation itself is correct. I'm new to this stuff and not really sure although the steps seem to be simple. Concerning the ILP tool: Im quite sure that i entered it correctly. Would it be appropriate to add the code here in another Edit? $\endgroup$
    – Paule
    Dec 16, 2015 at 18:20
  • $\begingroup$ @Paule, OK, I suggest that you do two things: (a) find the bug in the way you entered it into the ILP, and correct that, and then remove that part of the question, (b) edit the question to clarify what exactly your question is. If this doesn't answer your question, I'm not sure what your question is. You might want to see if you can articulate what you want to know that isn't already covered in en.wikipedia.org/wiki/… and other standard explanations of Miller-Tucker-Zemlin. $\endgroup$
    – D.W.
    Dec 16, 2015 at 20:47
  • $\begingroup$ No, I'm afraid that debugging your ILP code isn't on-topic for this site. We are for questions about computer science (e.g., concepts, algorithms) but not about code. I don't know if that kind of question would be on-topic anywhere on the Stack Exchange network. $\endgroup$
    – D.W.
    Dec 16, 2015 at 20:47
  • $\begingroup$ Your were right. Its a bug.. Not in my code but in the tool i use. I entered the ILP in another tool (LPSolve) and got the solution instantly. $\endgroup$
    – Paule
    Dec 17, 2015 at 11:40
  • $\begingroup$ I also made a small change to make the question clearer (i hope). Thanks for your help. $\endgroup$
    – Paule
    Dec 17, 2015 at 11:49

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.