search

coin-or / Clp

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

Example of code that causes the solve to fail when it shouldn't. #188

Closed PlannedCanada closed 3 years ago

PlannedCanada commented 3 years ago

Matrix multiplication with the known solution indicates it's correct, but CLP thinks the problem is infeasible. Here's a program demonstrating it: https://github.com/PlannedCanada/clp_glitch

jjhforrest commented 3 years ago

I am not sure that this is an important bug - the clue may be in the use of "glitch" - and the problem does seem to be a trifle artificial.

Clp uses a composite objective function while infeasible i.e. it tries to minimize objective + infeasibiityCost * sum of infeasibilities. This infeasibility cost can be set by user, but normally it may be 1.0e10. If the problem looks infeasible this is increased but after a bit (about 1.0e19) the code decides it is infeasible.

The code could be changed to make sure it tries just minimizing sum of infeasibilities, but I am not sure it is worth the effort.

If

glitch_model.setInfeasibilityCost(1.0e25);

is added then we get

Clp0006I 0 Obj -0 Primal inf 1.5133458e+14 (85) Dual inf 1.0320887e+28 (90) Clp0006I 92 Obj -0 Dual inf 1.2300457e+21 (1) Clp0006I 92 Obj -0 Dual inf 1.2300457e+21 (1) Clp0002I Dual infeasible - objective value -0

John Forrest

On 22/04/2021 21:50, PlannedCanada wrote:

Matrix multiplication with the known solution indicates it's correct, but CLP thinks the problem is infeasible. Here's a program demonstrating it: https://github.com/PlannedCanada/clp_glitch https://github.com/PlannedCanada/clp_glitch

— 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/188, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHEJV5WA6ZRZMUPR6A3TKCDZVANCNFSM43NK3SEA.

PlannedCanada commented 3 years ago

Hey, thanks for getting back to me, and so fast. I've now discovered and corrected what seems to be the cause of dual infeasibility in the model as well (an off by one error). CLP even works fine without the larger infeasibility cost on the correct model.