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

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

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