[Osi] dual bound on the primal

[Matthew Saltzman]

An alternative view of the linear algebra is to consider writing the
bound constraints explicitly from the start.  Then primal is

max cx
st  Ax = b
     x <= u
    -x <= -l

and the dual is

min yb + wu - zl
st  yA + w - z = c

It's clear, then, that altering the bound slightly alters the primal
solution--hence the primal objective--and the dual objective (if the
bound is tight, i.e., if the complementary dual w_j or z_j is nonzero).

The algebra works the same, no matter whether the bounds are handled
implicitly by the algorithm.

I'm ignoring some minor but annoying complications due to degeneracy
(tight bound, but zero dual).

On Wed, 2010-10-20 at 09:55 -0700, Lou Hafer wrote: 
> Kyle,
> 
> 	Linear algebra and plain ascii don't really play well together, but
> here's a start.
> 
> 	Consider the standard primal <-> dual pair
> 
>    max cx              min yb
>        Ax <= b   <=>       yA >= c
>    l <= x <= u             y >= 0
> 
> 	You have bounded variables l <= x <= u. In a modern simplex
> implementation, these are handled implicitly by the algorithm; they are
> not explicit constraints. Now, recall
> 
>   x<B> = inv(B)b - inv(B)Nx<N>
>   z = c<B>inv(B)b + (c<N> - c<B>inv(B)N)x<N>
>   y = c<B>inv(B)
>   cbar = (c<N> - c<B>inv(B)N) = (c<N> - yN)
> 
> where B is the basic partition, N the nonbasic partition, inv(B) is the
> basis inverse, c<B> and c<N> the basic and nonbasic objective
> coefficients, x<B> the basic variables, y the duals, cbar the reduced
> costs.
> 
> Suppose you were to add -x<j> <= -l<j> as an explicit constraint in your
> constraint system. x<j> is now basic, and the basis becomes
> 
>   B' = B a<j>   and the basis inverse is inv(B') = inv(B)  inv(B)a<j>
>        0  -1                                         0       -1
> 
> Your new duals are y' = [c<B> c<j>]inv(B'). Do the linear algebra and
> you'll see that the new dual is -(c<j> - c<B>inv(B)a<j>), the negative
> of the reduced cost of x<j>.
> 
> For a really exhaustive look at the correspondence between primal and
> dual, try ftp://fas.sfu.ca/pub/cs/TR/1998/CMPT1998-21.pdf
> 
> 						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