Miller, Tucker, Zemlin: Integer Programming Formulation
and Travelling Salesman Problem JACM 7(1960) 326-329
- zusätzliche Variablen
u1,…, un∈
mathend000#
- Constraints C
mathend000#:
∀1≤i≠j≤n : ui - uj + nxi, j≤n - 1
mathend000#
Übung: beweise
- für jede Rundreise gibt es eine Belegung der ui
mathend000#,
die C
mathend000# erfüllt.
- aus jeder Lösung von C
mathend000# kann man eine Rundreise rekonstruieren.
Was ist die anschauliche Bedeutung der ui
mathend000#?
2014-03-31