# Solve this integer program (problem: Travelling salesman problem)

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*}

• Can you name just one? I have never tried it before. Thanks in advance! – purrp son Dec 9 '18 at 18:04
• @Juho Do you happen to know, if there is a good online version that does it automatically for you? – purrp son Dec 9 '18 at 18:13
• @Juho Isn't it possible to solve it by hand? – purrp son Dec 9 '18 at 18:30
• 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). – Juho Dec 9 '18 at 18:31
• 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? – John L. Dec 9 '18 at 23:28

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