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

[Matthew Saltzman]

On Fri, 2010-09-03 at 14:29 -0400, Ted Ralphs wrote: 
> 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.

Actually, it's standard terminology from NLP.  It's a mapping of the
gradient onto the the nullspace of the structural constraints.
Projection is one way to do it.  Another is to solve Ax = b for a set of
basic variables, then compute the gradient in the "reduced space" of
nonbasic variables by substituting out the basic variables in the
objective function.

> 
> 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
> >
> 
> 
> 

-- 
                Matthew Saltzman

Clemson University Math Sciences
mjs AT clemson DOT edu
http://www.math.clemson.edu/~mjs