- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我有一个关于 SCIP 的一般性问题。我需要使用 SCIP 作为分支和价格框架来解决我的问题,我用 C++ 编写代码,所以我使用 VRP 示例作为模板。在某些情况下,代码在分数解处停止并将其作为最佳解返回,我认为出了点问题,我是否必须设置一些参数以告诉 SCIP 寻找整数解或者我犯了一个错误,我相信它不应该停止,而是在分数解上分支,直到它到达整数解(没有任何其他负的降低成本列)。我也最优地解决了子问题!有评论吗?!
最佳答案
如果你定义你的变量是连续的并且只添加一个定价器,SCIP 将解决 master 问题到最优(即,解决受限的 master,添加改进列,解决更新的受限的 master,等等,直到不再发现了改进的列)。
SCIP 没有理由检查解是否是积分的,因为您明确表示您不介意变量的值是否是积分的(通过将它们定义为连续的)。另一方面,如果您将变量定义为整数(或二进制)类型,SCIP 将完全按照我之前描述的方式执行,但最后检查是否所有整数变量都具有整数值,如果不是则分支.
但是,您应该注意,SCIP 中的所有分支规则都对变量进行分支,即,它们采用具有小数值的整数变量并拆分其域;二进制变量将在两个子节点中固定为 0 和 1。对于分支价格法,这通常不是一个好主意:首先,它很不平衡。您有大量变量,其中只有少数最终值为 1,大多数将为 0。因此将变量固定为 1 会产生很大影响,而将其固定为 0 几乎没有影响。但更重要的是,您需要在定价问题中考虑分支决策。如果将变量固定为 0,则必须防止定价器生成禁止列的拷贝(这可能会改进 LP 解决方案,因为它是以前最优解决方案的一部分)。为此,您可能需要寻找第二(或之后的 k)最佳解决方案。由于您正在使用 SCIP 作为 MIP 解决定价问题,您可能只添加一个约束来禁止此解决方案(二元变量的逻辑(线性)或一般整数变量的边界析取(非线性))。
我建议实现您自己的分支规则,该规则考虑到您正在以更平衡且不会过多损害您的定价的方式执行分支和价格以及分支。例如,查看 Ryan&Foster 分支规则,它是具有集合分区主结构的二元问题的标准。此规则在 Binpacking 以及 SCIP 附带的 Coloring 示例中实现。
另请查看 SCIP 常见问题解答,其中有一整节都是关于分支和价格的,其中还涵盖了主题分支(特别是,如何通过约束处理程序存储和执行分支决策,这是您需要为 Ryan&Foster 分支做的事情):http://scip.zib.de/doc/html/FAQ.php
SCIP 邮件列表上也有很多关于 branch-and-price 的问题 http://listserv.zib.de/mailman/listinfo/scip/ .如果你想搜索它,你可以使用谷歌搜索“site:listserv.zib.de scip search-string”
最后推荐大家看看GCG项目:http://www.or.rwth-aachen.de/gcg/它是 SCIP 对通用分支切割和价格求解器的扩展,即,您不需要实现任何东西,您只需输入模型的原始公式,然后通过 Dantzig-Wolfe 分解和通过分支削减和价格解决。您可以提供重新制定的结构,定价问题作为 MIP 解决(您也这样做),并且还有不同的分支规则。 GCG 也是 SCIP 优化套件的一部分,可以在套件中轻松构建。
关于c++ - SCIP和分支机构和价格,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24875259/
我知道有很多关于如何编译 SCIP 的帖子,但我找不到一个可以很好地回答我的以下问题。 对于Windows,SCIP主网页提供了几个预编译的二进制文件,如下: ====================
我想使用 SCIP 作为 MIP 求解器,但我不知道如何在我的源代码中添加目标函数。我在SCIP C++示例代码中没有找到相关代码。 最佳答案 SCIP 只理解线性目标函数,即每个变量都有一个目标系数
我目前正在实现列生成(多商品流的变体)。 注意:我禁用了预求解,因为我认为原型(prototype)制作会更容易。 在这种情况下,定价工作正常:添加正确的变量,相应地修改约束等等 - 当在定价过程中没
我在一个名为 scip.set 的文件中定义了自定义设置,并将其放入 myscipdir/settings。 设置包含 limits/time = 86400 limit/memory = 61440
我正在尝试在 linux MINT 17 QIANA 上安装 SCIP 优化套件。我已经下载了 scipoptsuite-3.1.0 表格 http://scip.zib.de/并使用 ZIMPL=f
一些背景信息: 我们使用线性规划(scip/ZIMPL)来解决优化问题 因此变量在数学公式中具有下标 目前使用 mySQL/HeidiSQL 作为数据库/接口(interface) 目前,我们将变量(
我是一名硕士生,目前正在使用 SCIP 撰写论文。我论文的主要实现任务是集成一个已经用 C++ 编码并准备用于 SCIP 分支定界过程的元启发式算法,以增强我的问题的解决过程。 如何调用元启发式文件中
关于 binpacking 示例中定义的阅读器插件的问题。我在接口(interface)方法(文件reader_bpa.c)中找到了如下声明, SCIP_READERDATA* readerdata
我正在尝试使用 scip pyomo 中的求解器在 ubuntu 20.04 上,但在调用求解器时收到一条奇怪的错误消息: FileNotFoundError: [Errno 2] No such f
有人可以告诉我如何使用 SCIP 的 C++ 包装器类吗?我不知道示例中的 Makefile 是如何工作的。我尝试简单地使用命令 g++ -Wall example.cpp 但是当我这样做时,它告诉我
我正在尝试了解如何使用 NEOS Server for SCIP .我已经阅读了有关 CPLEX LP file format 的教程.但我仍然得不到任何结果。 让我们以该教程中提供的示例为例: Ma
我觉得我缺少一些非常简单明了的东西。我正在尝试解决LP后添加一个约束(使用最佳LP解决方案作为设计此约束的机制)。我通过这段代码添加它 432 SCIP_CONS * cons = nullptr;
我是 C 的新手。我只需要使用 scip 中的一个函数。我制作了一个 make 文件如下: SCIPDIR=$/Users/amin/Documents/cProgram/scipoptsuite-6
我是 LP 的新手,只是简单地使用过 PuLP在 Python 中。 为什么SCIP 3.2.1 - CPLEX 12.63之间有速度差异和 CPLEX 12.6.3 ? SCIP 不是仍然使用 CP
我通过 Jni 接口(interface)使用 Java api 中的 Scip 求解器。 我想将我的 lp 模型转储到文件中。 为此,原生API中有以下c方法 extern SCIP_RETCODE
我在 SCIP 中有一个工作列生成算法。由于我在生成列时包含的特定约束,最后一轮定价可能会确定根节点不可行(当然是通过 Farkas 定价器)。 如果发生这种情况,我想 1) 放宽这些特定限制,2)
我想将 SCIP 优化套件 6.0.2 与 Python 接口(interface) PySCIPOpt 一起使用,并启用调试。我在 Linux - Ubuntu 18.04LTS 上工作,没有 su
我最近开始使用 Ortools 来解决 MILP 问题。 我尝试过 CBC,但它不提供全局最优解决方案,仅提供局部最优解决方案(似乎有 https://groups.google.com/forum/
有谁知道在处理典型的 MILP(混合整数线性规划)时,Java 的这 2 个求解器(Oj 算法)和 Python 的 SCIP 在性能方面如何相互关联(如:哪个最快) ) 问题?乍一看,我似乎无法在网
我试图在 SCIP 中的 MILP 的约束矩阵中获取变量的系数。我一直在想的是遍历变量出现的所有约束并以某种方式获得系数(我不确定如何)。但是有没有办法获得 std::vector 中的所有系数?通过
我是一名优秀的程序员,十分优秀!