Andrew Makhorin | 1 Mar 19:45 2011
Picon

Re: GLPK and nonlinear programming

On Tue, 2011-03-01 at 16:31 +0000, Alan Zinober wrote:
> We currently use AMPL and MINOS to run nonlinear programming problems.
> But the free edition of AMPL does not handle large problems.
> 
> Is it possible to use GLPK or any other free package with a nonlinear 
> solver?
> 
>     Alan
> 
> 
> 

No, Glpk does not support non-linear models.
GLENN RHOADS | 5 Mar 22:57 2011
Picon

Numerical instability warning


Hi,

I have an application that uses glpk to solve millions of tiny LPs and
I get several of the following messages.

Warning: numerical instability (primal simplex, phase II)

I'm not sure about the difference between a warning and an error, and
hence, whether I need to worry about this.  I found the place in the
code where this message is printed (in the file glpspx01.c) and after
printing the message it appears to go back to the start of the main
simplex solving loop.  So I'm thinking that maybe it was able to
recover from the problem and proceeded to find an accurate optimal
solution.  Is this case?  Does the message mean that it was unable to
find an accurate solution or does the message simply supply some
information that can safely be ignored?

-- Glenn C. Rhoads
Andrew Makhorin | 6 Mar 00:00 2011
Picon

Re: Numerical instability warning

> I have an application that uses glpk to solve millions of tiny LPs and
> I get several of the following messages.
> 
> Warning: numerical instability (primal simplex, phase II)
> 
> I'm not sure about the difference between a warning and an error, and
> hence, whether I need to worry about this.  I found the place in the
> code where this message is printed (in the file glpspx01.c) and after
> printing the message it appears to go back to the start of the main
> simplex solving loop.  So I'm thinking that maybe it was able to
> recover from the problem and proceeded to find an accurate optimal
> solution.  Is this case?  Does the message mean that it was unable to
> find an accurate solution or does the message simply supply some
> information that can safely be ignored?
> 

This message just informs you that the simplex solver detects that the
current basic solution became infeasible due to excessive round-off
errors. In this case the solver automatically switches to the phase I to
recover feasibility and then continues the search. If the solver routine
returns 0, the solution can be considered as accurate within the working
precision used. Note that you can use the routine glp_check_kkt to check
if the solution satisfies to the feasibility/optimality conditions.
Andrew Makhorin | 7 Mar 15:06 2011
Picon

Re: Numerical instability warning

> So if glp_check_kkt() indicates an inaccurate solution, I could resolve
> it with scaling.  If I did that, would I need to reload the initial
> input matrix sent in via glp_load_matrix()?  I'm assuming that the
> solver won't change any values in matrix sent in so that I wouldn't
> need to store a copy of this matrix to send in when re-solving.

You don't need to reload the matrix (until it has been changed) before
reoptimization, because its copy is stored in the problem object. Note
that scaling/unscaling the matrix doesn't affect original values of
constraint coefficients; the row/column scale factors are stored
separately and applied only internally by the solver routines, i.e. all
the problem data and solution components are stored in the problem
object in an original (unscaled) form.

> 
> I also notice that glpk includes an interior-point solver.  Does this
> solver have similar numerical stability issues?  

Being a numerical procedure it may have numerical difficulties, but of
other sort.

> If it doesn't, then I
> could try it instead.
> 

Probably, yes. Please note, however, that the glpk ip solver is not
perfect and not as robust as the simplex solver. Besides, currently it
includes no crossover procedure, so it is unable to provide a basic
solution.
(Continue reading)

Mike Steglich | 7 Mar 15:37 2011
Picon

interpretation of MPS files

Hi,

I have seen that  the routines to handle MPS files were re-implemented in version 4.38.  
According to these changes I found a different behavior in the interpretation of integers w/o upper bound.
It seems that an integer w/o a defined upper bound is interpreted as a binary variable. I guess that there is
a new default value for a missing upper bound of an integer variable ( value of 1 instead of infinity in the
older versions). Am I right with these assumptions? 

Cheers,

Mike
GLENN RHOADS | 7 Mar 16:37 2011
Picon

Re: Numerical instability warning

On Sun, 06 Mar 2011 02:00:12 +0300
 Andrew Makhorin <mao <at> gnu.org> wrote:
> Note that you can use the routine glp_check_kkt to check
> if the solution satisfies to the feasibility/optimality conditions.

I tried calling lpx_check_kkt() but I'm getting a segmentation fault
generated from within this routine.  I do the following,

