[Clp] Question about ClpPrimalColumnPivot.PivotColumn

[Dami Choi]

The Packed CoinIndexedVector updates has cost updates - for normal LP
28         that is just +-weight where a feasibility changed.  It also has
29         reduced cost from last iteration in pivot row
30         Can just do full price if you really want to be slowI can't seem
to reply directly to the thread since I wasn't subscribed to the mailing
list, so I'm making a new thread, sorry about that.

> dj stands for the reduced costs of variables.  The sections are for
> structural variables and row slacks.  We are going back to the 1960's
> when the best LP code was CEIR Inc and CEIR Ltd code LP/90/94 for the
> IBM 9094 with 36 bit words - so six 6 bit characters - so names were
> kept short - also it made it easier when using punched cards.  So you
> may see short names referenced in code e.g. FTRAN (Forward
> transformation -> columnUpdate).  The input column would be updated with
> the computer tapes going forwards.  Then the next update for the product
> form of the update would be written to the end of a tape.  For the next
> iteration to obtain a pricing vector the tapes would be read backwards
> (BTRAN).

I'm sorry for the sutpid question yet again, but what do you mean by
structural variables and row slacks? Is this definition of section
consistent throughout all the functions that have the section argument
(e.g. ClpSimplex::solutionRegion, costRegion, lowerRegion,
upperRegion)?

> >* In the PivotColumn function in ClpPrimalColumnPivot, what is the purpose
*> >* of the arguments updates and sparerow/columns? If I understand
*> >* correctly, only updates contains some information from the previous
*> >* iteration, and sparerow/column aids in the computation in the process of
*> >* updating the costs. But in what part of the simplex algorithm does this
*> >* updating cost correspond to, and why is it in the PivotColumn function
*> >* and not in the primal function?
*
> Algorithms have advanced since then and there are different pricing
> methods - virtual functions in C++ make it easier to keep these
> separate.  As vectors are sparse the spareRow etc CoinIndexedVectors are
> work arrays which are empty at beginning and end so that just non-zero
> elements are referenced and there is no overhead if a vector is not
> referenced by one of the pricing methods.

I'm sorry if you explained and I didn't understand, but I still don't
understand what is saved in updates. For instance, why is it used to
update the reduced costs in the beginning of the Dantzig pivot
algorithm (https://projects.coin-or.org/Clp/browser/trunk/src/ClpPrimalColumnDantzig.cpp#L80)?

In the comments it says:

The Packed CoinIndexedVector updates has cost updates - for normal LP
that is just +-weight where a feasibility changed.  It also has
reduced cost from last iteration in pivot row
Can just do full price if you really want to be slow

but I don't understand, what does "feasibility change" mean, and how
can we access the reduced cost in pivot row? I think I'm confused
because I thought updating the tableau (including the reduced costs)
was part of the simplex algorithm, and isn't specific to the specific
pivoting algorithm.


Thank you,


Dami
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20200917/a83b7cde/attachment.html>