Travelling Salesman als MIP

(dieses Bsp. aus Papadimitriou und Steiglitz:
Combinatorial Optimization, Prentice Hall 1982)

Travelling Salesman:

• Instanz: Gewichte w : {1,…, n}²→$\mathbb {R}$_≥0∪{ + ∞} und Schranke s∈R_≥0
• Lösung: Rundreise mit Gesamtkosten ≤s

Ansatz zur Modellierung:

• Variablen x_{i, j}∈{0, 1}, Bedeutung: x_{i, j} = 1$\iff$ Kante (i, j) kommt in Rundreise vor
• Zielfunktion?
• Constraints -- reicht das: $\sum_{i}^{}$x_{i, j} = 1,$\sum_{j}^{}$x_{i, j} = 1 ?