Хабрахабр (Стас Фомин)/Релаксация MAX-CUT

Ссылки сюда (2) →

• Написать, для данной матрицы весов W (numpy array, например), формулировку и решение задачи векторного программирования.
• Векторное программирование свести к semidefinite и для решения использовать пакет CVXOPT.
• Для Windows сборку CVXOPT брать тут http://www.lfd.uci.edu/~gohlke/pythonlibs/#cvxopt
• Придется вкурить документацию к CVXOPT (крутой оптимизационный пакет, очень полезно).

Собственно решение релаксации будет давать верхнюю оценку для MAX-CUT.

Решения этой задачи достаточно на «отлично».

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.