Как решить проблему 8 ферзей с CVXPY? - PullRequest
Новая
       42

Как решить проблему 8 ферзей с CVXPY?

0 голосов
/ 12 февраля 2019

Я действительно новичок в CVXPY.Я пытаюсь решить проблему 8 ферзей , то есть проблему размещения 8 шахматных ферзей на шахматной доске 8 x 8, чтобы никакие две королевы не угрожали друг другу.Насколько я понимаю, ограничения должны быть:

  1. сумма каждой строки равна 1.
  2. сумма каждого столбца равна 1.
  3. сумма каждогодиагональ равна 1.
  4. все переменные должны быть больше 0.

Более того, целевой функцией должно быть: максимизировать 2-норму матрицы (чтобы мы получали только1 и 0, потому что мы можем получить сумму 1 также с float с, но норма 1 с нулями больше, чем норма с плавающей точкой от 0 до 1, которая также составляет до 1 (например: 0,8 ^ 2 + 0,2^ 2 <1 ^ 2 + 0 ^ 2). </p>

Возможно ли решить эту проблему в CVXPY? Я довольно не понимаю, как формировать ограничения и целевую функцию в CVXPY, но вотмои первоначальные первоначальные попытки (я сразу получил «Ошибка DCP», поэтому у меня не было причин продолжать, но все же): 

from cvxpy import *
x=Variable(shape=(9,9), name='board')
obj = Maximize(norm(x))
const = [sum(x, axis=1)==1]
prob=Problem(objective=obj,constraints=const)
prob.solve()

Любая помощь будет оценена !!!

1 Ответ

0 голосов
/ 13 февраля 2019

Как я уже сказал в комментариях:

Maximize(norm(x)) приводит к невыпуклости проблемы.CVXPY предназначен только для выпуклых задач.

Проблемы с 8 ферментами обычно моделируются с помощью двоичных переменных ( link ).Вы пытаетесь использовать невыпуклую цель, чтобы обойти это.В общем случае это не работает:

  • Выпуклые решатели не примут вашу проблему
  • Локальные решатели NLP окажутся в локальном оптимуме
  • Так что глобальный решатель NLPтребуется (например, барон, антигона или куенн).Но это не проще, чем использование линейного MIP-решателя.

Как правило, сложную дискретную проблему нельзя сделать «легко решаемой» с помощью трюков.Другой такой трюк заключается в использовании ограничения x(1-x)=0.Это страдает от той же проблемы: вам нужен глобальный решатель для сложной невыпуклой задачи.Так что лучше придерживаться линейной формулировки с бинарными переменными.Если бы существовал простой способ сделать это выпуклым и непрерывным, то, по сути, разработчики MIP-решателей были бы вне бизнеса.С другой стороны, если вы обнаружите такое преобразование, я уверен, что вас будет ждать Нобелевский приз.

Также, как указано в комментариях, обратите внимание, что 

3. sum of each diagonal equals to 1.

должночитать 

3. sum of each diagonal <= 1.
...