search

coin-or / Clp

COIN-OR Linear Programming Solver
Other
396 stars 82 forks source link

Infeasible after presolve #189

Open manueloverride opened 3 years ago

manueloverride commented 3 years ago

The attached model is easily solved with presolve off, but with presolve it reports as infeasible.

./clp tm_bln.mps.gz
Coin LP version 1.17.6, build May  3 2021
command line - ./clp tm_bln.mps.gz 
At line 8 NAME          ClpDefau
At line 9 ROWS
At line 159 COLUMNS
At line 545 RHS
At line 546 BOUNDS
At line 696 ENDATA
Problem ClpDefau has 148 rows, 248 columns and 492 elements
Model was imported from ./tm_bln.mps.gz in 0.000623 seconds
Presolve 20 (-128) rows, 91 (-157) columns and 119 (-373) elements
0  Obj -3.3793956e+10 Primal inf 6624659.6 (12) Dual inf 703.26099 (10)
23  Obj -3.4087972e+10
Optimal - objective value -3.4087972e+10
After Postsolve, objective -3.4087972e+10, infeasibilities - dual 0 (0), primal 3.0039129e+11 (1)
Presolved model was optimal, full model needs cleaning up
0  Obj -3.4087972e+10 Primal inf 2.2526169e+11 (1)
1  Obj 2.6894147e+11 Primal inf 1.8646586e+12 (4)
1  Obj 2.6894147e+11 Primal inf 1.8646586e+12 (4)
1  Obj 2.1821432e+11 Primal inf 1.5181671e+12 (4)
2  Obj -3.9757854e+10 Primal inf 2.195128e+11 (4)
2  Obj -3.9757854e+10 Primal inf 2.195128e+11 (4)
2  Obj -3.9757854e+10 Primal inf 2.195128e+11 (4)
Primal infeasible - objective value -3.9757854e+10
PrimalInfeasible objective -3.975785423e+10 - 25 iterations time 0.002, Presolve 0.00

./clp tm_bln.mps.gz -presolve off solve
Coin LP version 1.17.6, build May  3 2021
command line - ./clp tm_bln.mps.gz -presolve off solve 
At line 8 NAME          ClpDefau
At line 9 ROWS
At line 159 COLUMNS
At line 545 RHS
At line 546 BOUNDS
At line 696 ENDATA
Problem ClpDefau has 148 rows, 248 columns and 492 elements
Model was imported from ./tm_bln.mps.gz in 0.000879 seconds
Perturbing problem by 0.001% of 31.622777 - largest nonzero change 2.0715534e-05 ( 6.5508271%) - largest zero change 2.0579708e-05
0  Obj 4688.2611 Primal inf 7970997.2 (9) Dual inf 1006.48 (15)
57  Obj -1.6275278e+09 Primal inf 8966891.5 (11)
71  Obj -1.627291e+09
71  Obj -6.9615588e+09 Primal inf 2.184229e+10 (1)
72  Obj -4.0488426e+09
Optimal - objective value -4.0488426e+09
Optimal objective -4048842603 - 72 iterations time 0.002

tm_bln.mps.gz

jjhforrest commented 3 years ago

This has similarities to #188 - but for dual not primal. Dual simplex wants to operate on a dual feasible problem - so if a variable is at its lower bound of 0.0 with a negative reduced cost (and its upper bound is 1.0e20 say) , it will put it to a fake upper bound of "dualBound". This is normally initialized to 1.0e10 - but should increase if problem looks infeasible (again like the primal case the code will declare infeasible if increase to say 1.0e18 does no good).

There is a bug here as infeasibility was declared without bound being increased - will look into it.

In the optimal solution two variables have value 3.7e10.

For the moment setting -dualBound 1.0e15 should work.

John Forrest

On 03/05/2021 19:27, manueloverride wrote:

The attached model is easily solved with presolve off, but with presolve it reports as infeasible.

|./clp tm_bln.mps.gz Coin LP version 1.17.6, build May 3 2021 command line - ./clp tm_bln.mps.gz At line 8 NAME ClpDefau At line 9 ROWS At line 159 COLUMNS At line 545 RHS At line 546 BOUNDS At line 696 ENDATA Problem ClpDefau has 148 rows, 248 columns and 492 elements Model was imported from ./tm_bln.mps.gz in 0.000623 seconds Presolve 20 (-128) rows, 91 (-157) columns and 119 (-373) elements 0 Obj -3.3793956e+10 Primal inf 6624659.6 (12) Dual inf 703.26099 (10) 23 Obj -3.4087972e+10 Optimal - objective value -3.4087972e+10 After Postsolve, objective -3.4087972e+10, infeasibilities - dual 0 (0), primal 3.0039129e+11 (1) Presolved model was optimal, full model needs cleaning up 0 Obj -3.4087972e+10 Primal inf 2.2526169e+11 (1) 1 Obj 2.6894147e+11 Primal inf 1.8646586e+12 (4) 1 Obj 2.6894147e+11 Primal inf 1.8646586e+12 (4) 1 Obj 2.1821432e+11 Primal inf 1.5181671e+12 (4) 2 Obj -3.9757854e+10 Primal inf 2.195128e+11 (4) 2 Obj -3.9757854e+10 Primal inf 2.195128e+11 (4) 2 Obj -3.9757854e+10 Primal inf 2.195128e+11 (4) Primal infeasible - objective value -3.9757854e+10 PrimalInfeasible objective -3.975785423e+10 - 25 iterations time 0.002, Presolve 0.00 ./clp tm_bln.mps.gz -presolve off solve Coin LP version 1.17.6, build May 3 2021 command line - ./clp tm_bln.mps.gz -presolve off solve At line 8 NAME ClpDefau At line 9 ROWS At line 159 COLUMNS At line 545 RHS At line 546 BOUNDS At line 696 ENDATA Problem ClpDefau has 148 rows, 248 columns and 492 elements Model was imported from ./tm_bln.mps.gz in 0.000879 seconds Perturbing problem by 0.001% of 31.622777 - largest nonzero change 2.0715534e-05 ( 6.5508271%) - largest zero change 2.0579708e-05 0 Obj 4688.2611 Primal inf 7970997.2 (9) Dual inf 1006.48 (15) 57 Obj -1.6275278e+09 Primal inf 8966891.5 (11) 71 Obj -1.627291e+09 71 Obj -6.9615588e+09 Primal inf 2.184229e+10 (1) 72 Obj -4.0488426e+09 Optimal

  • objective value -4.0488426e+09 Optimal objective -4048842603 - 72 iterations time 0.002 |

tm_bln.mps.gz https://github.com/coin-or/Clp/files/6416810/tm_bln.mps.gz

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/coin-or/Clp/issues/189, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHH4NV3LVIK2MCHBJB3TL3TKNANCNFSM44BJAMTA.

manueloverride commented 3 years ago

Thanks for the explanation. I hope to understand the internal workings of clp one day. Right now I'm just poking with a stick at it. For example, it says dualBound is limited in range. I could easily change the check for this but I have no idea if this breaks any assumptions elsewhere.

1e+15 was provided for dualBound - valid range is 1e-20 to 1e+12