Infeasibility error for feasible problem

[alexandergerber]

Cbc tells me that my problem is infeasible. However, it was solvable with another solver as well as with less data. The model is quite big what probably causes the the problem. Is there a way to fix this?

You can find my lp file here.

[andreacassioli]

Hi, similar issue here: I have a MIP that is declared infeasible on some machines, but can be easily solved to optimality on other. I am running version 2.9.9 (I cannot update until debian package is updated...).

[aldeo]

I have a similar issue. I ran the CBC CLI version 2.9.10 on a .LP and get an optimal solution. With CBC CLI version 2.10.0 i get the error below:

ERROR: CoinLpIO::read_monom_row, ### ERROR: Unable to read row monomial

There were -1 errors on input
** Current model not valid
Total time (CPU seconds):       0.01   (Wallclock seconds):       0.01

I get the same error with version 2.10.4. I'm running windows and using the zip files available in https://bintray.com/coin-or/download/Cbc#files : Cbc-2.9.10-win32-msvc14.zip, Cbc-2.10-win32-msvc14.zip, Cbc-2.10.4-win32-msvc15.zip

[andreacassioli]

It looks like 2.10 broke something, indeed. We can reproduce our problem supposed infeasibility (which is not...) on 2.10, while 2.9 correctly find optimality.

[Usiel]

Same here, simple LP that was solved with 2.9.9 is supposedly infeasible using 2.10.3. Could this be related to an issue on Clp?

[Usiel]

Adding some more information. Attached is an .lp file that fails with cbc 2.10.3: 2.10.3.fail.zip

Output cbc 2.10.3:

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

command line - /home/usiel/cbc_2.10.3 -timeMode elapsed -import /.../2.10.3.fail.lp -stat=1 -solve (default strategy 1)
Option for timeMode changed from cpu to elapsed
Presolve 3757 (-19032) rows, 9525 (-30306) columns and 30843 (-114690) elements
Statistics for presolved model

Problem has 3757 rows, 9525 columns (9089 with objective) and 30843 elements
There are 1505 singletons with objective 
Column breakdown:
9265 of type 0.0->inf, 201 of type 0.0->up, 1 of type lo->inf, 
0 of type lo->up, 0 of type free, 0 of type fixed, 
0 of type -inf->0.0, 0 of type -inf->up, 58 of type 0.0->1.0 
Row breakdown:
0 of type E 0.0, 0 of type E 1.0, 0 of type E -1.0, 
0 of type E other, 1551 of type G 0.0, 246 of type G 1.0, 
1923 of type G other, 1 of type L 0.0, 5 of type L 1.0, 
31 of type L other, 0 of type Range 0.0->1.0, 0 of type Range other, 
0 of type Free 
Presolve 3757 (-19032) rows, 9525 (-30306) columns and 30843 (-114690) elements
Perturbing problem by 0.001% of 400 - largest nonzero change 0.00049997725 ( 8.8079827%) - largest zero change 0.00049927087
0  Obj 1331.4422 Primal inf 1704.9995 (508) Dual inf 12.948742 (259)
150  Obj 1300.1876 Primal inf 1728.9993 (734)
300  Obj 1302.5162 Primal inf 1397.9993 (666)
428  Obj 1310.8308 Primal inf 1313.9994 (618)
Primal infeasible - objective value 1310.8308
Presolved problem not optimal, resolve after postsolve
After Postsolve, objective 1310.58, infeasibilities - dual 0.23354136 (1293), primal 1339.9999 (621)
Perturbing problem by 1e-08% of 40000000 - largest nonzero change 0.00040998725 ( 8.0395316%) - largest zero change 0.00040990381
0  Obj 1310.5777 Primal inf 1339.9999 (621)
Primal infeasible - objective value 1310.5777
PrimalInfeasible objective 1310.577731 - 428 iterations time 0.052, Presolve 0.03

Result - Linear relaxation infeasible

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

Total time (CPU seconds):       0.17   (Wallclock seconds):       0.18

Output cbc 2.9.9:

Welcome to the CBC MILP Solver 
Version: 2.9.9 
Build Date: Aug 25 2017 

command line - /home/usiel/cbc_2.9.9 -timeMode elapsed -import /.../2.10.3.fail.lp -stat=1 -solve (default strategy 1)
Option for timeMode changed from cpu to elapsed
Presolve 3757 (-19032) rows, 9525 (-30306) columns and 30843 (-114690) elements
Statistics for presolved model


Problem has 3757 rows, 9525 columns (9089 with objective) and 30843 elements
There are 1505 singletons with objective 
Column breakdown:
9265 of type 0.0->inf, 201 of type 0.0->up, 1 of type lo->inf, 
0 of type lo->up, 0 of type free, 0 of type fixed, 
0 of type -inf->0.0, 0 of type -inf->up, 58 of type 0.0->1.0 
Row breakdown:
0 of type E 0.0, 0 of type E 1.0, 0 of type E -1.0, 
0 of type E other, 1551 of type G 0.0, 246 of type G 1.0, 
1923 of type G other, 1 of type L 0.0, 5 of type L 1.0, 
31 of type L other, 0 of type Range 0.0->1.0, 0 of type Range other, 
0 of type Free 
Presolve 3757 (-19032) rows, 9525 (-30306) columns and 30843 (-114690) elements
Perturbing problem by 0.001 %% of 400 - largest nonzero change 0.00049997725 (%% 8.8079827) - largest zero change 0.00049927087
0  Obj 1331.4422 Primal inf 1704.9995 (508) Dual inf 12.948742 (259)
150  Obj 1300.1876 Primal inf 1728.9993 (734)
300  Obj 1302.5167 Primal inf 1397.9993 (666)
428  Obj 1310.8248 Primal inf 1314.9994 (617)
...
Optimal - objective value 1.5300001e+17
Optimal objective 1.5300001e+17 - 54326 iterations time 4.982, Presolve 0.03
Total time (CPU seconds):       5.14   (Wallclock seconds):       5.18

[jjhforrest]

A scaling problem - will look into it. However I would suggest you consider modifying your objective function. Fails wirh dual, but solves with primal - about 50K iterations. If I change all 1.0e15 objective values to 1.0e11 and all 1.0e20 to 1.0e12, it solves with primal or dual in only 3K iterations.

[Usiel]

Thanks John, will do that for now.

[jjhforrest]

Seems fine in master - so hopefully good in next release

[tkralphs]

Since master has diverged substantially from 2.10, it may be hard to figure out what to cherry-pick over in order to fix this in the next release. If you know of any specific commits that should be cherry-picked, let me know. Would be nice to get this fixed in 2.10, although we'll have a new stable from current master in the near future.

[dwr-psandhu]

@tkralphs Did this ever make it into 2.10.x releases? Is there a stable relese from current master that has this fix?

[tkralphs]

Unfortunately, my bandwidth for doing this has become more limited than what I expected when I made the above comment (which was probably optimistic anyway). Also, the community support for doing the work needed to get master into release has not really been there. So no, this has not happened yet. But it is very much still on my radar and something I want to see through.