1

我有一个混合整数二次程序 (MIQP)，我想使用 SCIP 解决它。该程序的形式使得在固定整数变量时，问题变成了线性程序。在修复连续变量后，它就变成了一个整数程序。一个简单的例子：

最大限度。\Sigma_{i} n_i * f_i(x_i)

这样。
n_1 * x_1 + n2 * x_2 < t
n_3 * x_1 + n2 * x_2 < m
。
.
n_i 和 x_i 中的许多随机二次约束，
依此类推

这里 f_i 是一个凹分段线性函数。
x_i 是连续变量（它们取实数值）
n_i 是整数变量

我能够使用 SCIP 解决问题。但是对于具有大量变量的问题，SCIP 需要花费大量时间才能找到解决方案。我特别注意到它没有找到很多原始解决方案。因此，上限降低的速度非常慢。但是，我可以通过积极地设置启发式强调来获得更好的结果。
如果有人可以指导我解决以下问题，那就太好了：
1）是否有任何特定的算法/软件包可以解决完全适合上述模型的问题？
2) 关于如何提高找到原始解决方案的速度的建议。
3）我可以使用什么类型的分支来获得更好的结果？
4）任何关于提高性能的指导都会非常有帮助。

我也可以放松整数约束。

谢谢

4

1 回答 1

1

1) SCIP 中的算法应该适合您的问题。还有其他实现类似算法的软件包，例如 BARON 和 ANTIGONE。

2) 看看哪些原始启发式算法在您的运行中是成功的，并更改它们的参数以更频繁地运行它们。

3）不知道。默认应该没问题。

4）确保你的变量有良好的界限。更紧密的界限允许构建更紧密的松弛。

如果您可以在某处发布您的问题实例，或 SCIP 运行日志，包括最后的详细统计信息，也许有人可以提供更多关于需要改进的提示。

于 2016-03-02T10:07:23.800 回答