[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.000000000e+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
address@hidden | www.stanleyblackanddecker.com