时间戳

首页 > 解决方案 > CVXPY如何解决8皇后问题？

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

问题描述

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

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

此外，目标函数应该是：最大化矩阵的 2-范数（这样我们就只能得到 1 和 0，因为我们也可以得到 1 和floats 的和，但是 1 和零的范数大于浮点数的范数在 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()

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

标签： pythonoptimizationmathematical-optimizationn-queenscvxpy

解决方案

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

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.

推荐阅读