如何使用CVXPY解决八皇后问题？

Question

我对CVXPY非常陌生。 我正在尝试解决八皇后问题，即在8x8的棋盘上放置8个国际象棋皇后，使得没有两个皇后互相威胁。 据我所知，约束应该是：

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

此外，目标函数应为：最大化矩阵的2-范数（以便我们只获取1和0，因为我们可以使用float获得1的总和，但是0之间的浮点数的范数比1的范数大到1^2+0^2（例如：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()

任何帮助都将不胜感激!!!

- Binyamin Even

---

并非如此。一些对角线将保持为空，其总和为0。 - user58697

"Maximize(norm(x))" 会导致问题变成非凸优化问题。CVXPY 仅用于凸优化问题。 - Erwin Kalvelagen

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.

- Erwin Kalvelagen

---

谢谢提供链接。在cvxpy中，有没有一种方法可以强制变量为0或1？ - Binyamin Even

是的，CVXPY支持二进制变量和MIP求解器（请参见文档）。因此，您可以轻松地构建线性MIP模型（它们本质上是凸的，所以CVXPY不会抱怨非凸性）。 - Erwin Kalvelagen