# How to describe the traveling salesman problem with an integer programming model?

I'm trying to describe the travelling salesman problem as an integer programming model. I'm interested in the asymmetric version of the problem. The problem can be summarized as finding the optimal Hamilton circuit. We also always start at node 1. ex: 1 -> 2 -> 4 -> 3 -> 1 is a solution for a graph containing 4 nodes.

I have the following constraints :

(1) $$\sum_{(i,j) \in A^+} y_{ij} = 1$$ Here $$y_{ij}$$ is a binary variable. if it's equal to 1 it means that the edge $$(i,j)$$ is in the optimal path. $$(i,j) \in A^+$$ means all edges that enters in a node $$A$$.

(2) $$\sum_{(j,i) \in A^-} y_{ji} = 1$$ Same thing but with every edge that exits a node $$A$$.

In the following constraints we use $$x_{ij} \geq 0$$ which represents the flow on an edge $$(i,j)$$

(3) $$\sum_{(i,j) \in A^+(i)} x_{ij} = |V|$$ when $$i \in V \text{ , } i = 1$$ This means that the total flow that exit through the various edges going out of node 1 is equal to the number of nodes in the graph.

(4) $$\sum_{(i,j) \in A^+(i)} x_{ij} - \sum_{(j,i) \in A^-(i)} x_{ji} = -1$$ when $$i \in V \text{ , } i \neq 1$$ This means that a node i consume one unit of flow. The exception is node 1.

(5) $$\sum_{(j,i) \in A^-(i)} x_{ji} = 1$$ when $$i \in V \text{ , } i = 1$$ This means that the flow that is sent to node 1 is equal to 1. This correspond to when we arrive to our destination ex: 1 -> 2 -> 3 -> 4 -> 1.

This programming model is not complete as long as I do not link the binary variables with the flow variables. However I don't understand how to do it properly. Should a new constraint be added?

To enforce $$x_{i,j} > 0 \implies y_{i,j} = 1$$, you can impose a linear big-M constraint $$x_{i,j} \le (|V|-1) y_{i,j}.$$
• For the first node should the big-M constraint be $x_{1,j} \leq |V| y_{1,j}$? Imagine we have 4 nodes this means that node 1 will send 4 units of flow on one of its edges to node ex: 2. Node 2 will consume 1 unit and send 3 units to the next node. It's only when we arrive back at node 1 that it will consume 1 unit. – WindBreeze Nov 23 '20 at 14:33
• That's what I had at first, but you need not send 1 unit back to node 1. Ahuja uses $|V|-1$. – RobPratt Nov 23 '20 at 14:34
• In my copy, it is (16.3e): $x_{i,j} \le (n-1)y_{i,j}$. The big-M value is $n-1$, which corresponds to your $|V|-1$. – RobPratt Nov 23 '20 at 21:07