如何用CVXPY解决8皇后问题？

Question

我对 CVXPY 真的很陌生。我正在尝试解决8 个皇后问题，即将 8 个国际象棋皇后放在 8 x 8 棋盘上，这样两个皇后就不会互相威胁。据我了解，约束应该是：

1. 每行的总和等于 1。
2. 每列的总和等于 1。
3. 每条对角线的总和等于 1。
4. 所有变量都应大于 0。

此外，目标函数应该是：最大化矩阵的 2-范数（这样我们只能得到 1 和 0，因为我们也可以得到 s 的和为 1 float，但是 1 与 0 的范数大于浮点数的范数） 0 到 1 之间且总和为 1（例如：0.8^2+0.2^2 < 1^2+0^2）。

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()

任何帮助将不胜感激！！！

Answer 1

正如我在评论中已经说过的：

Maximize(norm(x))导致问题非凸。CVXPY 仅适用于凸问题。

8 皇后问题通常使用二元变量建模（链接）。您尝试使用非凸目标来绕过此问题。一般来说，这是行不通的：

• 凸求解器不会接受你的问题
• 局部 NLP 求解器最终将达到局部最优
• 因此需要一个全局 NLP 求解器（例如 Baron、Antigone 或 Couenne）。但这并不比使用线性 MIP 求解器容易。

一般来说，一个本质上困难的、离散的问题不能通过技巧变得“容易解决”。另一个这样的技巧是使用约束x(1-x)=0。这遇到了同样的问题：您需要一个全局求解器来解决困难的非凸问题。因此，最好坚持使用二元变量的线性公式。如果有一种简单的方法可以使其凸且连续，基本上 MIP 求解器开发人员就会破产。另一方面，如果你发现了这样的转变，我相信诺贝尔奖正在等着你。

另外，正如评论中提到的，请注意

3. sum of each diagonal equals to 1.

应该读

3. sum of each diagonal <= 1.