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

Question

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

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

此外，目标函数应该是:最大化矩阵的 2-范数(这样我们只能得到 1 和 0，因为我们也可以使用 float 得到 1 的和，但是带零的 1 的范数大于 0 到 1 之间的 float 的范数，且总和也为 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 皇后问题通常使用二元变量 ( link ) 进行建模。您尝试使用非凸目标来绕过此问题。一般来说，这是行不通的:

• 凸求解器不会接受您的问题
• 局部 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.