2

I need your help.

I am working on Travelling Salesman Problem. In that problem I have these constraints:

$ \sum\limits_{j=1}^{n} X_{ij} = 1$ , $ i=1,2, ...,n$

$ \sum\limits_{i=1}^{n} X_{ij} = 1 $ , $j=1,2, ...,n$

$X_{ij} \in \{0,1\}$, $X_{ij}=1$ if the arc goes from node i to node j, else $X_{ij}=0$

And Miller Tucker and Zemlin (MTZ) constraints.

$ u_{i}-u_{j}+nX_{ij} \leq n-1$ , $ i \ne j; i,j\in V- \{1\}=\{2, ...,n\}$

I need an example that shows MTZ constraints works.

I don´t understand why with the first and second constraints the graph can contain several subtours?

Thank you :)

Jean Marie
  • 81,803
lauzi
  • 21
  • 1
  • 3

2 Answers2

2

The first two sets of constraints impose that every node must be visited exactly once. Now take any two disjoint sub-tours. They obviously satisfy these constraints, but are not an Hamiltonian tour. Therefore vectors $x$ satisfying the first two constraints not necessarily represent an Hamiltonian tour.

As regards the MZT constraints (subtour elimination constraints), the following holds:

Theorem - A vector $x\in \mathbb{B}^{{n}^{2}}$ satisfying constraints (1) and (2) is an Hamiltonian tour $\Longleftrightarrow$ $x$ satisfies the MZT constraints for some vector $u \in \mathbb{R}^{n-1}$.

Proof

Suppose that $x$ satisfies the MZT constraints but that it is not an Hamiltonian tour. Then $x$ represents at least two disjoint subtours. Let $C$ the subtour not containing the node 1. Summing up the MZT constraints over the arcs $(i,j)\in C$ we get $$\sum_{(i,j)\in C}(u_i-u_j +nx_{ij}) \leq (n-1)|C|$$ that is $$n|C|\leq(n-1)|C|$$ that is a contradiction.

Now suppose that $x$ is an Hamiltonian tour. Without loss of generality we can assume that the node 1 is the first node of such a tour. For each node $i\neq 1$, we set $u_i=k$ if $i$ is the $k$-th node in the tour. It is easy to see that with this choice, the given $x$ and $u$ satisfy the MZT constraints.

Marcello Sammarra
  • 385
0

If you generate some random points (say 5) you will quickly see that using assignment constraints only will generate sub-tours. (It may take a few tries).

Let me test this hypothesis. After first try, I get:

----     38 PARAMETER xc  x-coordinates

i1 1.717,    i2 8.433,    i3 5.504,    i4 3.011,    i5 2.922


----     38 PARAMETER yc  y-coordinates

i1 2.241,    i2 3.498,    i3 8.563,    i4 0.671,    i5 5.002


----     38 PARAMETER d  distance

            i1          i2          i3          i4          i5

i1                   6.832       7.369       2.034       3.013
i2       6.832                   5.850       6.114       5.712
i3       7.369       5.850                   8.276       4.398
i4       2.034       6.114       8.276                   4.332
i5       3.013       5.712       4.398       4.332


----     38 VARIABLE x.L  tour

            i1          i2          i3          i4          i5

i1                                           1.000
i2                                                       1.000
i3                   1.000
i4       1.000
i5                               1.000
Erwin Kalvelagen
  • 4,267