Direkt zum Inhalt

Lexikon der Mathematik: subtour elimination constraints

Techniken, um in auf der Assignment-Relaxation beruhenden Branchand-Bound Algorithmen für das Travelling-Salesman-Problem disjunkte Teilprobleme zu erhalten, in denen mindestens eine Rundreise auf einer Teilmenge der Orte, die bei der Lö-sung der Assignment-Relaxation berechnet wurde, eliminiert wird.

Bei einer Rundreise auf i Orten können z. B. i Teilprobleme gebildet werden, indem im j-ten Teilproblem die ersten j − 1 Teilstrecken der Rundreise erzwungen und die j-te Teilstrecke verboten werden.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.