Problem des Handlungsreisenden als ganzzahliges lineares Programm

Das Problem des Handlungsreisenden ist also ein Problem, bei dem ein Handlungsreisender alle Städte so durchqueren muss, dass die Gesamtfahrstrecke minimal ist. Sie können dies als ganzzahliges lineares Problem umschreiben:

Beschriften Sie die Städte mit den Nummern$0, ...,n$und definieren:

$x_{ij} = \begin{cases} 1 & \text{the path goes from city } i \text{ to city } j \\ 0 & \text{otherwise} \end{cases}$

Für$i = 0, ...,n$, lassen$u_i$sei eine künstliche Variable und nimm schließlich$c_{ij}$die Entfernung von der Stadt sein$i$zur Stadt$j$. Dann kann TSP als das folgende ganzzahlige lineare Programmierproblem geschrieben werden:

$\begin{align} \min &\sum_{i=0}^n \sum_{j\ne i,j=0}^nc_{ij}x_{ij} && \\ & 0 \le x_{ij} \le 1 && i,j=0, \cdots, n \\ & u_{i} \in \mathbf{Z} && i=0, \cdots, n \\ & \sum_{i=0,i\ne j}^n x_{ij} = 1 && j=0, \cdots, n \\ & \sum_{j=0,j\ne i}^n x_{ij} = 1 && i=0, \cdots, n \\ &u_i-u_j +nx_{ij} \le n-1 && 1 \le i \ne j \le n \end{align}$

Ich verstehe die letzte Einschränkung nicht,$u_i-u_j +nx_{ij} \le n-1,1 \le i \ne j \le n$. Es gibt einen Abschnitt auf Wikipedia, in dem erklärt wird, dass diese Einschränkung erzwingt, dass es nur eine einzige Tour gibt, die alle Städte abdeckt, anstatt mehrere unzusammenhängende Touren, die alle Städte abdecken. Es erklärt auch warum ( siehe Erklärung hier ), aber ich verstehe diese Erklärung nicht.

Kann jemand erklären, wie diese Einschränkung erzwingt, dass es nur eine einzige Tour gibt, die alle Städte abdeckt?