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.0e+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   henne...@web.cs.ndsu.nodak.edu
"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

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

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

[Garcia, Christophe]

Hi there,

I am new to GLPK and to LP solving in general
I created a model that is supposed to optimize the travel cost of technician 
that visit clients to repair their security system

-  I have a graph of nodes and edges representing possible paths with 
their costs

-  I have a qualification matrix to send a technician that has the 
required qualifications at a client site

Out of this I create constraints using the OPTANO modeling tools = mainly I 
create my variables, constraints and objective using OPTANO objects and it will 
translate this into a GLPK problem and then runs it

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.0e+000 inf =  2.300e+001 (23)
Perturbing LP to avoid stalling [199]...
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

Q1 : what "matrix is ill-conditioned" means ? do I have any kind of 
inconsistencies in my constraints ?
Q2 : what is this "working precision" ?
Q3 : what can be the source of this problem : my constraints ? my objective ?

Thank you for your help

Cheers
Christophe


Christophe Garcia
Resp Developpements Informatique
Stanley Security

3 chemin du Torey, 69340 Francheville, France
T +33 4 72 59 26 97 | F +33 4 72 59 26 79 | M +33 6 23 31 88 94
christophe.gar...@sbdinc.com | 
www.stanleyblackanddecker.com

[X]



___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk