调试帮助: Python PuLP中的混合整数线性规划问题

Question

我有一个MILP问题，我正在使用python语言中的PuLP来解决这个问题，并且遇到了一些有趣的行为，解算器让我无法理解。我很想知道是什么原因导致了这个问题。

先简单介绍一下问题陈述。这是一个交通网络问题，需要连接一堆节点，使总成本最小，同时满足一些约束条件，如禁用/强制某些车道。

当我使用using的捆绑求解器解决这个问题时，它给出了以下解决方案。

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更新到最新版本，但都没有帮助。是否有需要更改的求解器选项？我是个新手，所以不知道该怎么做。

Answer 1

很可能会遇到数值精度问题。检查this part of the pulp docs的第2点。在约束和目标函数系数的参数中，浮点数使用了太多的十进制数。只需将所有参数四舍五入为2或3位小数(或对您的问题有意义的任何参数)。

这可以看出，因为你的目标函数值非常长(18434742.025923416)，而且CBC给出了不同的最优目标(无论你使用哪种求解器，应该只有一个最优目标函数值)。