Здравствуйте, hypnotic, Вы писали:

H>Здравствуйте, _DAle_, Вы писали:

_DA>>- если порядка сотен вершин, то надо использовать cutting-plane method

H>Можно чуть поподробнее про cutting-plane method для данной задачи?
H>Я эту задачу на сильно разреженном графе решал методом ветвей и границ.

Вот примерное описание
http://www.tsp.gatech.edu/methods/dfj/index.html
В 2001 году с помощью этого метода был найден кратчайший гамильтонов цикл для 15112 немецких городов. На тот момент это был рекордный результат.

P.S. Сорри за долгий ответ, был небольшой отпуск