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∪{ + ∞} mathend000# und Schranke s∈R_≥0 mathend000#
• Lösung: Rundreise mit Gesamtkosten ≤s mathend000#

Ansatz zur Modellierung:

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