SCIP不能很好地解决MIQP问题，而CPLEX很快就找到了解决方案。
回答 2
Stack Overflow用户
发布于 2022-11-17 11:46:22
，这是为什么？
你的问题在所有变量中都有一个相当密集的凸二次目标函数，一个线性约束，所有变量都被限制为积分。
SCIP识别凸性，但又试图通过求解LP和在LP中加入二次函数的线性化来构造线性松弛。它以LP的解为参照点(类似于Kelley的切面法)。这可能意味着缓慢收敛(更好的方法是在可行区域的边界处线性化)，也就是说，需要很多LP求解，直到达到一个合适的界限为止。此外，产生的线性化割集是密集的，这意味着每一个新的切割，LP变得越来越慢。在根节点中进行了多次循环之后，SCIP决定分离没有取得足够的进展(停滞)，并在分数整数变量上分支。然而，由于松弛仍然是如此糟糕，对偶界没有给出任何好的指导，在哪一个变量上分支。而且，由于LP解决的速度太慢，所以不能快速处理节点。
CPLEX很有可能通过求解MIQP的凸QP松弛来计算对偶界。这给出了接近最优值的一个很好的界。我不知道它是否用这一点来线性化二次函数，这会导致LP界等于QP界，然后用LP继续，或者它通过求解QP继续。
在MIQP方面真的比SCIP好得多吗？
在这种情况下(可能还有其他目标稠密的凸MIQP )，是的。
我没有正确配置SCIP吗？
不是的。
如何用SCIP解决这个问题？
在SCIP中没有神奇的开关可以让它像CPLEX一样运行。
从LP弛豫到QP弛豫是在主SCIP中不可用的东西。更接近的是NLP潜水的启发。这解决了QP松弛，然后用分数值固定或限制一些整数变量，然后再求解。它需要深入研究根节点才能找到可行的解决方案，但是由于没有太多的约束，所以有可能得到一个值为52474.45的解决方案。不幸的是，在默认设置中，启发式的运行时间不够早。如果你设置
heuristics/nlpdiving/freq = 0
heuristics/nlpdiving/freqofs = 0
heuristics/nlpdiving/maxnlpiterabs = 10000
heuristics/nlpdiving/nlpfastfail = FALSE
heuristics/nlpdiving/varselrule = f它将在根节点的末尾运行一次(要使它更早地运行，请将heur_nlpdiving.c中的heur_nlpdiving.c更改为SCIP_HEURTIMING_BEFORENODE)。
这仍然留下了一个问题，即LP松弛是无用的。因此SCIP无法在合理的时间内证明最优性。如果你也设置了一个更好的界限
constraints/nonlinear/linearizeheursol = e在此基础上，将NLP潜水启发式解中的二次函数线性化加入到LP中。这样，我在根节点的末端就有了8%的缺口。
日志：https://gist.github.com/svigerske/dfdb9e95af1f4eb386b8b05770ffde4c
虽然主SCIP中没有QP松弛，但有一个示例说明如何使用NLP松弛进行边界。您可以在示例/Relaxator下面找到这一点。有了这个，您可以更接近CPLEX正在做的事情，但这确实只是一个非常小的例子。
如果关闭LP松弛并使用NLP松弛，则在根节点(52467.99)中得到一个很好的对偶界，但不再有原始界。这是因为许多原始的启发式工作与LP松弛，基本上是现在关闭。和以前一样，我们可以使NLP潜水启发式得到一个好的原始界(52597.73)。然而，要缩小剩下的0.25%的差距似乎很困难。首先，解决NLP松弛也不是快速的，因为我们没有(也不可能)温暖启动Ipopt。第二，没有实现复杂的分支规则。
如果要为实例尝试NLP松弛器示例，请对源进行以下更改：
--- a/examples/Relaxator/src/relax_nlp.c
+++ b/examples/Relaxator/src/relax_nlp.c
@@ -32,8 +32,8 @@
#define RELAX_FREQ 1
#define NLPITERLIMIT 500 /**< iteration limit of NLP solver */
-#define FEASTOLFAC 0.01 /**< factor for NLP feasibility tolerance */
-#define RELOBJTOLFAC 0.01 /**< factor for NLP relative objective tolerance */
+#define FEASTOLFAC 1.0 /**< factor for NLP feasibility tolerance */
+#define RELOBJTOLFAC 1.0 /**< factor for NLP relative objective tolerance */
/*
* Data structures
diff --git a/src/scip/heur_nlpdiving.c b/src/scip/heur_nlpdiving.c
index 88a9237d12..bc1ab8f690 100644
--- a/src/scip/heur_nlpdiving.c
+++ b/src/scip/heur_nlpdiving.c
@@ -63,7 +63,7 @@
#define HEUR_FREQ 10
#define HEUR_FREQOFS 3
#define HEUR_MAXDEPTH -1
-#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
+#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
#define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
/* event handler properties */并设置选项
lp/solvefreq = -1
relaxing/nlp/priority = 0
relaxing/lp/freq = -1
heuristics/nlpdiving/freq = 0
heuristics/nlpdiving/freqofs = 0
heuristics/nlpdiving/maxnlpiterabs = 10000
heuristics/nlpdiving/nlpfastfail = FALSE日志：https://gist.github.com/svigerske/5ebb29c5fc6425a60b023944f5b07c04
I给人的印象是，SCIP将首先解决松弛问题，然后尝试在此基础上找到一个整数解。这不对吗？如果是的话，为什么解决办法如此遥远？
如果松弛距离很远，那么它不能很好地指导在附近寻找整数解。LP松弛由线性约束、整数变量的界和一些非常接近二次目标函数的割集组成。利用LP松弛的原始启发式找到了一个可行的解，但松弛的目标函数值在-4e6左右。然后会有一些东西更新目标函数值，以使用原始的二次函数，但这最终在2e6左右，而不是任何最优值。
其他自由/开源的解决者，可以很好地处理这个实例，并进入我的脑海，是射击和米诺陶尔。前者应该计算紧线性松弛，但我不知道它在原始界上做得有多好。后者专门用于快速解决QP放松和做QP跳水。
Stack Overflow用户
发布于 2022-11-18 15:44:54
请注意，Cplex在日志中说：
Classifier predicts products in MIQP should be linearized.即Cplex将模型线性化，并将其求解为线性MIP。如果你自己线性化模型，SCIP，在所有的可能性，也会表现得更好。
https://stackoverflow.com/questions/74455600
复制相似问题
腾讯云开发者
