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

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

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

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

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

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

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