Solver returns INFEASIBLE on a simple problem with a clear solution

[c-kob]

Minimisation of a simple linear model with a single constraint returns INFEASIBLE, despite producing the right numerical solution.

The following model (in EBM format) produces the issue:

V bieter1 624985000 829209000 1 false
V bieter2 0 398636000 1 false
V bieter3 0 131103000 1 false
V bieter4 72746000 876541000 1 false
E bieter4&bieter1 857550000
L 0 1
L 3 1

Model file is here

Minimising this model produces the following output (in debug mode)

Note: this is not a general issue with very simple models - other instances with a single contraint work fine. It's of course easy to avoid the problem by checking for obvious solutions, but if the simplicity of the model is the root cause, such simple models should consistently fail.

Versions used:

• 53.3.0
• 51.4.0

[apete]

That was interesting. I can confirm that I see the same problem.

The default LP solver does fails to recognise that it found a feasible solution, and therefore reports the problem to be infeasible (but still returns the "current" solution.)

Even if the solver reported the problem to be infeasible, the returned solution is written back to the model variables. When this happens validation is also performed, and that concludes that the solution is feasible (doesn't know about optimal or not). This is the FEASIBLE state you see inside the solution attribute.

When the results are returned the original status from the solver is used, and not the one from the model/solution validation.

1. There is some sort of problem with the default LP solver.
2. The behaviour when validating the results returned from the solver is somewhat illogical

I'll look at this, but can't promise a (date for the) fix.

If you set
model.options.experimental = true;
you'll use another LP solver that doesn't have this problem.

and if you set
model.options.debug(LinearSolver.class);
you'll see what the solver does.

[apete]

It's the magnitude of the model parameters that's causing the issue. The algorithm treats 1E-9 as "too small" and therefore pivots on the wrong element causing a small infeasibility.

Adjusting the numerical thresholds cause other tests to fail.

Short workaround for you:

1. If possible, rescale the problem
2. Use model.options.experimental = true;

[c-kob]

Many thanks!

[andreasdahlberg01]

@apete Out of curiosity, when will the new LP-solver be used as default?

[apete]

I don't know.

The main reason why it has not yet replaced the old is that it's lacking features to efficiently function as a MIP sub-solver. For pure LP models I believe it's already the better alternative.

The remaining work is not trivial and I haven't been able to focus on it lately. You can be sure it's not going away. It's fully intended to be future LP solver.