1

我正在尝试编写一个新的 scip 放松处理程序。对于每个节点，我想用我想出的值来更新它的下限和上限。然后我希望 scip 在其求解过程中自然地使用这些更好的界限。但我得到了奇怪的结果。

我的问题是如何更新分支和边界中当前节点的下限和上限？

在我的关系处理程序中，我有这个调试代码：

double l = -100;
double u = -15;
cout << "SCIP STAGE " << (scip->set->stage) << std::endl;
cout << SCIPgetNNodes(scip) << " min scip  " << SCIPgetLocalLowerbound(scip) << " <= " << SCIPgetUpperbound(scip) << endl;
cout << SCIPgetNNodes(scip) << " min my b  " << l             << " <= " << u << endl;

SCIPupdateLocalLowerbound(scip, l);

cout << SCIPgetNNodes(scip) << " min scip  " << SCIPgetLocalLowerbound(scip) << " <= " << SCIPgetUpperbound(scip) << endl;

输出是

SCIP STAGE 9
1 min scip  -1e+14 <= -100000
1 min my b  -100 <= -15
1 min scip  1e+20 <= -10000

scip stage 9 是 SCIP_STAGE_SOLVING，看起来不错。

带有“scip”的行是节点的 scip 边界。带有“my b”的中间线是指我的新界限。

我SCIPupdateLocalLowerbound(scip, -10)在当前下限为 -1e14 时调用，因此该调用后新的下限应为 10。但是，下限变为 1e20，这是一个巨大的错误。

我希望这SCIPupdateLocalLowerbound(scip, -10);会使SCIPgetLocalLowerbound(scip)return -10not 1e20。我究竟做错了什么？

另外，我没有看到一个名为 的函数SCIPupdateLocalUpperbound()，那么如何更新节点的上限？

编辑 2015/03/13 感谢 Gregor 解释 scip 的那一部分。我还有一个小问题。

为了完整起见，我将本地节点的最小化问题的下限设置为

SCIPupdateLocalLowerbound(scip, l)

我正在设置最小化问题的全局上限

if ( newUpperBound < scip->primal->upperbound)
    {
        SCIPprimalSetUpperbound(scip->primal, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->transprob, scip->tree, scip->lp, newUpperBound);
    }

SCIPprimalSetUpperbound 的第二个参数采用

BMS_BLKMEM*           blkmem,             /**< block memory */

我正在传递一个在 scip->mem 中找到的 blkmem。这是正确的，还是我应该传递一些其他干净的块内存？我是否覆盖了一些重要的东西？

编辑 2015/03/19

现在我在设置目标函数时不明白输出。提醒一下（对我来说），原来的主问题是最大化问题，而 scip 的转换问题是最小化问题。如果我看一下结果

cout << SCIPgetNNodes(scip) << " min scip  " << SCIPgetLocalLowerbound(scip) << " <= " << SCIPgetUpperbound(scip) << endl;
cout << SCIPgetNNodes(scip) << " min my b  " << newLowerBound             << " <= " << newUpperBound << endl;


cout << "SCIPgetObjlimit " << SCIPgetObjlimit(scip) << endl;
cout << "SCIPretransformObj " << SCIPretransformObj(scip,newUpperBound) << endl;

输出是：

7 min scip  -1.10142e+08 <= 100000
7 min my b  -1.37597e+08 <= 2.11197e+08
SCIPgetObjlimit -1.97183e+08
SCIPretransformObj -2.11197e+08

所以 scip 的这个节点的最小值的界限是 -1.10142e+08 <= 100000，我这个节点的最小值的界限是 -1.37597e+08 <= 2.11197e+08，在这种情况下更糟。

为什么 SCIPgetObjlimit = -1.97183e+08？为什么不是-100000？如果 100000 是转换空间中的当前上限（最小化），那么 -100000 是我原始问题的当前全局下限。

4

1 回答 1

2

虽然下界是每个节点特有的局部属性（因为它们通常是从该节点的最优 LP 松弛目标推断出来的，或者如果它们已经被求解，则上界来自原始解决方案问题，因此在全球范围内有效。

从 SCIP 的角度来看，下限大于或等于全局上限的每个节点都可以被修剪，并且这些节点得到 +infinity（即，默认 SCIP 设置的 1e+20）作为下限。仔细查看这些值会发现您强制修剪此节点，因为当您将本地边界设置为l=-100时，全局边界为 -100000 ，因此此处旨在执行 SCIP 的行为。

编辑 关于您问题的第二部分：实际上，从某种意义上说，从primal.h起源于插件（例如您的松弛器）中，实际上是禁止使用诸如 的方法的。原因正是您现在面临的问题，涉及您不需要关心的 SCIP 内部。SCIPprimalSetUpperBound()

我建议通过SCIPsetObjlimit(). 请注意，必须在原始空间中给出客观限制，即。如果您想在之前通过上限，请使用ub = SCIPretransformObj(scip, ub)and after SCIPsetObjlimit(scip, ub)。

编辑原始问题和转换问题中的原始界限：

  1. SCIPgetUpperBound(scip)：转换问题空间中的当前上限，最佳解决方案目标的最小值和（转换后的）目标限制
  2. SCIPgetPrimalBound(scip)：SCIPgetUpperBound(scip)原始问题空间中的值，即。在考虑最佳解决方案和用户目标限制（如果有）的情况下。
  3. SCIPgetObjlimit(scip)：用户设置的目标限制值，不考虑原始解决方案目标。

我假设您设置了一个客观的限制，但 SCIP 找到了一个更好的原始解决方案。

于 2015-03-12T09:06:42.033 回答