How do one solve the following integer program? $$ \begin{align*} \text{minimize} \quad &\sum_{(i,j) \in E} d_{ij} x_{ij} \\ \text{subject to} \quad & \sum_{j \in V} x_{ij} = 2 \;\; \forall i \in V \\ &\sum_{i,j \in S, i \neq j} x_{ij} \leq |S|-1 \;\; \forall S \subset V, S \neq \emptyset \\ &x_{ij} \in \{0,1\} \end{align*} $$

  • $\begingroup$ Can you name just one? I have never tried it before. Thanks in advance! $\endgroup$ – purrp son Dec 9 '18 at 18:04
  • $\begingroup$ @Juho Do you happen to know, if there is a good online version that does it automatically for you? $\endgroup$ – purrp son Dec 9 '18 at 18:13
  • $\begingroup$ @Juho Isn't it possible to solve it by hand? $\endgroup$ – purrp son Dec 9 '18 at 18:30
  • $\begingroup$ Yes, of course. Any algorithm that your computer uses can also be calculated by hand. If you truly only care about a 5-vertex instance, you can solve it in an instant by brute-force (just try all possible tours and take the shortest one). $\endgroup$ – Juho Dec 9 '18 at 18:31
  • $\begingroup$ Have you checked your textbook and the Wikipedia entry? In case you are not aware, you are asking one of most studied problem in computer science. Have you searched github for algorithms and implementations? $\endgroup$ – John L. Dec 9 '18 at 23:28

You solve any integer program by any algorithm for the problem. In general, integer programming is NP-hard, so there are naturally many approaches for the problem ranging from exact algorithms to various heuristics.

There are various tools that provide you with suitable methods, like Gurobi, CPLEX, MATLAB and Mathematica.

As a remark, if you only care about small instances (say at most 12 vertices), then you can also just try all possible tours and pick the shortest one easily. In that case, you can forget about an IP model. Such a model will be more useful when you can't afford to enumerate all possible solutions, but need something smarter to hopefully avoid some of this work.

  • $\begingroup$ I think you misunderstood me. I would like to go through a heuristic by hand on a small set of vertices like 5. What heuristic would be good for this purpose? I don't know how to program, that's why I am asking $\endgroup$ – purrp son Dec 9 '18 at 18:46
  • $\begingroup$ @purrpson Execute the nearest neighbor heuristic, you see it in action on Wikipedia. But note that this is not connected at all with your original question. $\endgroup$ – Juho Dec 9 '18 at 18:54
  • $\begingroup$ Final question, can Christofides algorithm be used to solve the linear integer programming problem? $\endgroup$ – purrp son Dec 9 '18 at 19:04
  • $\begingroup$ @purrpson No, like Wikipedia explains it's an approximation algorithm for TSP. It is not an algorithm to solve integer programs. $\endgroup$ – Juho Dec 9 '18 at 19:06

Your problem is TSP on the graph given by the vertex set $V$, the edge set $E$, and the weights $d_{ij}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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