为什么这个混合整数程序的求解效率如此之低？
Why is this mixed integer program so inefficient to solve?
我正在尝试使用 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)
理论
甚至0-1 integer-programming is NP-hard，这基本上意味着，没有有效的算法（对于一般问题），除非P=NP。
这对您的问题意味着什么：
这意味着，存在可以建模为 MIP 的问题，仅包含 100 个或更少的变量，并且您的求解器无法解决它（优化）。让我更清楚一点：对于你给我的每个 MIP 求解器，我可以构造一个可能包含 100 个变量的实例，而你的求解器无法解决（这可以用于每个 NP-hard 问题，尽管我们谈论的是一般问题此处为整数规划）。
处理 NP-hard 问题就是使用关于您的问题和数据的假设，以便能够修剪掉指数级大搜索-space（每个 NP-hard 问题都需要遍历它).但是：P!=NP 意味着，对于所有一般问题（部分相关：No free lunch theorem），没有算法可以做到这一点（利用特定于问题的东西）！结果：所有优秀的 MIP 求解器都是为解决常见问题而构建的，这对许多人来说很重要，并且正是由于这种良好且有用的启发式方法（例如切割平面）才得以开发。
所以现在我们知道，所有成功的 MIP 求解器都是 启发式算法，经过调整可以更快地解决更常见的问题，但在其他问题上可能会失败（同样：没有免费的午餐定理).鉴于上述假设，这不会消失。尝试不同的求解器和调整不同的参数会有所帮助（夸张的：不同的参数 = 不同的求解器）！
至少还有一件事要说：
即使我们将自己限制在，比方说，一个简单的装箱问题，也有简单的实例和困难的实例。其中一些会立即解决，而另一些则永远不会停止。 很难分析哪些实例困难哪些不困难。但是这些差异可能导致求解时间的方差非常大，这是 NP 硬度的自然结果！
关于 SAT-problem 存在一些有趣的（基于统计物理学的）研究，研究人员发现并量化了一种 相变现象 ，它告诉我们，什么关于随机公式的问题（就 variable/clause 比率而言）很难。
（一些介绍性博客条目涵盖了其中的一些内容：SAT 求解器：SAT 是难还是简单？
实践（仅备注）
像 Gurobi 和 CPLEX 这样的商业求解器比 CBC 和 co 强大得多。 （并且 CBC 已经是一个非常好的求解器）并且它们都为学术工作提供免费许可。但是他们遇到了 post.
中提到的相同问题
在参数方面，要提一下，一般的参数可以调整为：
- 快速找到好的解决方案（启发式的高频）
- 获得良好的边界（切割平面的高频）
- 证明最优（我再次假设切割平面的 h-f，但我不确定）
对这些调音方式进行了解释 within this excellent paper: "Practical Guideline for Solving Difficult Mixed Integer Linear Programs，您应该阅读它。
也许还可以查看 完整方法与不完整方法（SAT 世界中的示例：DPLL/CDCL 与随机搜索）来解决优化问题以了解为什么进行一些调整更擅长取得一些进步=变得更好objective，而其他人更擅长证明我们达到了最低要求。
SCIP 可以在几分之一秒内解决问题。三种启发式（锁定、移位和 oneopt）产生越来越好的解决方案，直到达到双重界限。它在根节点中解决，没有任何切割平面。
如果没有预求解，它会删除一半的约束和一半的二进制变量，SCIP 需要更长的时间来解决它。它仍然在根节点中解决，只添加了很少的切割平面，同样的启发式算法找到了 3 个整数可行解，包括最优解。
虽然这并没有回答你关于为什么这个问题对于 GLPK 或 CBC 来说很难的问题，但至少对于 SCIP 来说并不难，它也是开源的并且对学术界免费.很可能其中一种启发式算法未在其他求解器中实现，因为在 SCIP 中禁用启发式算法会使找到解决方案变得更加困难 - 分支根本无法解决此问题。
你需要有正确的启发式。
我正在尝试使用 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)
理论
甚至0-1 integer-programming is NP-hard，这基本上意味着，没有有效的算法（对于一般问题），除非P=NP。
这对您的问题意味着什么：
这意味着，存在可以建模为 MIP 的问题，仅包含 100 个或更少的变量，并且您的求解器无法解决它（优化）。让我更清楚一点：对于你给我的每个 MIP 求解器，我可以构造一个可能包含 100 个变量的实例，而你的求解器无法解决（这可以用于每个 NP-hard 问题，尽管我们谈论的是一般问题此处为整数规划）。
处理 NP-hard 问题就是使用关于您的问题和数据的假设，以便能够修剪掉指数级大搜索-space（每个 NP-hard 问题都需要遍历它).但是：P!=NP 意味着，对于所有一般问题（部分相关：No free lunch theorem），没有算法可以做到这一点（利用特定于问题的东西）！结果：所有优秀的 MIP 求解器都是为解决常见问题而构建的，这对许多人来说很重要，并且正是由于这种良好且有用的启发式方法（例如切割平面）才得以开发。
所以现在我们知道，所有成功的 MIP 求解器都是 启发式算法，经过调整可以更快地解决更常见的问题，但在其他问题上可能会失败（同样：没有免费的午餐定理).鉴于上述假设，这不会消失。尝试不同的求解器和调整不同的参数会有所帮助（夸张的：不同的参数 = 不同的求解器）！
至少还有一件事要说：
即使我们将自己限制在，比方说，一个简单的装箱问题，也有简单的实例和困难的实例。其中一些会立即解决，而另一些则永远不会停止。 很难分析哪些实例困难哪些不困难。但是这些差异可能导致求解时间的方差非常大，这是 NP 硬度的自然结果！
关于 SAT-problem 存在一些有趣的（基于统计物理学的）研究，研究人员发现并量化了一种 相变现象 ，它告诉我们，什么关于随机公式的问题（就 variable/clause 比率而言）很难。
（一些介绍性博客条目涵盖了其中的一些内容：SAT 求解器：SAT 是难还是简单？
实践（仅备注）
像 Gurobi 和 CPLEX 这样的商业求解器比 CBC 和 co 强大得多。 （并且 CBC 已经是一个非常好的求解器）并且它们都为学术工作提供免费许可。但是他们遇到了 post.
中提到的相同问题在参数方面，要提一下，一般的参数可以调整为：
- 快速找到好的解决方案（启发式的高频）
- 获得良好的边界（切割平面的高频）
- 证明最优（我再次假设切割平面的 h-f，但我不确定）
对这些调音方式进行了解释 within this excellent paper: "Practical Guideline for Solving Difficult Mixed Integer Linear Programs，您应该阅读它。
也许还可以查看 完整方法与不完整方法（SAT 世界中的示例：DPLL/CDCL 与随机搜索）来解决优化问题以了解为什么进行一些调整更擅长取得一些进步=变得更好objective，而其他人更擅长证明我们达到了最低要求。
SCIP 可以在几分之一秒内解决问题。三种启发式（锁定、移位和 oneopt）产生越来越好的解决方案，直到达到双重界限。它在根节点中解决，没有任何切割平面。
如果没有预求解，它会删除一半的约束和一半的二进制变量，SCIP 需要更长的时间来解决它。它仍然在根节点中解决，只添加了很少的切割平面，同样的启发式算法找到了 3 个整数可行解，包括最优解。
虽然这并没有回答你关于为什么这个问题对于 GLPK 或 CBC 来说很难的问题，但至少对于 SCIP 来说并不难，它也是开源的并且对学术界免费.很可能其中一种启发式算法未在其他求解器中实现，因为在 SCIP 中禁用启发式算法会使找到解决方案变得更加困难 - 分支根本无法解决此问题。
你需要有正确的启发式。