Re: [Bug-glpk] two issues

[Andrew Makhorin]

>The first was brought to my attention by JP Fasano of the COIN
>project.  When reading an MPS file, a constant in the objective is
>specified by a RHS entry for the objective.  Apparently the MPS
>convention is that the value has the opposite sign as other objective 
>coefficients since it is on the "RHS".  GLPK incorrectly treats the
>constant as the same sign.  In version 3.2.3, I believe this can be
>corrected on line 176 of glplpx8a.c:
>                  if (cqe->ind == obj) lpx_set_obj_c0(lp, cqe->val);
>should be
>                  if (cqe->ind == obj) lpx_set_obj_c0(lp, -cqe->val);
>
>For writing MPS files, I believe line 517 should be changed
>                  rhs = (make_obj && i == 0 ? obj[0] : 0.0); break;
>should be
>                  rhs = (make_obj && i == 0 ? -obj[0] : 0.0); break;
>
>JP originally noticed this when doing routine tests on the netlib
>instance e226.

This is an interesting issue. It'd be most natural to think that an rhs
specified in mps file for a free row should be processed in the same way
as rhs'es specified for other, non-free rows, in which case it should be
added to the linear form with the *opposite* sign (btw, this was done in
earlier versions of glpk). However, a while ago I met some discussion
in sci.op-research that concerns this issue (unfortunately I didn't save
an url, so I give a copy of those messages). In particular, it is seen
that cplex and pcx add rhs with the *original* sign. That's why I decided
to do the same in glpk.

Andrew Makhorin


These are copies of two messages from sci.op-research:

------------------------------------------------------------------------
"Thilo Mies" <address@hidden> wrote in message
news:address@hidden
> Hello,
>
> the problem E226 from Netlib specifies a value in the
> RHS-section unequal zero (-7.113) for the objective
> function value, often referred to as "-z" or "Tableau[0,0]".
> The result listed for E226 in Netlib.txt (-1.8751929066E+01)
> seems to ignore this entry completely.
>
> Interestingly, this value is handled differently by several well
> known solvers. Some solvers ignore the value, some add it
> to the final objective value and some subtract it.
>
>   - BPMPD:   -1.163...E+01
>   - PCX:     -2.586...E+01
>   - SOPLEX:  -1.875...E+01
>   - CPLEX:   -2.586...E+01
>   - MOSEK:   -1.163...E+01
>   - LPAKO:   -1.875...E+01
>
> I would like to know:
>
>   - How do other solvers handle this case (e.g. OSL, XPRESS)?>
>   - Someone pointed out earlier, that the original MPSX-system should
>      be the reference for problems with the MPS-format. How does this
>      system handle this case?>
>   - If one of the authors of the above mentioned solvers should read this:
>      Why do you handle this case the way you do?
>
> Thanks,
> Thilo
------------------------------------------------------------------------
From: Stefano Gliozzi (address@hidden)
Subject: Re: Interesting problem with E226 from Netlib 
 Newsgroups: sci.op-research
Date: 2002-03-28 07:16:59 PST 

> Hi,
> I checked on the MPSX/370 V2 manual (actually I was one of the developers),
> and no specification is given for an N type row with an RHS. As far as I
> remember it would probably add the RHS to the objective function (as Bob
> Daniel is pointing out). But then notice that MPS was not an IBM standard,
> but - as far as I know - a standard "agreed upon" in the ORSA around the mid
> 60s (I remember photocopies of a 1963(?) paper by Dr. Milton Gutterman
> (Amoco) drafting the rules of the standard. Then each solver had it's own
> dialect (even worse with IP and SOS variable definition), and therefore any
> exoctic definition like an RHS in a free row tents to be a matter of
> implementation in the solver code.
>
> Stefano Gliozzi
------------------------------------------------------------------------