[Octave-bug-tracker] [bug #66010] Function glpk produces incorrect output

[Hendrik K]

Follow-up Comment #11, bug #66010 (group octave):

I had another deeper look at the octave code and the glpk documentation and
its sample code:

- Scaling the LP problem is a widely used approach to improve the numerical
behavior of the dual simplex algorithm. So I think as well that msglev level 2
is appropriate to show when the scaling is requested.


- As seen below the constraints matrix with a number of values smaller than
eps() is the root issue.
 
The (octave default) presolving converts the LP problem to an equivalent LP
problem, which may be easier for solving with the simplex method than the
original one. This is attained mainly due to reducing the problem size and
improving its numeric properties (for example, by removing some inactive
constraints or by fixing some non-basic variables).
Or for contraints matrix A with such dodgy values (< eps) presolving converts
obviously the original (unsolvable) constraint matrix to a solvable albeit
incorrect "equivalent" one (as already mentioned funny things can happen in
numerical analysis for very small numbers (<eps)...). Therefore the return
code giving back by glp_simplex did not show any issues.

Or Glpk offers sorting ("glp_sort_matrix") which should never hurt in a normal
case, but which actually helps presolving to detect such ill formed contraints
better. So it is done by default in their sample code before doing the solving
(e.g. see examples/glpsol.c). 

I tried this out calling glp_sort_matrix after loading it:

diff -r 583637c89c11 libinterp/dldfcn/__glpk__.cc
--- a/libinterp/dldfcn/__glpk__.cc      
+++ b/libinterp/dldfcn/__glpk__.cc     
@@ -172,6 +172,7 @@
     }
 
   glp_load_matrix (lp, nz, rn, cn, a);
+  glp_sort_matrix(lp);
 
   if (save_pb)
     {


It works and now the error is detected when presolving is active: 
Return code status = 10 from glp_simplex, so "No primal feasible solution."

So I suggest doing this change and do always sorting (see above patch), as I
cannot hurt, as it follows the glpk use case example and as it should help.

Some further suggested changes:
===============================
a) gplk does NOT activate presolv by default (int presolve (default: GLP OFF),
so I suggest we do the same : presol (default: 0)

b) gplk has changed the default tol_piv value to 1E-9.  Currently octave still
used the (former) default value 1e-10, so I suggest we change tolpiv to
(default: 1e-9) as well.


    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?66010>

_______________________________________________
Message sent via Savannah
https://savannah.gnu.org/

signature.asc
Description: PGP signature