c++ - SCIP:捕获“节点不可行”事件后如何解决 LP,
问题描述
我在 SCIP 中有一个工作列生成算法。由于我在生成列时包含的特定限制,可能会发生最后一轮定价确定根节点不可行(当然是 Farkas 定价器)。
如果发生这种情况,我想 1) 放宽这些特定约束,2) 解决 LP,以及 3) 重新开始定价列。
所以,我创建了自己的 EventHandler 类,捕获节点不可行事件:
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
是特定约束的当前右侧。在节点不可行证明之后巧妙地调用了这个函数,但是,我不知道如何“告诉” scip 应该解决 LP 并且应该包括可能的新列。有人可以帮我解决这个问题吗?
解决方案
当事件处理程序捕捉到NODEINFEASIBLE事件时,已经来不及改变一些关于不可行的问题,节点处理已经完成。此外,在求解过程中不允许更改约束的 rhs(因为这意味着之前所做的缩减可能无效)。
我建议如下:如果您的 Farkas 定价无法识别新列以使 LP 再次可行,则该节点将在以下声明为不可行。因此,在 Farkas 定价结束时(如果您位于根节点),您可以只对添加到要放松的约束的辅助变量进行定价,其边界对应于您的 DELTA。请注意,您需要在创建约束时将其标记为可修改。然后,由于添加了一个变量,SCIP 将触发另一轮定价。
推荐阅读
- bash - 请解释一下这个 BASH 命令“cat /y//.ssh/id_rsa.pub”
- python - 每当我输入“退出”时,它就会卡在 for 循环中,而不是像在通过原始 if 语句一样重复它
- swift - 如何在spritekit中使直线的一侧跟随触摸?
- graph - 按要打印的起始节点对路径进行分组 - Gremlin
- inheritance - 在solidity中覆盖函数,访问内部函数
- java - Java - 我很难根据 UML 图制作 2 种方法
- spring - (S3 后端不工作)Spring Config Server:无法从 AWS S3 获取配置文件内容
- r - 检查所有子列表是否具有相同长度/元素数量的方法?
- argo-workflows - 带有多个 minio 对象的 Argo 事件
- token - Tomochain 网络缺少代币