首页 文章

为什么这个混合整数程序如此低效无法解决？

提问于
浏览 次
3

我正在尝试使用GLPK和CBC来解决MIP，并且解算器都无法有效地找到解决方案 . GLPK求解器日志显示它可以快速找到一个在真实最佳值的0.1％范围内的解决方案，但是它会永远尝试找到真正的最佳值 .

我知道我可以使用 miptol arg来设置容差 - 我的问题是，这个问题会导致求解器如此低效地找到真正的最优值？我经常用稍微不同的输入来解决这个问题的版本，并且它们在不到一秒的时间内解决 .

这是file with my problem specification，它可以在GLPK中使用 glpsol --cpxlp anonymizedlp.lp 运行 .

以下是一些GLPK日志 - 您将看到在54K迭代中找到近乎最佳的MIP解决方案，然后分支树才开始增长和增长：

GLPSOL: GLPK LP/MIP Solver, v4.61
Parameter(s) specified in the command line:
 --cpxlp /var/folders/g6/fs71g8j575v4_whqythqw7h40000gn/T/11446-pulp.lp -o
 /var/folders/g6/fs71g8j575v4_whqythqw7h40000gn/T/11446-pulp.sol
Reading problem data from '/var/folders/g6/fs71g8j575v4_whqythqw7h40000gn/T/11446-pulp.lp'...
664 rows, 781 columns, 2576 non-zeros
443 integer variables, 338 of which are binary
3195 lines were read
GLPK Integer Optimizer, v4.61
664 rows, 781 columns, 2576 non-zeros
443 integer variables, 338 of which are binary
Preprocessing...
213 constraint coefficient(s) were reduced
524 rows, 652 columns, 2246 non-zeros
318 integer variables, 213 of which are binary
Scaling...
 A: min|aij| =  1.282e-01  max|aij| =  1.060e+07  ratio =  8.267e+07
GM: min|aij| =  7.573e-01  max|aij| =  1.320e+00  ratio =  1.744e+00
EQ: min|aij| =  6.108e-01  max|aij| =  1.000e+00  ratio =  1.637e+00
2N: min|aij| =  3.881e-01  max|aij| =  1.355e+00  ratio =  3.491e+00
Constructing initial basis...
Size of triangular part is 524
Solving LP relaxation...
GLPK Simplex Optimizer, v4.61
524 rows, 652 columns, 2246 non-zeros
      0: obj =  -0.000000000e+00 inf =   2.507e+02 (195)
    238: obj =  -5.821025664e+06 inf =   0.000e+00 (0)
*   363: obj =  -7.015287886e+04 inf =   0.000e+00 (0) 1
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
+   363: mip =     not found yet <=              +inf        (1; 0)
+  8606: mip =     not found yet <=  -7.015289436e+04        (8239; 0)
+ 13027: mip =     not found yet <=  -7.015289436e+04        (12660; 0)
+ 16367: mip =     not found yet <=  -7.015289436e+04        (16000; 0)
+ 19135: mip =     not found yet <=  -7.015289436e+04        (18768; 0)
+ 21523: mip =     not found yet <=  -7.015289436e+04        (21156; 0)
+ 23667: mip =     not found yet <=  -7.015289436e+04        (23300; 0)
+ 25415: mip =     not found yet <=  -7.015289436e+04        (25048; 0)
+ 27260: mip =     not found yet <=  -7.015289436e+04        (26893; 0)
+ 29055: mip =     not found yet <=  -7.015289436e+04        (28688; 0)
+ 30770: mip =     not found yet <=  -7.015289436e+04        (30403; 0)
+ 32362: mip =     not found yet <=  -7.015289436e+04        (31995; 0)
Time used: 60.0 secs.  Memory used: 14.1 Mb.
+ 33876: mip =     not found yet <=  -7.015289436e+04        (33509; 0)
+ 35338: mip =     not found yet <=  -7.015289436e+04        (34971; 0)
+ 36721: mip =     not found yet <=  -7.015289436e+04        (36354; 0)
+ 38080: mip =     not found yet <=  -7.015289436e+04        (37713; 0)
+ 39372: mip =     not found yet <=  -7.015289436e+04        (39005; 0)
+ 40601: mip =     not found yet <=  -7.015289436e+04        (40234; 0)
+ 41837: mip =     not found yet <=  -7.015289436e+04        (41470; 0)
+ 43036: mip =     not found yet <=  -7.015289436e+04        (42669; 0)
+ 44192: mip =     not found yet <=  -7.015289436e+04        (43825; 0)
+ 45350: mip =     not found yet <=  -7.015289436e+04        (44983; 0)
+ 46374: mip =     not found yet <=  -7.015289436e+04        (46007; 0)
+ 47281: mip =     not found yet <=  -7.015289436e+04        (46914; 0)
Time used: 120.0 secs.  Memory used: 20.4 Mb.
+ 48220: mip =     not found yet <=  -7.015289436e+04        (47853; 0)
+ 49195: mip =     not found yet <=  -7.015289436e+04        (48828; 0)
+ 50131: mip =     not found yet <=  -7.015289436e+04        (49764; 0)
+ 51110: mip =     not found yet <=  -7.015289436e+04        (50743; 0)
+ 52131: mip =     not found yet <=  -7.015289436e+04        (51764; 0)
+ 53092: mip =     not found yet <=  -7.015289436e+04        (52725; 0)
+ 53901: >>>>>  -7.015398607e+04 <=  -7.015289436e+04 < 0.1% (53532; 0)
+ 61014: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (57365; 3302)
+ 64785: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (61136; 3302)
+ 67671: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (64022; 3302)
+ 70330: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (66681; 3302)
+ 72613: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (68964; 3302)
+ 74731: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (71082; 3302)
Time used: 180.0 secs.  Memory used: 29.9 Mb.
+ 76685: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (73036; 3302)
+ 78508: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (74859; 3302)
+ 80220: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (76571; 3302)
+ 81852: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (78203; 3302)
+ 83368: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (79719; 3302)
+ 84815: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (81166; 3302)
+ 86126: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (82477; 3302)
+ 87358: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (83709; 3302)
+ 88612: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (84963; 3302)
+ 89821: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (86172; 3302)
+ 90989: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (87340; 3302)
+ 92031: mip =  -7.015398607e+04 <=  -7.015290061e+04 < 0.1% (88382; 3302)
linear-programming glpk integer-programming coin-or-cbc

