[BUG] Suspecting wrong return of LpStatusOptimal when using CBC

[Vincent-Liagre-QB]

What did you do?

Trying to solve a problem using PuLP and CBC (see versions below).

The solution I got is not valid (some constraints are violated)

What did you expect to see?

Some status telling no valid solution was found.

What did you see instead?

Got the following statuses :

status : 1 # constants.LpStatusOptimal
sol_status : 2 # constants.LpSolutionIntegerFeasible

From inserting a breakpoint in the code I got those statuses from the following logic :

pulp/pulp/apis/coin_api.py

Lines 337 to 340 in 858304d

	if status == constants.LpStatusNotSolved and len(statusstrs) >= 5:
	if statusstrs[4] == "objective":
	status = constants.LpStatusOptimal
	sol_status = constants.LpSolutionIntegerFeasible

Which is applied when solver stops on time limit - which is what happened. Now when the solver stops on time limit the solution could be :

1. either valid but not optimal
2. or invalid

It seems the logic above aims at capturing the "valid but not optimal" case. But it seems to have caught an "invalid solution" case in my case.

Some extra info

statusstrs is ['Stopped', 'on', 'iterations', '-', 'objective', 'value', '79185057.39091943']

The pulp.sol file is

Stopped on iterations - objective value 79185057.39091943
      0 C0000000  -1.3877788e-17               5.0000413
      1 C0000001    2.220446e-16               5.0000474
      2 C0000002               0               5.0000866
...
 287415 X0287415               0              -72.999889
 287416 X0287416               0              -32.999903
 287417 X0287417               0              -22.999902
 287418 X0287418               0              -27.999866

The CBC logs

Welcome to the CBC MILP Solver 
Version: 2.10.3
Build Date: Dec 15 2019

