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

[Ted Ralphs]

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.

Cheers,

Ted

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
coral.ie.lehigh.edu/~ted