Lineare Optimierung beim TSP

[Cyf]

Ich meinte damit, dass es mit Hilfe Branch-and-Cut offenbar möglich ist eine Zeit zu errechnen, die auf keinen Fall unterschritten werden kann, somit kann man die Qualität einer Lösung abschätzen, oder falls man diese Zeit mit Hilfe von Heuristiken erreicht, somit weiß, dass man die bestmögliche Route gefunden hat und man aufhören kann.
Die Frage nach den zusätzlichen Schwierigkeiten zielt vorallem darauf ab, welche Verfahren bei soetwas noch funktionieren, falls man es einbauen wollte, weil ich das Gefühl habe, dass es da Probleme geben könnte. Zur Lösung selbst halte ich derzeit ACO noch für das einfachste, wobei ich eben auch da nicht weiß, ob es sich umbauen ließe, weil sich hier ja der die Gewichtung der Kanten ständig ändert (aber ACO geht hier jetzt am Thema vorbei).