LPXKKT *kkt    // variable declaration
lpx_check_kkt( lp, 1, kkt );

I get a segmentation fault in _glp_lpx_check_kkt() at the line
649    kkt->pe_ae_row = ae_ind;

because the variable kkt is null (0x0)

The manual simply says "The parameter kkt is a pointer to the structure
LPXKKT, to which the routine stores the results of the check."

I was assuming that this structure is generated by the routine and that
the passed in pointer gets set to it.  Do I need to call something that
sets this kkt pointer to the LPXKKT structure?  What's wrong?

-- Glenn
glpk xypron | 7 Mar 19:06 2011
Picon
Picon

Re: Numerical instability warning

Hello Glenn,

the code is in glpk-4.45/src/glplpx01.c

You have to assign a structure of type LPXKKT to kkt before
calling lpx_check_kkt.

Best regards

Xypron

 
-------- Original-Nachricht --------
> Datum: Mon, 07 Mar 2011 10:37:55 -0500
> CC: help-glpk <at> gnu.org
> Betreff: Re: [Help-glpk] Numerical instability warning

> On Sun, 06 Mar 2011 02:00:12 +0300
>  Andrew Makhorin <mao <at> gnu.org> wrote:
> > Note that you can use the routine glp_check_kkt to check
> > if the solution satisfies to the feasibility/optimality conditions.
> 
> I tried calling lpx_check_kkt() but I'm getting a segmentation fault
> generated from within this routine.  I do the following,
> 
> LPXKKT *kkt    // variable declaration
> lpx_check_kkt( lp, 1, kkt );
> 
> I get a segmentation fault in _glp_lpx_check_kkt() at the line
> 649    kkt->pe_ae_row = ae_ind;
(Continue reading)

glpk xypron | 7 Mar 19:24 2011
Picon
Picon

Re: interpretation of MPS files

Hello Mike,

in glpk-4.45/src/glpmps01c you can find the following lines:

         else if (kind == GLP_IV)
            glp_set_col_bnds(csa->P, j, GLP_DB, 0.0, 1.0);

The GLPK default indeed seems to be an upper bound of 1.

lpsolve assumes an infinite upper bound, see
http://lpsolve.sourceforge.net/5.5/mps-format.htm

Same is true for Gurobi and ILOG CPLEX, see
http://www.gurobi.com/doc/40/refman/node580.html
http://www.lix.polytechnique.fr/~liberti/teaching/xct/cplex/reffileformatscplex.pdf

Hence I would consider the GLPK implementation as inconsistent with
the defacto standard for MPS files.

Best regards

Xypron

-------- Original-Nachricht --------
> Datum: Mon, 7 Mar 2011 15:37:13 +0100
> Betreff: [Help-glpk] interpretation of MPS files

> Hi,
> 
> I have seen that  the routines to handle MPS files were re-implemented in
(Continue reading)

Andrew Makhorin | 7 Mar 22:52 2011
Picon

Re: interpretation of MPS files

> I have seen that the routines to handle MPS files were re-implemented > in version 4.38. According to these changes I found a different > behavior in the interpretation of integers w/o upper bound. It seems > that an integer w/o a defined upper bound is interpreted as a binary > variable. I guess that there is a new default value for a missing > upper bound of an integer variable ( value of 1 instead of infinity in > the older versions). Am I right with these assumptions? > Yes. This modification was intentionally made to provide conformity with the reference specification of the MPS format given in the IBM OSL manual. Under the heading "BOUNDS Section" and the subheading "Default Bounds," the OSL manual says the following: "For integer variables, the default bounds on columns are 0 and 1."
_______________________________________________
Help-glpk mailing list
Help-glpk <at> gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk
Andrew Makhorin | 7 Mar 22:37 2011
Picon

Re: interpretation of MPS files

> I have seen that  the routines to handle MPS files were re-implemented
>  in version 4.38.  According to these changes I found a different
>  behavior in the interpretation of integers w/o upper bound. It seems
>  that an integer w/o a defined upper bound is interpreted as a binary
>  variable. I guess that there is a new default value for a missing
>  upper bound of an integer variable ( value of 1 instead of infinity in
>  the older versions). Am I right with these assumptions? 
> 

Yes. This modification was intentionally made to provide conformity with
the reference specification of the MPS format given in the IBM OSL
manual. 

Under the heading "BOUNDS Section" and the subheading "Default Bounds,"
the OSL manual says the following:

"For integer variables, the default bounds on columns are 0 and 1."

Gmane