SCIP：捕获 'node infeasibility' 事件后如何解决 LP，

Question

我在 SCIP 中有一个工作列生成算法。由于我在生成列时包含的特定约束，最后一轮定价可能会确定根节点不可行（当然是通过 Farkas 定价器）。

如果发生这种情况，我想 1) 放宽这些特定限制，2) 解决 LP，以及 3) 重新开始定价列。

所以，我创建了自己的 EventHandler class，捕捉节点不可行性事件：

SCIP_DECL_EVENTINITSOL(EventHandler::scip_initsol)
{
    SCIP_CALL( SCIPcatchEvent(scip_, SCIP_EVENTTYPE_NODEINFEASIBLE, eventhdlr, NULL, NULL));
    return SCIP_OKAY;
}

以及相应的 scip_exec 虚拟方法：

SCIP_DECL_EVENTEXEC(EventHandler::scip_exec)
{
  double cur_rhs = SCIPgetRhsLinear(scip_, *d_varConsInfo).c_primal_obj_cut);
  SCIPchgRhsLinear (scip_, (*d_varConsInfo).c_primal_obj_cut, cur_rhs + DELTA);

  return SCIP_OKAY;     
}

其中(*d_varConsInfo).c_primal_obj_cut是要改变的具体约束，DELTA是全局参数，cur_rhs是当前具体约束的右手边。这个函数在节点不可行性证明之后被巧妙地调用，但是，我不知道如何 'tell' scip 应该解析 LP 并且应该包含可能的新列。有人可以帮我解决这个问题吗？

Answer 1

也许你应该看看 SCIP 的 PRICERFARKAS 方法 (https://scip.zib.de/doc/html/PRICER.php#PRICER_FUNDAMENTALCALLBACKS)。

If the current LP relaxation is infeasible, it is the task of the pricer to generate additional variables that can potentially render the LP feasible again. In standard branch-and-price, these are variables with positive Farkas values, and the PRICERFARKAS method should identify those variables.

Answer 2

当事件处理程序捕获到 NODEINFEASIBLE 事件时，已经来不及改变问题的不可行性，节点处理已经完成。此外，您不得在求解过程中更改约束的 rhs（因为这意味着之前所做的归约可能无效）。

我建议如下：如果您的 Farkas 定价无法识别新列以使 LP 再次可行，则该节点将在以下声明为不可行。因此，在 Farkas 定价结束时（如果您位于根节点），您可以只为添加到要放松的约束的辅助变量定价，其边界对应于您的 DELTA。请注意，您需要在创建约束时将其标记为可修改。然后，由于添加了一个变量，SCIP 将触发另一轮定价。

SCIP：捕获 'node infeasibility' 事件后如何解决 LP，

SCIP: How to resolve LP after catching a 'node infeasibility' event,

c++

linear-programming

scip