Re: [Help-glpk] ERROR = basis matrix is singular to working precision

[Michael Hennebry]

On Thu, 30 Aug 2018, Garcia, Christophe wrote:

> I have a problem understanding GLPK behavior with my model when I get this 
> error message :
>
> GLPK Simplex Optimizer, v4.65
> 5157 rows, 5980 columns, 892762 non-zeros
>      0: obj =  0.000000000e+000 inf =  2.300e+001 (23)
> Perturbing LP to avoid stalling [199]...

GLPK is temporarily modifying yur problem so that it can keep going.

> Warning: basis matrix is ill-conditioned (cond = 1.13e+015)
> Warning: basis matrix is ill-conditioned (cond = 1.45e+015)
> Warning: basis matrix is ill-conditioned (cond = 1.48e+015)
> Warning: basis matrix is ill-conditioned (cond = 2.2e+014)
> Error: basis matrix is singular to working precision (cond = 1.54e+017)
>
> I thought it could be numeric overflow so I added a divider to all my values in 
> the constraints and the objective function but it did not solve my problem

Condition numbers are dimesionless.
Such scaling does not affect them.
There is scaling that might help,
but I think that GLPK does that on its own.

> Q1 : what "matrix is ill-conditioned" means ? do I have any kind of 
> inconsistencies in my constraints ?

The condition number is equivalent to the magnitude
of a matrix time the magnitude of its inverse.
It is a measure of how much errors in the
inputs could be magnified in the output,
even with exact arithmetic.
10**15=1000**5
1024**5=2**50

> Q2 : what is this "working precision" ?

double precision is often 53 bits.
See above.

> Q3 : what can be the source of this problem : my constraints ? my objective ?

Not your objective.

Two constraints, almost the same and both binding might produce this.

I'd suggest telling GLPK to use the dual simplex method.
If that does not work, I'd turn off preprocessing.
If that does not work, I'd try dropping constraints (not variable bounds)
until I got a solution.
If it's feasible, done.
Otherwise, use it as the basis from which to start the dual simplex method.


--
Michael   address@hidden
"Sorry but your password must contain an uppercase letter, a number,
a haiku, a gang sign, a heiroglyph, and the blood of a virgin."
                                                             --  someeecards