command line - C:\Users\xxx\lib\site-packages\pulp\solverdir\cbc\win\64\cbc.exe C:\Users\VINCEN~1\AppData\Local\Temp\548096f6ac1c4068b4279e6e1cc7afca-pulp.mps max sec 5 timeMode elapsed branch printingOptions all solution C:\Users\VINCEN~1\AppData\Local\Temp\548096f6ac1c4068b4279e6e1cc7afca-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 87516 COLUMNS
At line 943551 RHS
At line 1031063 BOUNDS
At line 1031064 ENDATA
Problem MODEL has 87511 rows, 287419 columns and 582317 elements
Coin0008I MODEL read with 0 errors
seconds was changed from 1e+100 to 5
Option for timeMode changed from cpu to elapsed
Presolve 39318 (-48193) rows, 250108 (-37311) columns and 497609 (-84708) elements
Perturbing problem by 0.001% of 8902.4899 - largest nonzero change 0.00099987002 ( 0.091902448%) - largest zero change 0.00045007451
0  Obj -0.62515941 Primal inf 2950199.7 (16117) Dual inf 31186322 (118464)
421  Obj 1.1089242e+09 Primal inf 41716007 (23996)
842  Obj 1.0591788e+09 Primal inf 39683787 (24379)
1263  Obj 1.0114967e+09 Primal inf 37673355 (24516)
1684  Obj 9.6030435e+08 Primal inf 35676071 (24738)
2105  Obj 9.1401653e+08 Primal inf 33778149 (24820)
2526  Obj 8.6848653e+08 Primal inf 31924412 (24917)
2947  Obj 8.2556145e+08 Primal inf 30200012 (25104)
3368  Obj 7.8162452e+08 Primal inf 28562512 (25094)
3789  Obj 7.4034834e+08 Primal inf 26963210 (25158)
4210  Obj 7.0030161e+08 Primal inf 25418436 (25145)
4631  Obj 6.6233187e+08 Primal inf 23908607 (25126)
5052  Obj 6.2686457e+08 Primal inf 22530881 (25122)
5473  Obj 5.9469941e+08 Primal inf 21240793 (25131)
5894  Obj 5.6190769e+08 Primal inf 19882469 (25065)
6315  Obj 5.3041469e+08 Primal inf 18608012 (25029)
6736  Obj 4.9904101e+08 Primal inf 17422152 (24948)
7157  Obj 4.7159836e+08 Primal inf 16295864 (24858)
7578  Obj 4.4408799e+08 Primal inf 15183068 (24768)
7999  Obj 4.1886626e+08 Primal inf 14148756 (24602)
8420  Obj 3.9398905e+08 Primal inf 13168681 (24505)
8841  Obj 3.6852406e+08 Primal inf 12250705 (24409)
9262  Obj 3.4624054e+08 Primal inf 11393841 (24314)
9683  Obj 3.2538627e+08 Primal inf 10605318 (24185)
10104  Obj 3.0641424e+08 Primal inf 9847557.9 (24125)
10525  Obj 2.9003331e+08 Primal inf 9186511.7 (24064)
10946  Obj 2.7223584e+08 Primal inf 8536080.9 (23975)
11367  Obj 2.5695936e+08 Primal inf 7942427.2 (23902)
11788  Obj 2.413077e+08 Primal inf 7336879.6 (23809)
12209  Obj 2.2720727e+08 Primal inf 6815071.8 (23781)
12630  Obj 2.1569572e+08 Primal inf 6359863.7 (23750)
13051  Obj 2.0493468e+08 Primal inf 5940396.2 (23731)
13472  Obj 1.9585694e+08 Primal inf 5583776.8 (23655)
13893  Obj 1.8685816e+08 Primal inf 5222080.1 (23647)
14314  Obj 1.7794097e+08 Primal inf 4855147.4 (23550)
14735  Obj 1.6916812e+08 Primal inf 4524587.5 (23520)
15156  Obj 1.6162387e+08 Primal inf 4230253.8 (23461)
15577  Obj 1.5522211e+08 Primal inf 3982936.8 (23472)
15998  Obj 1.4974786e+08 Primal inf 3754410.6 (23478)
16419  Obj 1.4448256e+08 Primal inf 3551877.2 (23470)
16840  Obj 1.3934683e+08 Primal inf 3358306.3 (23429)
17261  Obj 1.3504694e+08 Primal inf 3177642.7 (23459)
17682  Obj 1.3037917e+08 Primal inf 2986358.5 (23446)
18103  Obj 1.2655774e+08 Primal inf 2813882 (23395)
18524  Obj 1.2255575e+08 Primal inf 2651593.9 (23321)
18945  Obj 1.1894006e+08 Primal inf 2487510.5 (23256)
19366  Obj 1.1544834e+08 Primal inf 2333300.6 (23145)
19787  Obj 1.1200945e+08 Primal inf 2197359.9 (23053)
20208  Obj 1.0943493e+08 Primal inf 2075084 (22924)
20629  Obj 1.0673019e+08 Primal inf 1938668.3 (22688)
21050  Obj 1.0465557e+08 Primal inf 1829263.3 (22493)
21471  Obj 1.0249505e+08 Primal inf 1703654.2 (22214)
21892  Obj 1.0081674e+08 Primal inf 1581507.7 (21825)
22313  Obj 98770166 Primal inf 1468403.7 (21523)
22734  Obj 97356617 Primal inf 1359882.6 (21118)
23155  Obj 95989319 Primal inf 1258929.6 (20674)
23576  Obj 94735426 Primal inf 1164418.3 (20276)
23997  Obj 93388731 Primal inf 1055078.2 (19548)
24418  Obj 92288419 Primal inf 962282.23 (18923)
24839  Obj 91140454 Primal inf 879652.69 (18435)
25260  Obj 90023843 Primal inf 798869.43 (17857)
25681  Obj 88916795 Primal inf 711197.31 (17198)
26102  Obj 88005644 Primal inf 636697.23 (16511)
26523  Obj 87072858 Primal inf 569958.22 (15950)
26944  Obj 86303808 Primal inf 504972.75 (15383)
27365  Obj 85414328 Primal inf 450661.94 (14838)
27786  Obj 84631013 Primal inf 384663.71 (13988)
28207  Obj 83930303 Primal inf 331713.79 (13513)
28628  Obj 83203031 Primal inf 281477.09 (12778)
29049  Obj 82644829 Primal inf 233874.03 (12175)
29470  Obj 82115938 Primal inf 195258.34 (11642)
29891  Obj 81596015 Primal inf 162047.79 (11072)
30312  Obj 81164255 Primal inf 132996.06 (10678)
30733  Obj 80795459 Primal inf 110220.75 (10366)
31154  Obj 80483579 Primal inf 91947.113 (10146) Dual inf 2.5896952e-14 (1)
31575  Obj 80265611 Primal inf 83325.204 (10000) Dual inf 2.5896952e-14 (1)
31996  Obj 80116502 Primal inf 75521.758 (9831) Dual inf 2.5896952e-14 (1)
32417  Obj 79998284 Primal inf 68716.848 (9735) Dual inf 2.5896952e-14 (1)
32838  Obj 79897906 Primal inf 64698.294 (9726) Dual inf 2.5896952e-14 (1)
33259  Obj 79829314 Primal inf 60994.717 (9815) Dual inf 2.5896952e-14 (1)
33680  Obj 79752358 Primal inf 55099.416 (9742) Dual inf 2.5896952e-14 (1)
34101  Obj 79677871 Primal inf 51945.411 (9775) Dual inf 2.5896952e-14 (1)
34522  Obj 79625908 Primal inf 45183.027 (9715) Dual inf 2.5896952e-14 (1)
34943  Obj 79565808 Primal inf 52730.944 (9731) Dual inf 2.5896952e-14 (1)
35364  Obj 79522074 Primal inf 49279.652 (9749) Dual inf 2.5896952e-14 (1)
35785  Obj 79482963 Primal inf 57626.1 (9776) Dual inf 2.5896952e-14 (1)
36206  Obj 79447452 Primal inf 56487.545 (9826) Dual inf 2.5896952e-14 (1)
36627  Obj 79416918 Primal inf 56823.689 (9816) Dual inf 2.5896952e-14 (1)
37048  Obj 79381057 Primal inf 35228.135 (9780) Dual inf 2.5896952e-14 (1)
37469  Obj 79356554 Primal inf 30262.625 (9679) Dual inf 2.5896952e-14 (1)
37890  Obj 79336789 Primal inf 28363.869 (9617) Dual inf 2.5896952e-14 (1)
38311  Obj 79325697 Primal inf 27316.275 (9580) Dual inf 2.5896952e-14 (1)
38732  Obj 79313830 Primal inf 26074.863 (9563) Dual inf 2.5896952e-14 (1)
39153  Obj 79304268 Primal inf 19806.012 (9342) Dual inf 2.5896952e-14 (1)
39574  Obj 79294729 Primal inf 34135.857 (9396)
39995  Obj 79287017 Primal inf 34324.853 (9343)
40416  Obj 79280195 Primal inf 32280.771 (9274)
40837  Obj 79273885 Primal inf 34859.525 (9248)
41258  Obj 79268003 Primal inf 34314.716 (9260)
41679  Obj 79262647 Primal inf 19474.147 (9172)
42100  Obj 79258730 Primal inf 17995.745 (9069)
42521  Obj 79254160 Primal inf 17497.297 (9019)
42942  Obj 79250526 Primal inf 16339.425 (8985)
43363  Obj 79246484 Primal inf 14169.689 (8878)
43784  Obj 79242005 Primal inf 15729.815 (8874)
44205  Obj 79238113 Primal inf 21795.181 (8920)
44626  Obj 79234560 Primal inf 16937.267 (8888)
45047  Obj 79230987 Primal inf 15598.682 (8820)
45468  Obj 79226672 Primal inf 12829.641 (8689)
45889  Obj 79223618 Primal inf 37418.172 (8670)
46310  Obj 79221709 Primal inf 14916.549 (8499)
46731  Obj 79219107 Primal inf 23073.776 (8580)
47152  Obj 79217410 Primal inf 24282.614 (8460)
47573  Obj 79214546 Primal inf 17228.891 (8379)
47994  Obj 79211483 Primal inf 14990.494 (8333)
48415  Obj 79210037 Primal inf 12314.976 (8211)
48836  Obj 79208273 Primal inf 47356.85 (8255)
49257  Obj 79207076 Primal inf 8693.0308 (8123)
49678  Obj 79205455 Primal inf 12210.176 (8056)
50099  Obj 79204301 Primal inf 6884.4727 (7956)
50520  Obj 79202711 Primal inf 6979.6478 (7859)
50941  Obj 79200381 Primal inf 7760.214 (7895)
51362  Obj 79198326 Primal inf 5144.525 (7625)
51783  Obj 79195102 Primal inf 5473.5115 (7593)
52204  Obj 79193598 Primal inf 4935.8986 (7564)
52625  Obj 79192429 Primal inf 4645.7643 (7485)
53046  Obj 79191373 Primal inf 52667.871 (7600)
53467  Obj 79189855 Primal inf 4189.0245 (7350)
53888  Obj 79188903 Primal inf 4439.4662 (7252)
54309  Obj 79187452 Primal inf 3717.6766 (7174)
54730  Obj 79186633 Primal inf 3691.2486 (7089)
55151  Obj 79185744 Primal inf 4022.0665 (7100)
55572  Obj 79184793 Primal inf 3653.6088 (6973)
Stopped - objective value 79184793
Presolved problem not optimal, resolve after postsolve
After Postsolve, objective 79185057, infeasibilities - dual 8328.2115 (54859), primal 8314.251 (7296)
Stopped objective 79185057.39 - 55572 iterations time 5.052, Presolve 0.46

