help-glpk
[Top][All Lists]

## [Help-glpk] "lpx_simplex" fails to find a feasible-point

 From: Carl Ponder Subject: [Help-glpk] "lpx_simplex" fails to find a feasible-point Date: Mon, 8 Jan 2007 22:15:22 +0300

```
I have a fairly trivial LP problem that I'm trying to
solve using GLPK,
but it says there's no feasible-point even though I can compute one by
hand. Here is the coefficient matrix:

1    0    -0.5055     0.0000     0.0000    0    0    0    0    0    0
0    1    -0.4207     0.0000     0.0000    0    0    0    0    0    0
1    0     0.0000    -0.4779     0.0000    0    0    0    0    0    0
0    1     0.0000    -0.3355     0.0000    0    0    0    0    0    0
1    0     0.0000     0.0000    -0.4023    0    0    0    0    0    0
0    1     0.0000     0.0000    -0.1920    0    0    0    0    0    0
1    0  -252.9900     0.0000     0.0000    1    0    0    0    0    0
0    1  -210.5600     0.0000     0.0000    0    1    0    0    0    0
1    0     0.0000  -239.1900     0.0000    0    0    1    0    0    0
0    1     0.0000  -167.9000     0.0000    0    0    0    1    0    0
1    0     0.0000     0.0000  -201.3400    0    0    0    0    1    0
0    1     0.0000     0.0000   -96.0900    0    0    0    0    0    1

The first six rows are set as >=0.0 and the second six are set as
=0.0.
I'm minimizing the sum of the last six column-variables, that absorb
the "residue" of what might otherwise make the last six rows nonzero.
All variables are set as >=0.0. An example of a feasible-point is the
following, in order of the columns they mutliply with:

201.34
96.09
0.796
0.842
1
0.05
89.84
0.07
53.78
0
0

Is this matrix degenerate in some way that breaks GLPK? I've
tried the
various combinations of lpx_simplex, lpx_interior, lpx_scale_prob, and
LPX_K_PRESOL=1. I assume that GLPK is working as designed, since the
"make check" passes okay. I'm running on an IBM Thinkpad
running RHEL 4
Linux. Thanks,

Carl Ponder

```
 I have a fairly trivial LP problem that I'm trying to solve using GLPK, but it says there's no feasible-point even though I can compute one by hand. Here is the coefficient matrix:   1    0    -0.5055     0.0000     0.0000    0    0    0    0    0    0   0    1    -0.4207     0.0000     0.0000    0    0    0    0    0    0   1    0     0.0000    -0.4779     0.0000    0    0    0    0    0    0   0    1     0.0000    -0.3355     0.0000    0    0    0    0    0    0   1    0     0.0000     0.0000    -0.4023    0    0    0    0    0    0   0    1     0.0000     0.0000    -0.1920    0    0    0    0    0    0   1    0  -252.9900     0.0000     0.0000    1    0    0    0    0    0   0    1  -210.5600     0.0000     0.0000    0    1    0    0    0    0   1    0     0.0000  -239.1900     0.0000    0    0    1    0    0    0   0    1     0.0000  -167.9000     0.0000    0    0    0    1    0    0   1    0     0.0000     0.0000  -201.3400    0    0    0    0    1    0   0    1     0.0000     0.0000   -96.0900    0    0    0    0    0    1 The first six rows are set as >=0.0 and the second six are set as =0.0. I'm minimizing the sum of the last six column-variables, that absorb the "residue" of what might otherwise make the last six rows nonzero. All variables are set as >=0.0. An example of a feasible-point is the following, in order of the columns they mutliply with:     201.34      96.09       0.796       0.842       1       0.05      89.84       0.07      53.78       0       0 Is this matrix degenerate in some way that breaks GLPK? I've tried the various combinations of lpx_simplex, lpx_interior, lpx_scale_prob, and LPX_K_PRESOL=1. I assume that GLPK is working as designed, since the "make check" passes okay. I'm running on an IBM Thinkpad running RHEL 4 Linux. Thanks,                 Carl Ponder