我尝试使用 cbc 作为具有许多二元变量的求解器来解决带有 pulp 的 MIP。
求解器提供以下最优解:
Result - Optimal solution found
Objective value: 3140711.46256624
Enumerated nodes: 0
Total iterations: 72
Time (CPU seconds): 5.00
Time (Wallclock seconds): 5.00
warmStart=True
解决了问题。
求解器打印以下输出: 1 At line 2 NAME MODEL
2 At line 3 ROWS
3 At line 55726 COLUMNS
4 At line 855090 RHS
5 At line 910812 BOUNDS
6 At line 927761 ENDATA
7 Problem MODEL has 55721 rows, 642462 columns and 156901 elements
8 Coin0008I MODEL read with 0 errors
9 opening mipstart file .\Lager-Saw-pulp.mst.
10 MIPStart values read for 642462 variables.
11 seconds was changed from 1e+100 to 240
12 ratioGap was changed from 0 to 1e-05
13 Option for timeMode changed from cpu to elapsed
14 Continuous objective value is 2.00949e+06 - 0.48 seconds
15 Cgl0008I 169 inequality constraints converted to equality constraints
16 Cgl0005I 144 SOS with 7260 members
17 Cgl0004I processed model has 28899 rows, 14377 columns (7260 integer (7260 of which binary)) and 96340 elements
18 Cbc0045I Trying just fixing integer variables (and fixingish SOS).
19 Cbc0045I MIPStart provided solution with cost 3.14071e+06
20 Cbc0012I Integer solution of 3140711.5 found by Reduced search after 0 iterations and 0 nodes (2.39 seconds)
21 Cbc0038I Full problem 28899 rows 14377 columns, reduced to 21480 rows 14031 columns - too large
22 Cbc0031I 117 added rows had average density of 142.11111
23 Cbc0013I At root node, 341 cuts changed objective from 2009494.7 to 2013968.6 in 1 passes
24 Cbc0014I Cut generator 0 (Probing) - 6 row cuts average 2.0 elements, 1 column cuts (1 active) in 0.077 seconds - new frequency is -100
25 Cbc0014I Cut generator 1 (Gomory) - 45 row cuts average 281.3 elements, 0 column cuts (0 active) in 0.030 seconds - new frequency is 1
26 Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.009 seconds - new frequency is -100
27 Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
28 Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 124 row cuts average 168.4 elements, 0 column cuts (0 active) in 0.020 seconds - new frequency is 1
29 Cbc0014I Cut generator 5 (FlowCover) - 59 row cuts average 4.8 elements, 0 column cuts (0 active) in 0.005 seconds - new frequency is 1
30 Cbc0014I Cut generator 6 (TwoMirCuts) - 107 row cuts average 176.1 elements, 0 column cuts (0 active) in 0.064 seconds - new frequency is -100
31 Cbc0001I Search completed - best objective 3140711.46256619, took 1476 iterations and 0 nodes (19.21 seconds)
32 Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
33 0 Obj 3140757.2 Primal inf 4.3865913 (7) Dual inf 2.4104488e+14 (67)
34 Perturbing problem by 0.001% of 238.92857 - largest nonzero change 0.002390586 ( 0.0019959867%) - largest zero change 1.9999992e-05
35 129 Obj 3140757.3 Primal inf 4.1038477 (14)
36 129 Obj 3140757.3 Primal inf 4.1038486 (5)
37 Primal infeasible - objective value 3140757.3
38 Cuts at root node changed objective from 2.00949e+06 to 2.01397e+06
39 Probing was tried 1 times and created 7 cuts of which 0 were active after adding rounds of cuts (0.077 seconds)
40 Gomory was tried 1 times and created 45 cuts of which 0 were active after adding rounds of cuts (0.030 seconds)
41 Knapsack was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.009 seconds)
42 Clique was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
43 MixedIntegerRounding2 was tried 1 times and created 124 cuts of which 0 were active after adding rounds of cuts (0.020 seconds)
44 FlowCover was tried 1 times and created 59 cuts of which 0 were active after adding rounds of cuts (0.005 seconds)
45 TwoMirCuts was tried 1 times and created 107 cuts of which 0 were active after adding rounds of cuts (0.064 seconds)
46 ZeroHalf was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.006 seconds)
47
48 Result - Problem proven infeasible
49
50 Objective value: 100000000000000007629769841091887003294964970946560.00000000
51 Enumerated nodes: 0
52 Total iterations: 1476
53 Time (CPU seconds): 20.40
54 Time (Wallclock seconds): 20.40
如
line 10
所示,正确读取了起始解决方案,并在 line 20
中找到了整数解决方案,其目标与第一次优化运行相同。就我的预期而言。
但之后它变得混乱,因为求解器停止搜索更好的解决方案并声明该解决方案不可行。
我在 Windows 上使用 cbc 2.10.3,当你通过 pip 获取它时,它会附带 pulp。 我也用 cbc 2.10.10 尝试过,它产生了同样的问题,但在控制台中输出不同(更少)。
有朋友用商业求解器试过,warmstart提供的解不是最优解。
在纸浆中,我也按照这里的建议使用
keepFiles=True
:https://github.com/coin-or/pulp/discussions/411
我还尝试使用更高的整数容差(integerT 和 primalT)
有人知道我做错了什么吗? 如果有人想在机器上查看,我可以通过电子邮件提供这两个 mps 文件,因为它们太大了,无法张贴在这里。
提前致谢, 马蒂亚斯
更新
为了重现性,我使用以下代码和文件:
新的 CBC-CMD:
import prob1.mps
branch
solution prob1.sol
新的 CBC-CMD:
import prob2.mps
mips prob1.sol
branch
文件: GitHub