Result - Stopped on time limit

Enumerated nodes:           0
Total iterations:           0
Time (CPU seconds):         5.63
Time (Wallclock Seconds):   5.63

Option for printingOptions changed from normal to all
Total time (CPU seconds):       6.34   (Wallclock seconds):       6.34

Useful extra information

The info below often helps, please fill it out if you're able to. :)

What operating system are you using?

• Windows: ( version: 11)
• Linux: ( distro: ___ )
• Mac OS: ( version: ___ )
• Other: ___

I'm using python version:

• 2.7
• 3.4
• 3.5
• 3.6
• Other: 3.8

I installed PuLP via:

• pypi (python -m pip install pulp)
• github (python -m pip install -U git+https://github.com/coin-or/pulp)
• Other: ___ (conda?)

Other useful environment info :

• CBC : 2.10.3
• PuLP : 2.7.0

Did you also

• Tried out the latest github version: https://github.com/coin-or/pulp
• Searched for an existing similar issue: https://github.com/coin-or/pulp/issues?utf8=%E2%9C%93&q=is%3Aissue%20

[Vincent-Liagre-QB]

Also adding the code dates back from this PR : #169

[pchtsp]

the status are correct. CBC reports it found an integer solution.

status : 1 # constants.LpStatusOptimal
sol_status : 2 # constants.LpSolutionIntegerFeasible

you mentioned it was invalid. Are you sure?

[Vincent-Liagre-QB]

@pchtsp thanks for looking into this - I do believe it's infeasible. My reasons to believe :

1. There are ** in the solution file which are, from inspecting valid solutions and as per the comment of the below in the code, indications of infeasible solutions

pulp/pulp/apis/coin_api.py

Lines 243 to 244 in e602a40

	# incase the solution is infeasible
	if l[0] == "**":

2. I have ex-post analyses that indicate this. Will try and save my problem as a JSON file to provide the full, reproducible example.

Also to your point : I don't think CBC reports that the solution is feasible. It only reports : ['Stopped', 'on', 'iterations', '-', 'objective', 'value', '79185057.39091943'] + the rest of the solution file with ** in it