Vrftsjtryk

I need your help.

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

$ sumlimits_{j=1}^{n} X_{ij} = 1$ , $ i=1,2, ...,n$

$ sumlimits_{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,jin 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 :)

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

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 $xin 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 $ineq 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.