Travelling Salesman als MIP (II)

Miller, Tucker, Zemlin: Integer Programming Formulation and Travelling Salesman Problem JACM 7(1960) 326-329

• zusätzliche Variablen u₁,…, u_n∈$\mathbb {R}$
• Constraints C:  ∀1≤i≠j≤n : u_i - u_j + nx_{i, j}≤n - 1

Übung: beweise

• für jede Rundreise gibt es eine Belegung der u_i, die C erfüllt.
• aus jeder Lösung von C kann man eine Rundreise rekonstruieren.

Was ist die anschauliche Bedeutung der u_i?