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

[Matthew Saltzman]

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