2 回答

  • 2

    SCIP能够在几分之一秒内解决问题 . 三个启发式（锁定，移位和oneopt）产生越来越好的解决方案，直到双重界限被击中 . 它在根节点中解决，没有任何切割平面 .

    如果没有预先解决，它会删除一半的约束和一半的二进制变量，SCIP需要更长的时间来解决它 . 它仍然在根节点中解决，只添加了很少的切割平面，并且相同的启发式找到了3个整数可行解，包括最优解 .

    虽然这不能回答你关于 why 的问题，但这个问题对于GLPK或CBC来说很难解决，但是它解决了这个问题 .

    你需要有正确的启发式方法 .

    回复于
  • 3

    理论

    即使0-1 integer-programming是NP-hard，这基本上意味着，没有有效的算法（对于一般问题），除非 P=NP .

    这对你的问题意味着什么：

    这意味着，存在问题，可以建模为MIP，只包含100个变量和更少，并且您的求解器无法解决（最佳） . 让我更清楚一点：对于你给我的每个MIP求解器，我可以构造一个包含100个变量的实例，你的解算器无法解决这个问题（这可以针对每个NP难的问题来完成，尽管我们讨论的是一般的整数编程在这里） .

    接近NP难问题就是使用关于您的问题和数据的假设，以便能够删除指数级的大搜索空间（需要遍历每个NP难问题） . 但是： P!=NP 意味着，没有算法能够解决所有问题（利用特定问题的东西）（部分相关：No free lunch theorem）！结果是：所有良好的MIP解算器都是为解决常见问题而 Build 的，这对许多人来说很重要，并且由于这种良好且有用的启发式方法（例如切割平面）得以开发 .

    所以现在我们知道，所有成功的MIP解算器都是 heuristics ，经过调整可以更快地解决更常见的问题，并且在其他问题上可能会失败（再次：没有免费午餐定理） . 鉴于上述假设，这不会消失 . 尝试不同的求解器并调整不同的参数可以帮助（exagerrated：不同的参数=不同的求解器）！

    至少还有一件事要说：

    即使我们限制自己，简单的bin-packing问题，也有简单的实例和硬实例 . 其中一些将立即解决，而其他人永远不会停止 . It's very difficult to analyze which instances are hard and which are not. But these differences effect in a possibly very high variance in regards to solving-time, which is a natural consequence of NP-hardness!

    关于SAT-problem存在一些有趣的（基于统计物理学的）研究，其中研究人员发现并量化了一个相变现象，它告诉我们，在随机公式方面哪些问题（就变量/子句比而言）是困难的 .

    （一些介绍性博客文章介绍了其中一些内容：SAT Solvers: Is SAT Hard or Easy?

    练习（仅备注）

    像Gurobi和CPLEX这样的商业解决方案比CBC和co . 强大得多 . （CBC已经是一个非常好的解决方案），他们都提供免费的学术工作许可 . 但是他们遇到了这篇文章中提到的相同问题 .

    在参数方面，应该提到的是，参数一般可以调整为：

    • 快速找到一个好的解决方案（高频启发式）

    • 获得良好的界限（切割平面的高频率）

    • 证明是最佳的（我再次假设切割面的h-f，但我不确定）

    这些调整解释within this excellent paper: "Practical Guideline for Solving Difficult Mixed Integer Linear Programs，您应该阅读它 .

    也许结账 complete vs. incomplete methods （SAT-world中的例子：DPLL / CDCL与随机搜索）解决优化问题明白，为什么有些调整能更好地取得一些进展=获得更好的目标，而有些则更能证明我们达到了最低限度 .

    回复于

相关问题