如何更新节点的下限和上限

Question

我正在尝试编写一个新的 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 第 9 阶段是 SCIP_STAGE_SOLVING，看起来不错。

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

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

我预计 SCIPupdateLocalLowerbound(scip, -10); 会使 SCIPgetLocalLowerbound(scip) return -10 而不是 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

现在我不明白设置 objective 函数时的输出。提醒一下（对我来说），原来的master问题是最大化问题，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 是转换后的 space（最小化）中的当前上限，那么 -100000 是我当前针对原始问题的全局下限。

Answer 1

虽然下界是每个节点的局部属性特殊（因为它们通常是从该节点的最佳 LP 松弛 objective 推断出来的，或者节点子下界，以防它们已经解决，上限来自您问题的原始解决方案，因此在全球范围内有效。

从SCIP的角度来看，下限大于或等于全局上限的每个节点都可以被修剪，并且这样的节点得到+无穷大（即1e+20，默认SCIP设置）作为下限.仔细查看这些值会发现您强制修剪该节点，因为当您将本地绑定设置为 l=-100 时全局绑定为 -100000，因此 SCIP 的行为是有意的这里。

编辑关于你问题的第二部分：实际上 forbidden 在某种意义上使用诸如 SCIPprimalSetUpperBound() 之类的方法，它源自 primal.h，来自插件，例如，你的放松器。原因正是你现在面临的问题，关于你不需要关心的 SCIP 内部。

我建议通过 SCIPsetObjlimit() 设置 objective 限制。请注意，必须在原始 space 中给出 objective 限制，即。如果你想之前通过上限，请使用 ub = SCIPretransformObj(scip, ub) 然后使用 SCIPsetObjlimit(scip, ub).

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

SCIPgetUpperBound(scip)：转换问题的当前上限 space、最佳解的最小值 objective 和（转换的）objective 极限
SCIPgetPrimalBound(scip)：原题space中SCIPgetUpperBound(scip)的值，即。在考虑最佳解决方案和用户 objective 限制（如果有）的情况下。
SCIPgetObjlimit(scip)：用户设置的objective极限值，not respecting primal solution objectives.

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

如何更新节点的下限和上限

how to update a node's lower and upper bound

scip