[Osi] Question re. meaning of OsiSimplex::getReducedGradient

Ted Ralphs ted at lehigh.edu
Fri Sep 3 14:29:55 EDT 2010

Well, I think that "reduced gradient" is mixing two different
terminologies. It seems to me that "reduced" really only make sense as
a modifier to "cost." The reduced cost (as I usually define) _is_ a
(sub)gradient of the value function of the linear program (with the
variable bounds considered to be parametric). I'm not sure what a
"reduced gradient" would be. It should really be just a "subgradient,"
technically speaking.

Generally, I agree with Matt, though. The way the reduced cost is
defined in most LP textbooks, it's precisely the gradient. I think it
would be confusing and not terribly useful to define it otherwise.
It's easy enough to take absolute value if you need to.



On Fri, Sep 3, 2010 at 1:52 PM, Matthew Saltzman <mjs at clemson.edu> wrote:
> My initial sense is that this should be the true reduced gradient.  I
> reason that when I develop the revised simplex method, I'd write the
> basis equations the same way, whether I'm maximizing or minimizing:
> Solve structural constraints Ax = b for x_B:
>        x_B = B^{-1} b - B^{-1}N x_n
> Substitute into z = c x:
>        z = c_B B^{-1} b + (c_N - c_B B^{-1} N) x_N
> The optimality test then changes depending on whether I'm minimizing
> (entering variable has negative coefficient in the z row) or maximizing
> (entering variable has positive coefficient in the z row).  So my sense
> is that if I asked for this vector, I'd expect the sign on a coefficient
> to tell me the actual effect (increase or decrease) on the objective of
> increasing the corresponding variable.
> In the alternative, I guess positive coefficients always improve the
> objective, whether maximizing or minimizing.  For myself, I find that
> rather counterintuitive and potentially ambiguous.  (Maybe negative
> coefficients should always improve the objective?)  I notice Lou didn't
> specify which way around he'd adjust the signs, only that they'd be
> consistent WRT improvement.  Anyone want to argue for it?  Which way
> around is the right way?
> On Fri, 2010-09-03 at 10:18 -0700, Lou Hafer wrote:
>> Folks,
>>       In the process of writing up the unit test for the OsiSimplex API, I've
>> run into a question of interpretation that needs to be resolved.
>>       The original spec for getReducedGradient is this:
>> // Get the reduced gradient for the cost vector c
>>   virtual void getReducedGradient (double *columnReducedCosts,
>>                                  double *duals,
>>                                  const double * c);
>> The question is straightforward:  should the signs of columnReducedCosts and
>> duals be adjusted for maximisation / minimisation?  Put in another way, is
>> gradient a different thing from reduced costs and duals?
>>       I have no strong opinion, but it affects the way the test will be
>> written and it should be clarified in the documentation.  In the absence of any
>> replies, I'm going to go with the meaning implied by the parameter names (i.e.,
>> sign should be appropriate for maximisation / minimisation).
>>                                                       Lou
>> _______________________________________________
>> Osi mailing list
>> Osi at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/osi
> --
>                Matthew Saltzman
> Clemson University Math Sciences
> mjs AT clemson DOT edu
> http://www.math.clemson.edu/~mjs
> _______________________________________________
> Osi mailing list
> Osi at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/osi

Dr. Ted Ralphs
Associate Professor, Lehigh University
(610) 628-1280
ted 'at' lehigh 'dot' edu

More information about the Osi mailing list