调试帮助：Python PuLP 中的混合整数线性规划问题
Debug help: Mixed Integer Linear Programming problem in Python PuLP
我有一个 MILP 问题，我在 Python 和 运行 中使用 PuLP 解决了求解器的一些有趣行为，我无法理解。我很想知道是什么导致了这个问题。
先简单介绍一下问题陈述。这是一个 t运行 体育网络问题，有一堆节点被连接起来，这样总成本最小，同时满足一些约束，比如 disabling/forcing 一些车道。
当我使用 PuLP 的捆绑求解器解决问题时，它给出了以下解决方案。
objective = cost
opt_model.setObjective(objective)
opt_model.sense = plp.LpMinimize
opt_model.solve()
print(plp.LpStatus[opt_model.status])
print("objective=", opt_model.objective.value())
Optimal
objective= 20968423.09652282
我意识到 PuLP 使用的求解器版本是 2.9.0，但 COIN-OR 网站上的最新版本是 2.10.3，所以决定使用最新的 CBC 求解器。当我这样做时，这个完全相同的问题在新求解器中变得不可行。
objective = cost
opt_model.setObjective(objective)
opt_model.sense = plp.LpMinimize
opt_model.solve(solver=plp.COIN_CMD(path='<path to solver>/cbc'))
print(plp.LpStatus[opt_model.status])
print("objective=", opt_model.objective.value())
Infeasible
objective= 18434742.025923416
然而，有趣的是，只有当我通过 PuLP 解决问题时，它才会给我一个问题。如果我使用 PuLP 创建的 .lp 文件并直接使用下载的 cbc 二进制文件求解，它会求解并给出一个与 PuLP 求解器的答案非常接近的最佳答案！
Welcome to the CBC MILP Solver
Version: 2.10.3
Build Date: Dec 15 2019
command line - ./cbc writeLP_model_Partial.lp (default strategy 1)
Continuous objective value is 1.84347e+07 - 0.16 seconds
Cgl0003I 0 fixed, 0 tightened bounds, 854 strengthened rows, 338 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 630 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 278 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 100 strengthened rows, 0 substitutions
Cgl0004I processed model has 6676 rows, 5092 columns (5092 integer (3674 of which binary)) and 21162 elements
Cbc0038I Initial state - 435 integers unsatisfied sum - 73.1625
Cbc0038I Pass 1: (1.31 seconds) suminf. 54.06687 (218) obj. 2.10227e+07 iterations 631
Cbc0038I Pass 2: (1.31 seconds) suminf. 54.06685 (218) obj. 2.10227e+07 iterations 0
Cbc0038I Pass 3: (1.32 seconds) suminf. 54.06685 (218) obj. 2.10227e+07 iterations 0
Cbc0038I Pass 4: (1.33 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 1
Cbc0038I Pass 5: (1.33 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 6: (1.33 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 7: (1.34 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 8: (1.34 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 9: (1.35 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 10: (1.35 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 11: (1.35 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 12: (1.36 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 13: (1.37 seconds) suminf. 47.92774 (193) obj. 2.24017e+07 iterations 444
Cbc0038I Pass 14: (1.38 seconds) suminf. 47.92774 (193) obj. 2.24017e+07 iterations 33
Cbc0038I Pass 15: (1.38 seconds) suminf. 47.92774 (193) obj. 2.24017e+07 iterations 0
Cbc0038I Pass 16: (1.39 seconds) suminf. 47.92774 (193) obj. 2.24017e+07 iterations 0
Cbc0038I Pass 17: (1.40 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 355
Cbc0038I Pass 18: (1.41 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 20
Cbc0038I Pass 19: (1.41 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 20: (1.42 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 21: (1.42 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 22: (1.42 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 23: (1.43 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 24: (1.43 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 25: (1.44 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 26: (1.44 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 27: (1.46 seconds) suminf. 44.63425 (184) obj. 2.45218e+07 iterations 368
Cbc0038I Pass 28: (1.47 seconds) suminf. 44.63425 (184) obj. 2.45218e+07 iterations 17
Cbc0038I Pass 29: (1.47 seconds) suminf. 44.63425 (184) obj. 2.45218e+07 iterations 0
Cbc0038I Pass 30: (1.48 seconds) suminf. 44.63425 (184) obj. 2.45218e+07 iterations 0
Cbc0038I Rounding solution of 2.09662e+07 is better than previous of 1e+50
Cbc0038I Before mini branch and bound, 3925 integers at bound fixed and 1 continuous
Cbc0038I Mini branch and bound did not improve solution (1.50 seconds)
Cbc0038I After 1.50 seconds - Feasibility pump exiting with objective of 2.09662e+07 - took 0.25 seconds
Cbc0012I Integer solution of 20966181 found by feasibility pump after 0 iterations and 0 nodes (1.50 seconds)
Cbc0001I Search completed - best objective 20966181.27328906, took 0 iterations and 0 nodes (1.55 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from 2.09843e+07 to 2.09843e+07
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 s
econds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
ZeroHalf was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Result - Optimal solution found
Objective value: 20966181.27328906
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 1.74
Time (Wallclock seconds): 1.82
Total time (CPU seconds): 1.85 (Wallclock seconds): 1.96
我在这里错过了什么？我尝试了不同的方法，比如将 PuLP 更新到最新版本，但这没有帮助。是否有任何我需要更改的求解器选项？我是新手，所以不知道该尝试什么。
您很可能 运行 陷入了数值精度问题。检查 this part of the pulp docs 的第 2 点。您在约束参数和 objective 函数系数中为浮点数使用了太多小数。只需将所有参数四舍五入到 2 位或 3 位小数（或对您的问题有意义的任何值）。
这可以看出，因为你objective函数值很长（18434742.025923416）并且因为CBC给出了不同的objective最优（应该只有一个最优objective 函数值，与您使用的求解器无关）。
我有一个 MILP 问题，我在 Python 和 运行 中使用 PuLP 解决了求解器的一些有趣行为，我无法理解。我很想知道是什么导致了这个问题。
先简单介绍一下问题陈述。这是一个 t运行 体育网络问题，有一堆节点被连接起来，这样总成本最小，同时满足一些约束，比如 disabling/forcing 一些车道。
当我使用 PuLP 的捆绑求解器解决问题时，它给出了以下解决方案。
objective = cost
opt_model.setObjective(objective)
opt_model.sense = plp.LpMinimize
opt_model.solve()
print(plp.LpStatus[opt_model.status])
print("objective=", opt_model.objective.value())
Optimal
objective= 20968423.09652282
我意识到 PuLP 使用的求解器版本是 2.9.0，但 COIN-OR 网站上的最新版本是 2.10.3，所以决定使用最新的 CBC 求解器。当我这样做时，这个完全相同的问题在新求解器中变得不可行。
objective = cost
opt_model.setObjective(objective)
opt_model.sense = plp.LpMinimize
opt_model.solve(solver=plp.COIN_CMD(path='<path to solver>/cbc'))
print(plp.LpStatus[opt_model.status])
print("objective=", opt_model.objective.value())
Infeasible
objective= 18434742.025923416
然而，有趣的是，只有当我通过 PuLP 解决问题时，它才会给我一个问题。如果我使用 PuLP 创建的 .lp 文件并直接使用下载的 cbc 二进制文件求解，它会求解并给出一个与 PuLP 求解器的答案非常接近的最佳答案！
Welcome to the CBC MILP Solver
Version: 2.10.3
Build Date: Dec 15 2019
command line - ./cbc writeLP_model_Partial.lp (default strategy 1)
Continuous objective value is 1.84347e+07 - 0.16 seconds
Cgl0003I 0 fixed, 0 tightened bounds, 854 strengthened rows, 338 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 630 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 278 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 100 strengthened rows, 0 substitutions
Cgl0004I processed model has 6676 rows, 5092 columns (5092 integer (3674 of which binary)) and 21162 elements
Cbc0038I Initial state - 435 integers unsatisfied sum - 73.1625
Cbc0038I Pass 1: (1.31 seconds) suminf. 54.06687 (218) obj. 2.10227e+07 iterations 631
Cbc0038I Pass 2: (1.31 seconds) suminf. 54.06685 (218) obj. 2.10227e+07 iterations 0
Cbc0038I Pass 3: (1.32 seconds) suminf. 54.06685 (218) obj. 2.10227e+07 iterations 0
Cbc0038I Pass 4: (1.33 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 1
Cbc0038I Pass 5: (1.33 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 6: (1.33 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 7: (1.34 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 8: (1.34 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 9: (1.35 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 10: (1.35 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 11: (1.35 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 12: (1.36 seconds) suminf. 53.70259 (217) obj. 2.10265e+07 iterations 0
Cbc0038I Pass 13: (1.37 seconds) suminf. 47.92774 (193) obj. 2.24017e+07 iterations 444
Cbc0038I Pass 14: (1.38 seconds) suminf. 47.92774 (193) obj. 2.24017e+07 iterations 33
Cbc0038I Pass 15: (1.38 seconds) suminf. 47.92774 (193) obj. 2.24017e+07 iterations 0
Cbc0038I Pass 16: (1.39 seconds) suminf. 47.92774 (193) obj. 2.24017e+07 iterations 0
Cbc0038I Pass 17: (1.40 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 355
Cbc0038I Pass 18: (1.41 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 20
Cbc0038I Pass 19: (1.41 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 20: (1.42 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 21: (1.42 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 22: (1.42 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 23: (1.43 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 24: (1.43 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 25: (1.44 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 26: (1.44 seconds) suminf. 47.92774 (193) obj. 2.34752e+07 iterations 0
Cbc0038I Pass 27: (1.46 seconds) suminf. 44.63425 (184) obj. 2.45218e+07 iterations 368
Cbc0038I Pass 28: (1.47 seconds) suminf. 44.63425 (184) obj. 2.45218e+07 iterations 17
Cbc0038I Pass 29: (1.47 seconds) suminf. 44.63425 (184) obj. 2.45218e+07 iterations 0
Cbc0038I Pass 30: (1.48 seconds) suminf. 44.63425 (184) obj. 2.45218e+07 iterations 0
Cbc0038I Rounding solution of 2.09662e+07 is better than previous of 1e+50
Cbc0038I Before mini branch and bound, 3925 integers at bound fixed and 1 continuous
Cbc0038I Mini branch and bound did not improve solution (1.50 seconds)
Cbc0038I After 1.50 seconds - Feasibility pump exiting with objective of 2.09662e+07 - took 0.25 seconds
Cbc0012I Integer solution of 20966181 found by feasibility pump after 0 iterations and 0 nodes (1.50 seconds)
Cbc0001I Search completed - best objective 20966181.27328906, took 0 iterations and 0 nodes (1.55 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from 2.09843e+07 to 2.09843e+07
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 s
econds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
ZeroHalf was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Result - Optimal solution found
Objective value: 20966181.27328906
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 1.74
Time (Wallclock seconds): 1.82
Total time (CPU seconds): 1.85 (Wallclock seconds): 1.96
我在这里错过了什么？我尝试了不同的方法，比如将 PuLP 更新到最新版本，但这没有帮助。是否有任何我需要更改的求解器选项？我是新手，所以不知道该尝试什么。
您很可能 运行 陷入了数值精度问题。检查 this part of the pulp docs 的第 2 点。您在约束参数和 objective 函数系数中为浮点数使用了太多小数。只需将所有参数四舍五入到 2 位或 3 位小数（或对您的问题有意义的任何值）。
这可以看出，因为你objective函数值很长（18434742.025923416）并且因为CBC给出了不同的objective最优（应该只有一个最优objective 函数值，与您使用的求解器无关）。