help-glpk
[Top][All Lists]

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

 From: Andrew Makhorin Subject: Re: [Help-glpk] "lpx_simplex" fails to find a feasible-point Date: Mon, 8 Jan 2007 22:42:39 +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

Please write the problem data to a text file, say, in mps or cplex
format (lpx_write_mps, lpx_write_cpxlp) and post it to me.

Andrew Makhorin

```