1
$\begingroup$

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?

$\endgroup$
10
$\begingroup$

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}.$$

This TSP formulation is described in Application 16.2 of Ahuja, Magnanti, and Orlin, Network Flows.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – WindBreeze Nov 23 '20 at 14:33
  • $\begingroup$ That's what I had at first, but you need not send 1 unit back to node 1. Ahuja uses $|V|-1$. $\endgroup$ – RobPratt Nov 23 '20 at 14:34
  • $\begingroup$ Could you tell me where I can find the big-M constraint in 16.2? I don't see it, maybe I'm not looking at the right edition of the book? $\endgroup$ – WindBreeze Nov 23 '20 at 20:46
  • $\begingroup$ 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$. $\endgroup$ – RobPratt Nov 23 '20 at 21:07
  • $\begingroup$ I have edited the question. I need a third constraint and the constraint given in your answer doesn't seem to work. $\endgroup$ – WindBreeze Nov 28 '20 at 18:46

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.