意想不到的改善与零目标函数一个LP文件
回答
大家好！
我一直在试图解决一个非常大的待定LP格式的二进制线性系统。因此,目标函数为零(或常数)。因此我只是在寻找一个可行的解决方案。到目前为止Gurobi确实在努力寻找一个解决方案(我还没有一个解决方案)。我甚至试着调优一个较小的相关问题和使用这些参数。想到我,当目标函数为零,也许Gurobi运行‘盲’,所以我试着考虑人为地添加一个目标函数的一种方式。现在我的问题我知道,当找到一个可行的解决方案然后变量的总和等于一个数n .所以我编辑目标函数最大化(或减少)的所有变量的总和。当我把这个变化对小问题(N = 66)发现的解决方案是非常快(当然,客观价值= 66)。我正在尝试这种方法更大的问题。我的问题是:为什么这样一个简单的改变目标函数导致降低解决方案的时间吗? I called this change 'artificial' because the equality constraints actually imply this condition, so I'm not actually telling Gurobi anything new.
谢谢你,马库斯。
-
JaromiłNajmanGurobi员工
你好马库斯,
为什么这样一个简单的改变目标函数导致降低解决方案的时间吗?
Gurobi能够使用目标函数的方向更好的“引导”,通过搜索空间和更容易找到可行的解决方案。从而提供一个非平凡的目标函数经常帮助当一只希望找到一个可行的点。
因为你正在寻找可行点,你可能会想尝试“不放松启发式”通过设置参数NoRelHeurTime和实验MIPFocus,启发式,rin参数。您可能还感兴趣看约束编程。
最好的问候,
Jaromił0 -
嗨Jaromił,
谢谢你的回复。我不是很了解Gurobi所以我想知道如果你能扩大你提到一些可能的值的参数。
首先一点上下文,以防它帮助。正如我所提到的在我上一篇我解决纯二进制LP问题。7733年有1572516个变量和等式约束和目标函数,除非我决定添加一个如之前所述)。所有的变量是二进制。
你建议设置NoRelHeurTime参数。文档没有manbet体育手机客户端说很多参数。google之前的帖子我发现一篇文章,建议设置2个小时,试图得到一个可行的解决方案。现在我运行问题。(我该坚持零目标函数或使用“人工”给了我加速在较小的问题?)我也使用MIPFocus = 1,似乎是设置“找到一个好的质量可行的解决方案”。我不确定其他参数,虽然我使用方法= 3因为别人认为,我的问题似乎并没有受益于增加更多的线程吗?
这个问题我已经选择好参数设置是它需要Gurobi很长一段时间我的问题。非常缓慢的在得到“根放松”,然后花很长时间在零节点。我试过各种设置和没有解决方案经过一周的运行时。
任何建议,我们将不胜感激。
谢谢你！
马库斯。
0 -
JaromiłNajman
你好马库斯,
首先一点上下文,以防它帮助。正如我所提到的在我上一篇我解决纯二进制LP问题。7733年有1572516个变量和等式约束和目标函数,除非我决定添加一个如之前所述)。所有的变量是二进制。
这是一个非常大的问题。因此,毫不奇怪,找到一个可行解点可能需要很长时间。你能分享的第一个~ 20行日志文件?
只因为你感兴趣的一个可行的解决方案,您应该设置参数SolutionLimit= 1这将使Gurobi终止一旦第一个找到可行的解决方案。
你建议设置NoRelHeurTime参数。文档没有manbet体育手机客户端说很多参数。google之前的帖子我发现一篇文章,建议设置2个小时,试图得到一个可行的解决方案。现在我运行问题。(我该坚持零目标函数或使用“人工”给了我加速在较小的问题?)
没有放松启发式搜索可行点之前解决根节点放松。它经常执行如果根放松是昂贵的解决。第一阶段的启发式显示“远”放松成为可行的,而第二个阶段然后列表找到可行的解决方案。的参数NoRelHeurTime设置的秒数人愿意花在这种启发式。既然你已经观察到提供一个目标函数性能好处,我将坚持这种方法,并提供一个简单的目标函数。
我也使用MIPFocus = 1,似乎是设置“找到一个好的质量可行的解决方案”。
设置MIPFocus= 1应该是正确的选择,因为你感兴趣的一个可行解。不过,有时它可能是更好的设置MIPFocus= 2或3但必须测试。
我不确定其他参数,虽然我使用方法= 3因为别人认为,我的问题似乎并没有受益于增加更多的线程吗?
方法= 3 Gurobi利用原始对偶单纯形和障碍并行算法解决根节点时放松。如果你的根节点放松迅速解决,那么通常可以忽略的参数。MIPs,更多的线程通常帮助更多的如果B&B树很大。
的启发式参数控制时间为可行的启发式。在你的情况下,你可以设置它为1 Gurobi花最大的努力寻找可行点。
这个问题我已经选择好参数设置是它需要Gurobi很长一段时间我的问题。非常缓慢的在得到“根放松”,然后花很长时间在零节点。我试过各种设置和没有解决方案经过一周的运行时。
任何建议,我们将不胜感激。
你应该制定一个较小的版本的模型,并使用这个小版本。然后您可以使用Gurobi的自动参数调优工具寻找合适的参数较小的版本。考虑到优化模型的规模和复杂性,它可能需要运行的调优工具几天找到好的参数。
最好的问候,
Jaromił0 -
嗨Jaromił,
天哪,有很多尝试。我有一个小问题,但它似乎很迅速的解决,不遭受同样的根节点的延误。我试着调小模型(不是2天),但我不确定这些参数也将如何工作的大问题。我将尝试一些你的建议,谢谢。我有附加日志的最后3天运行时我的大问题…
谢谢你！
马库斯。
marcusgarvie@Marcuss-MacBook-Pro LPfiles % gurobi_cl ResultFile = subregion6_alt。= 3 subregion6_alt.lp溶胶的方法Gurobi优化器版本9.5.0构建v9.5.0rc5 (mac64[机构])Obj: 7733行、1372296列,1372296 0线程数:10个物理核心,10个逻辑处理器,使用多达10个线程优化模型与7733行、1372296列和50774952 0连续变量类型:0,1372296整数(1372296二进制)Presolve删除96行和0列(Presolve时间= 6 s)……Presolve删除96行和97704列(Presolve时间= 10 s)……Presolve删除96行和97704列(Presolve时间= 15秒)…Presolve删除96行和97704列(Presolve时间= 20 s)……Presolve删除96行和97704列(Presolve时间= 25 s)……Presolve删除504行和97704列(Presolve时间= 30年代)……Presolve删除504行和97704列(Presolve时间= 35 s)……Presolve删除504行和97704列(Presolve时间= 40年代)……Presolve删除504行和97704列(Presolve时间= 45 s)……Presolve删除504行和97704列(Presolve时间= 51 s)……Presolve删除504行和97704列Presolve时间:52.23秒Presolved: 7229行、1274592列,1274592 0连续变量类型:0,1274592整数(1274592二进制)并发LP优化器:原始单纯形,对偶单纯形和障碍只显示屏障日志……根屏障日志……订购时间:0.03秒障碍统计:AA的新西兰:1.412 e + 06新西兰的因素:3.275 e + 06(大约500 MB的内存)因素行动:2.402 e + 09年每迭代(小于1秒)线程:8客观的残余Iter原始对偶原始双惠0 8.56184000 2.09000000 e + e + 04 02 7.52 e + 02 7.52 e-14 2.50 e 03 85年代1 9.91639026 2.19176780 e + e + 02年02年6.89 2.68 8.88 e + 00 e-16 e-05 85年代2 2.47693217 3.41 2.16687891 e + e + 02年02 e-01 9.58 e-16 3.97 e-06 86年代3 2.09000000 6.33 2.09747374 e + e + 02年02 e-14 8.88 e-16 2.93 e-07 86年代4 2.09000000 5.71 2.09000747 e + e + 02年02 e-14 8.88 e-16 2.93平台以及87年代5 2.09000000 1.67 2.09000000 e + e + 02年02 e-13 8.88 e-16 2.95 e-16 87年代障碍解决模型5迭代和87.37秒(196.13单位)最优目标2.09000000 e + 0297年代建筑初始交叉基础100年代建筑初始交叉基础105年代建筑初始交叉基础110年代建筑初始交叉基础根交叉日志……1350年变量添加到115年代交叉基础4140年变量添加到120年代交叉基础剩余289 DPushes DInf 0.0000000 e + 00 122年代0 DPushes剩余DInf 0.0000000 e + 00 123年代剩余1 PPushes PInf 0.0000000 e + 00 123年代0 PPushes剩余PInf 0.0000000 e + 00 123年代按阶段完成:Pinf 0.0000000 e + 00, Dinf 2.9062210 e-09 123年代根单工日志……迭代目标原始Inf。双正。128年2.0900000 e + 02年0.000000 0.000000 e + e + 00 00 123年代128年2.0900000 e + 02年0.000000 0.000000 e + e + 00 00 124年代解决与障碍根放松:目标2.090000 e + 02 128迭代,58.47秒(97.70单位)当前节点节点| |客观界限|工作Expl Unexpl | Obj深度IntInf | |现任BestBd差距/节点时间0 0 0 4736 - 209.00000 - 209.00000 - 416年代0 0 0 4924 - 209.00000 - 209.00000 - 2605年代0 0 0 4924 - 209.00000 - 209.00000 - 3232年代0 0 0 4921 - 209.00000 - 209.00000 - 5966年代0 0 0 4919 - 209.00000 - 209.00000 - 7832年代0 0 0 4927 - 209.00000 - 209.00000 - 10164年代0 0 0 4922 - 209.00000 - 209.00000 - 11850年代0 0 0 4916 - 209.00000 - 209.00000 - 13135年代0 0 0 4924 - 209.00000 - 209.00000 - 14284年代0 0 0 4930 - 209.00000 - 209.00000 - 16081年代0 0 0 4942 - 209.00000 - 209.00000 - 17815年代0 0 0 5101 - 209.00000 - 209.00000 - 18628年代0 0 0 4742 - 209.00000 - 209.00000 - 19445年代0 0 0 5053 - 209.00000 - 209.00000 - 20425年代0 0 0 4970 - 209.00000 - 209.00000 - 21358年代0 0 0 4928 - 209.00000 - 209.00000 - 23743年代0 0 0 4947 - 209.00000 - 209.00000 - 25540年代0 0 0 5029 - 209.00000 - 209.00000 - 27184年代0 0 0 5012 - 209.00000 - 209.00000 - 28992年代0 0 0 5100 - 209.00000 - 209.00000 - 30796年代0 0 0 5027 - 209.00000 - 209.00000 - 31820年代0 0 0 5106 - 209.00000 - 209.00000 - 33856年代0 0 0 5106 - 209.00000 - 209.00000 - 35385年代0 2 0 5106 - 209.00000 - 209.00000 - 47056 s4981 - 209.00000 - 209.00000 - 1 13027 47493年代3 6034 5041 - 209.00000 - 209.00000 - 2 48181年代7 16 209.00000 3 5036 - 209.00000 - 7034 49341年代26 4984 - 209.00000 - 209.00000 - 4 8094 53714年代25 36 5054 - 209.00000 - 209.00000 - 5 13888 54131年代35 46 5045 - 209.00000 - 209.00000 - 5 11531 54484年代45 56 209.00000 6 5050 - 209.00000 - 10120 54749年代55 73 5033 7 209.00000 - 209.00000 - 9030 55083年代72 84 209.00000 8 5049 - 209.00000 - 7471 55489年代83 98 5062 9 209.00000 - 209.00000 - 7297 55856年代97 149 209.00000 5072 - 209.00000 - 6780 56843年代148 243 209.00000 5077 - 209.00000 - 6148 61607年代246 438 209.00000 19 5053 - 209.00000 - 5821 67016年代447 659 209.00000 28 4953 - 209.00000 - 5985 72875年代670 877 209.00000 45 4831 - 209.00000 - 6019 80608年代888 1014 61 - 209.00000 4727 - 209.00000 - 6459 91951年代1029 1151 72 - 209.00000 4616 - 209.00000 - 7096 117062年代1172 1280 94 - 209.00000 4378 - 209.00000 - 7912 126992年代1305 1344 108 - 209.00000 4334 - 209.00000 - 8493 134686年代1387 1446 115 - 209.00000 4306 - 209.00000 - 8425 143648年代1503 1635 128 - 209.00000 4222 - 209.00000 - 9253 156614年代1704 1785 144 - 209.00000 4005 - 209.00000 - 10259 163621年代1860 1916 154 - 209.00000 3814 - 209.00000 - 11293 171141年代1999 2037 169 - 209.00000 3670 - 209.00000 - 11833 179167年代2128 2132 173 - 209.00000 3548 - 209.00000 - 12251 235864年代0 -
嗨Jaromił,
只是一个更新。较小的模型我有很长一段路,也试着调优参数。你帮助我找到以下参数的选择了最大的改进解决时间:
设置参数SolutionLimit值1
设置参数方法值4
设置参数启发式值1
设置参数MIPFocus值1(NoRelHeurTime参数似乎并不做太多)。我也买了一个新MacBookPro M1马克斯芯片,加速的东西。在我的旧笔记本电脑默认参数的小模型采取31分钟来解决。现在使用新的参数集,修改后的目标函数,和新的笔记本电脑,我刚得到一个解决方案在21秒!我运行这个新设置的大问题,希望最终会导致一个解决方案。
谢谢你！
马库斯。
0 -
JaromiłNajman
哇!这确实是一个巨大的进步。我希望它还帮助的大问题。
最好的问候,
Jaromił0
请登录留下你的评论。
评论
6个评论