[Help-glpk] Re: Simplex method infeasible, IP method feasible

[Andrew Makhorin]

>Using the API routines I set up the basic LP problem
>
>     min  c'x
>     s.to Ax <= b
>          lb <= x <= ub
>          x real
>
>where
>
>c=[1 0 0]',
>A=[ -1  1        1
>     1  0        0
>     0 -0.22252  0.97493
>     0 -0.90097  0.43388
>     0 -0.90097 -0.43388
>     0  0.62349 -0.78183],
>b=[  0
>    68.855
>    39.483
>     5.2338
>   -73.042
>    76.044],
>
>lb=[-1e6 -1e6 -1e6]',
>ub=[ 1e6  1e6  1e6]',
>
>This problem is infeasible. In fact I solved it with
>the lpx_simplex() function and lpx_get_status() returns LPX_NOFEAS
>(183). 
>I have tried then to solve it with the interior point method, by means
>of the lpx_interior() function, but the lpx_get_ips_stats()
>returns LPX_T_OPT(151) that is an optimal solution has been found. 
>How is it possible ? 

Why infeasible? I tried your example with both simplex and interior.
Here are the results below.

------------------------------------------------------------------------
param m;
param n;
param A{1..m,1..n};
param b{1..m};
param c{1..n};
param lb{1..n};
param ub{1..n};
var x{j in 1..n} >= lb[j] <= ub[j];
minimize Z: sum{j in 1..n} c[j] * x[j];
s.t. row{i in 1..m}: sum{j in 1..n} A[i,j] * x[j] <= b[i];
data;
param m := 6;
param n := 3;
param c := 1 1, 2 0, 3 0;
param A : 1 2 3 :=
1    -1  1        1
2     1  0        0
3     0 -0.22252  0.97493
4     0 -0.90097  0.43388
5     0 -0.90097 -0.43388
6     0  0.62349 -0.78183 ;
param b := 
1     0
2    68.855
3    39.483
4     5.2338
5   -73.042
6    76.044 ;
param lb default -1e6;
param ub default 1e6;
end;
------------------------------------------------------------------------
38 lines were read
Generating Z...
Generating row...
Model has been successfully generated
lpx_simplex: original LP has 7 rows, 3 columns, 13 non-zeros
lpx_simplex: presolved LP has 5 rows, 3 columns, 11 non-zeros
gm_scal: max / min = 4.494e+00
gm_scal: max / min = 3.016e+00
lpx_adv_basis: size of triangular part = 5
      0:   objval =  -2.000000000e+06   infeas =   1.000000000e+00 (0)
      4:   objval =   6.885450326e+01   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
------------------------------------------------------------------------
Status:     OPTIMAL
Objective:  Z = 68.85450326 (MINimum)

  Row name   St   Activity     Lower bound   Upper bound    Marginal
------------ -- ------------- ------------- ------------- -------------
Z            B        68.8545
row[1]       NU             0                           0            -1
row[2]       B        68.8545                      68.855
row[3]       B       -43.5373                      39.483
row[4]       B       -93.4892                      5.2338
row[5]       NU       -73.042                     -73.042      -1.44146
row[6]       NU        76.044                      76.044     -0.479103

Column name  St   Activity     Lower bound   Upper bound    Marginal
------------ -- ------------- ------------- ------------- -------------
x[1]         B        68.8545        -1e+06         1e+06
x[2]         B        92.4178        -1e+06         1e+06
x[3]         B       -23.5632        -1e+06         1e+06
------------------------------------------------------------------------
38 lines were read
Generating Z...
Generating row...
Model has been successfully generated
lpx_interior: original LP problem has 7 rows and 3 columns
lpx_interior: transformed LP problem has 9 rows and 12 columns
Factorizing S = A*A' symbolically...
nz(A) = 24
nz(S) = 32 (upper triangular part)
nz(U) = 32
Guessing initial point...
Optimization begins...
0: F =   2.522900541e+05; rpi =  3.0e-01; rdi =  1.1e+00; gap =  2.0e-01
1: F =  -4.073511216e+04; rpi =  9.2e-02; rdi =  1.1e-01; gap =  1.8e-01
2: F =  -1.149989554e+03; rpi =  1.1e-02; rdi =  1.3e-02; gap =  2.4e-02
3: F =  -4.535554945e+01; rpi =  1.1e-03; rdi =  1.3e-03; gap =  2.5e-03
4: F =   6.094577995e+01; rpi =  1.2e-04; rdi =  1.3e-04; gap =  3.2e-04
5: F =   7.301120469e+01; rpi =  1.5e-05; rdi =  1.3e-05; gap =  5.8e-05
6: F =   7.071345903e+01; rpi =  2.3e-06; rdi =  1.7e-06; gap =  7.9e-06
7: F =   6.904303590e+01; rpi =  2.3e-07; rdi =  1.7e-07; gap =  8.1e-07
8: F =   6.887344654e+01; rpi =  2.3e-08; rdi =  1.7e-08; gap =  8.1e-08
9: F =   6.885634138e+01; rpi =  2.3e-09; rdi =  1.7e-09; gap =  8.1e-09
OPTIMAL SOLUTION FOUND
------------------------------------------------------------------------
Status:     INTERIOR OPTIMAL
Objective:  Z = 68.85634138 (MINimum)

  Row name        Activity     Lower bound   Upper bound    Marginal
------------    ------------- ------------- ------------- -------------
Z                     68.8563                                         0
row[1]              0.0024996                           0      -1.09566
row[2]                68.8563                      68.855    -0.0956563
row[3]               -43.5318                      39.483  -1.40115e-05
row[4]               -93.4859                      5.2338  -1.68234e-05
row[5]               -73.0434                     -73.042      -1.57935
row[6]                76.0391                      76.044      -0.52496

Column name       Activity     Lower bound   Upper bound    Marginal
------------    ------------- ------------- ------------- -------------
x[1]                  68.8563        -1e+06         1e+06             0
x[2]                  92.4166        -1e+06         1e+06             0
x[3]                 -23.5578        -1e+06         1e+06             0