我有一个 MILP 问题,我正在使用 Python 中的 PuLP 解决该问题,并且遇到了一些我无法理解的解算器的有趣行为。我很想就可能导致此问题的原因获得一些想法。
先说一点问题陈述。这是一个交通网络问题,需要连接一堆节点,这样总成本最小,同时满足一些约束,比如禁用/强制一些车道。
当我使用 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 更新到最新版本,但这并没有帮助。我需要更改任何求解器选项吗?我是新手,所以不知道该尝试什么。