0
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
11
  • $\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
    Commented Nov 23, 2020 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
    Commented Nov 23, 2020 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
    Commented Nov 23, 2020 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
    Commented Nov 23, 2020 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
    Commented Nov 28, 2020 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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