[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-glpk] two issues
From: |
Andrew Makhorin |
Subject: |
Re: [Bug-glpk] two issues |
Date: |
Mon, 13 Jan 2003 19:21:06 +0300 |
>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
------------------------------------------------------------------------