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

[Nicolo' Giorgetti]

On Fri, 12 Sep 2003 14:41:32 +0400 Andrew Makhorin <address@hidden> wrote:

> From: Nicolo' Giorgetti <address@hidden>
> To: <address@hidden>
> Subject: Re: [Help-glpk] Re: Simplex method infeasible, IP method
> feasible Date: Friday, September 12, 2003 2:20 PM
> 
> >I'm doing some errors in defining the problem but I'm not able
> >to see where they are. Do you have any suggestion ?
> >Thank you very much.
> 
> CONFER!

Dear Andrew,

Sorry, I have another problem similar to the previous one.

Could you solve it both with the simplex method and the interior point 
method ? 

--------- problem: output_lpt.lpt -------------------

\* Problem: Unknown *\

Minimize
 obj: + x(1)

Subject To
 r(1): - x(1) + x(2) + x(3) <= 0
 r(2): + x(1) <= 68.855034718
 r(3): - 0.222520933956 x(2) + 0.974927912182 x(3) <= 39.4828617494
 r(4): - 0.900968867902 x(2) + 0.433883739118 x(3) <= 5.23377925511
 r(5): - 0.900968867902 x(2) - 0.433883739118 x(3) <= -73.0421245614
 r(6): + 0.623489801859 x(2) - 0.781831482468 x(3) <= 76.0438443135

Bounds
 -1000000 <= x(1) <= 1000000
 -1000000 <= x(2) <= 1000000
 -1000000 <= x(3) <= 1000000

End

-------------------------------------------------------


I solved it using glpsol and I obtained two different outputs:

--------------- Simplex ------------------------
$glpsol --lpt output_lpt.lpt

lpt_read_prob: reading LP data from `output_lpt.lpt'...
lpt_read_prob: 3 variables, 6 constraints
lpt_read_prob: 19 lines were read
lpx_simplex: original LP has 6 rows, 3 columns, 12 non-zeros
lpx_simplex: presolved LP has 5 rows, 3 columns, 11 non-zeros
gm_scal: max / min = 4.494e+000
gm_scal: max / min = 3.016e+000
lpx_adv_basis: size of triangular part = 5
      0:   objval = -2.000000000e+006   infeas =  1.000000000e+000 (0)
      4:   objval =  6.885503472e+001   infeas =  2.000844258e-012 (0)
*     4:   objval =  6.885503472e+001   infeas =  5.401980374e-006 (0)
*     5:   objval =  6.885504317e+001   infeas =  7.015617570e-006 (0)
lpx_simplex: numerical instability (primal simplex, phase II)
      5:   objval =  6.885504317e+001   infeas =  1.000000000e+000 (0)
      5:   objval =  6.885504317e+001   infeas =  1.000000000e+000 (0)
PROBLEM HAS NO FEASIBLE SOLUTION
lpx_simplex: cannot recover undefined or non-optimal solution
Time used:   0.0 secs
Memory used: 0.1M (80744 bytes)

------- Interior point method ------------------------

$ glpsol --interior --lpt output_lpt.lpt

lpt_read_prob: reading LP data from `output_lpt.lpt'...
lpt_read_prob: 3 variables, 6 constraints
lpt_read_prob: 19 lines were read
lpx_interior: original LP problem has 6 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.522900440e+005; rpi = 3.0e-001; rdi = 1.1e+000; gap =
2.0e-001  
  1: F = -4.073474860e+004; rpi = 9.2e-002; rdi = 1.1e-001; gap
= 1.8e-001  
  2: F = -1.149990823e+003; rpi = 1.1e-002; rdi = 1.3e-002;
gap = 2.4e-002  
  3: F = -4.535524941e+001; rpi = 1.1e-003; rdi = 1.3e-003; gap =
2.5e-003   
  4: F =  6.094629906e+001; rpi = 1.2e-004; rdi= 1.3e-004; gap =
3.2e-004  
  5: F =  7.301168842e+001; rpi = 1.5e-005; rdi = 1.3e-005; gap =
5.8e-005  
  6: F =  7.071401526e+001; rpi = 2.3e-006; rdi = 1.7e-006; gap =
7.9e-006  
  7: F =  6.904379861e+001; rpi= 2.3e-007; rdi = 1.7e-007; gap= 8.1e-007
  8: F =  6.887392223e+001; rpi = 2.3e-008; rdi= 1.7e-008; gap= 8.1e-008
  9: F = 6.885693739e+001; rpi = 2.3e-009; rdi= 1.7e-009; gap= 8.1e-009
OPTIMAL SOLUTION FOUND 
Time used:   0.0 secs 
Memory used: 0.1M(58588 bytes)


I solved it with the barrier algorithm of CPLEX and I have obtained the
following output:

------------ from CPLEX --------------------

Problem 'output_lpt.lpt' read.
Read time =    0.10 sec.
Tried aggregator 1 time.
LP Presolve eliminated 1 rows and 0 columns.
Reduced LP has 5 rows, 3 columns, and 11 nonzeros.
Presolve time =    0.02 sec.
Number of nonzeros in lower triangle of A*A' = 10
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.00 sec.
Summary statistics for Cholesky factor:
  Rows in Factor            = 5
  Integer space required    = 5
  Total non-zeros in factor = 15
  Total FP ops to factor    = 55
 Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf      
      0 -3.9574734e+005 -1.1000138e+007 3.10e+006 2.08e+005 1.00e+001
   1 -3.1615429e+005 -1.7627440e+006 7.28e+005 4.89e+004 1.98e+000
   2  2.3392532e+003 -9.5588211e+004 3.41e+004 2.29e+003 6.48e-015
   3  6.9185003e+001 -1.8265269e+002 5.61e+000 3.77e-001 6.23e-015
   4  6.8912782e+001  6.8129432e+001 1.09e+000 7.31e-002 4.27e-015
   5  6.8846880e+001  6.8615031e+001 3.32e-002 2.13e-003 1.67e-013
   6  6.8854183e+001  6.8835404e+001 1.96e-003 2.26e-015 4.06e-015
   7  6.8854957e+001  6.8853283e+001 1.86e-004 2.33e-010 1.96e-015
   8  6.8855028e+001  6.8854909e+001 2.43e-005 1.63e-016 1.24e-015
   9  6.8855031e+001  6.8855056e+001 1.89e-005 3.09e-015 2.82e-015
  10  6.8855035e+001  6.8855067e+001 9.21e-006 3.58e-015 1.90e-015
  11  6.8855035e+001  6.8855071e+001 7.90e-006 6.67e-015 1.77e-015
 Barrier cannot determine infeasibility.
Barrier time =    0.05 sec.

Primal crossover.
  Primal:  Fixed no variables.
  Dual:  Fixing 1 variable.
        0 DMoves:  Infeasibility 0.00000000e+000  Objective
6.88550432e+001  Dual:  Pushed 1, exchanged 0.
Using devex.
Removing shift (1).
Total crossover time =    0.08 sec.

Primal simplex - Infeasible:  Infeasibility =   8.4553621207e-006
Solution time =    0.18 sec.  Iterations = 0 (0)


Best Regards,
Nicolo'.