[Osi] dual bound on the primal

[Lou Hafer]

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