[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] basis matrix is singular, but not in the saved model
From: |
Mark Gritter |
Subject: |
[Help-glpk] basis matrix is singular, but not in the saved model |
Date: |
Fri, 22 Jun 2007 18:51:17 -0700 |
I am using GLPK to solve some game-theory problems with dense matrices
(as I have asked about before.) Andrew's suggestion to use column
generation has been very useful (thank you!)
In my current program I got the following error while running
lpx_simplex on the main LP model:
* 44250: objval = 1.482023718e+00 infeas = 9.060097142e-14 (0)
* 44300: objval = 1.481789163e+00 infeas = 9.819968853e-16 (0)
* 44350: objval = 1.481729328e+00 infeas = 6.997407302e-14 (0)
spx_invert: the basis matrix is singular
spx_simplex: numerical problems with basis matrix
spx_simplex: sorry, basis recovery procedure not implemented yet
However, when I run the saved model through glpsol it arrives at a solution:
lpx_read_cpxlp: reading problem data from `test.cplex'...
lpx_read_cpxlp: 1687 rows, 2248 columns, 1898434 non-zeros
lpx_read_cpxlp: 949119 lines were read
lpx_write_mps: writing problem data to `test.mps'...
lpx_simplex: original LP has 1687 rows, 2248 columns, 1898434 non-zeros
lpx_simplex: presolved LP has 1687 rows, 2248 columns, 1898434 non-zeros
lpx_adv_basis: size of triangular part = 1687
0: objval = 0.000000000e+00 infeas = 1.000000000e+00 (0)
200: objval = 1.344510660e+00 infeas = 3.297820208e-01 (0)
400: objval = 1.881226167e+00 infeas = 1.941659565e-01 (0)
...
* 2400: objval = 1.481966312e+00 infeas = 7.559774601e-14 (0)
* 2600: objval = 1.481709975e+00 infeas = 0.000000000e+00 (0)
* 2648: objval = 1.481704489e+00 infeas = 2.057120297e-17 (0)
OPTIMAL SOLUTION FOUND
Right now my loop works something like this:
1. Save the model to file
2. Solve restricted problem with lpx_simplex
3. Look for additional rows (first-player strategies that improve his
score). If found, add them to the model and go back to step #1.
4. Look for additional columns (second-player strategies) with
negative reduced cost. If found, add them to the model and repeat
step #1.
Should I reset the basis before running the simplex method again?
Could I recover from this error by resetting the basis and rerunning
lpx_simplex?
Thanks,
Mark
- [Help-glpk] basis matrix is singular, but not in the saved model,
Mark Gritter <=