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

how to update a node's lower and upper bound

我正在尝试编写一个新的 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 是我当前针对原始问题的全局下限。

虽然下界是每个节点的局部 属性 特殊(因为它们通常是从该节点的最佳 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).

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

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

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