为什么这个混合整数规划问题求解效率如此低？

Question

我正在尝试使用GLPK和CBC解决一个混合整数规划问题，但两个求解器都不能有效地找到解。GLPK求解器日志显示它快速找到了一个距离真实最优解仅相差0.1%的解，但随后花费很长时间寻找真正的最优解。

我知道可以使用miptol参数设置容限值，我的问题是，什么原因导致求解器在查找真正最优解方面效率如此低下？我经常解决类似输入略有不同的问题版本，并且它们都可以在不到一秒钟内解决。

这里有一个包含我的问题说明的文件，可以在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)

- thomaskeefe

Answer 1

SCIP 能够在几分之一秒内解决问题。三个启发式算法（锁定、移动和oneopt）生成越来越好的解，直到达到双重上界。它在根节点中解决，没有任何割平面。

如果不进行预处理，即删除一半的约束和二进制变量，SCIP 需要更长的时间来解决它。它仍然在根节点中解决，只添加了非常少的割平面，并且相同的启发式算法找到 3 个整数可行解，包括最优解。

虽然这并没有回答你关于为什么 GLPK 或 CBC 很难解决这个问题的问题，但至少对于 SCIP 来说并不困难，而 SCIP 也是开源的，学术界免费使用。最有可能的是其他求解器中没有实现其中一个启发式算法，因为禁用 SCIP 中的启发式算法会使它更难找到解决方案 - 分支策略无法解决此问题。

你需要正确的启发式算法。

- mattmilten

Answer 2

理论

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

那对于你的问题意味着什么：

这意味着，有些问题可以建模为MIP，只包含100个或更少的变量，但你的求解器无法解决它（到最优解）。让我更清楚地解释一下：对于你给我的每个MIP求解器，我都可以构造一个包含可能100个变量的实例，你的求解器无法解决（尽管我们在这里谈论的是一般整数规划问题）。

接近NP难问题的关键在于利用您的问题和数据的假设，以便能够修剪指数级大的搜索空间（对于每个NP难问题都需要遍历）。但是：P！= NP意味着没有算法可以为所有问题一般地利用问题特定的东西来解决这个问题（部分相关：无免费午餐定理）！ 结果是：所有优秀的MIP求解器都是为解决常见问题而构建的，这些问题对许多人很重要，并且因此开发了好的有用的启发式方法（例如切割平面）。

现在我们知道，所有成功的MIP求解器都是启发式方法，调整为更快地解决常见问题，并可能在其他问题上惨败（再次强调：无免费午餐定理）。在以上假设的基础上，这种情况不会消失。尝试使用不同的求解器和调整不同的参数可以帮助解决问题（夸张的说：不同的参数=不同的求解器）！

至少还有一件事要说：

即使我们仅限于简单的装箱问题，也存在易解和难解的实例。其中一些会立即解决，而其他一些则永远无法停止。很难分析哪些实例是困难的，哪些不是。但这些差异会导致解决时间可能非常高，这是NP难度的自然结果！ 有一些基于统计物理学的有趣研究关于SAT问题，研究人员发现并量化了一个相变现象，告诉我们在随机公式方面的变量/子句比率中哪些问题是难以解决的。

（一些介绍性博客文章涵盖了其中的一些内容：SAT求解器：SAT难还是容易？

练习（仅备注）

商用求解器如Gurobi和CPLEX比CBC等求解器要强大得多（而且CBC已经是一个非常好的求解器），它们都为学术工作提供免费许可证。但是它们也会遇到本帖中提到的相同问题。

就参数而言，应该提到，通常可以调整参数来：

- 快速找到一个好的解（高启发式频率） - 获得良好的界限（高割平面频率） - 证明最优（我假设再次使用高割平面频率，但不确定）

这些类型的调整在这篇优秀论文 "Practical Guideline for Solving Difficult Mixed Integer Linear Programs"中有详细解释，你应该阅读它。

也许还可以查看完整与不完整方法（SAT世界中的示例：DPLL / CDCL与随机搜索），以解决优化问题，以了解为什么某些调整更好于取得一些进展 = 获得更好的目标，而其他则更适用于证明我们达到了最小值。

- sascha