0

我正在使用 Gurobi（通过 C++）作为我的理学硕士论文的一部分来解决二次背包问题实例。到目前为止，我能够生成一个具有二元决策变量、二次目标函数和容量约束的模型，Gurobi 很好地解决了它。然后我想解决QKP的持续松弛问题。我像以前一样构建了模型，但是使用连续变量而不是二进制变量，当我尝试优化它时，Gurobi 给了我一个异常：

10020 - Objective Q not PSD (negative diagonal entry)

这让我有点困惑，因为问题实例的所有值都≥0。在准备发布这个问题时，我将两个模型都写到文件中并发现了原因：

NAME (null)
* Max problem is converted into Min one

这当然意味着所有以前的正值现在都是负的。现在我知道为什么 Q 不是 PSD 但我该如何解决这个问题？我可以防止从 Max 问题转换为 Min 问题吗？我是否需要以不同的方式配置模型以实现连续松弛？

从我（没有经验的）的角度来看，它看起来就像 Gurobi 中弹自己的脚。

4

1 回答 1

2

当您使用 Gurobi 或任何其他凸优化器最大化二次目标时，您的“Q”矩阵必须是半负定的，而当您最小化时，您的“Q”矩阵必须是正定的。改变符号和目标的意义不会改变任何事情。

Gurobi 不会验证您的问题是否是凸问题，但它会报告它发现的任何非凸问题。您最初的问题似乎作为 MIP 解决的事实是一个意外，您不应该依赖它。

您应该通过一些简单的变换将具有二元变量的二次目标建模为线性问题。如果 x 和 y 是二进制的，则表达式x*y可以更改为z如果添加约束

z <= x
z <= y
z >= x + y - 1
于 2014-07-07T17:13:26.743 回答