[Coin-lpsolver] Question about the use of pivot()

[John J Forrest]

Sonja,

>From your description e.g. sequenceIn it sounds as if you are using Clp
directly rather than through OsiClp.  That will be more efficient and will
work much better in the long run, but there are tricky things e.g. there
are external solution arrays and internal (possibly scaled) arrays.

Assuming that the first step in your algorithm is to evaluate all legal
pivots and get solutions etc I would start from primalRanging in ClpSimplex
ClpSimplexOther.  As it stands it takes a list of variables and returns how
much each can increase/decrease before a pivot and which variable replaces
it.  In your case the only interesting variables are the non-basic ones.
However that will only give the adjacent feasible vertices (and will only
give one in the case of a tie).  It sounds as if you want to get all
vertices (for which the basis will not be singular).

This can be done with some work.  Basically primalRanging uses a method
checkPrimalRatios to select outgoing variable.  A similar method could look
at all outgoing variables where updated incoming column has a reasonably
sized pivot.  If you are ready to try, I would add a new method which a
hack of primalRanging and a new method to replace checkPrimalRatios.  I
don't know what output you want - one possibility might be a list of

sequenceIn
valid sequenceOut
objective value
bool whether feasible with original rhs

If you care to get something together that works (or almost works) with a
test driver I can help you with some details.  If you can persuade the
community that such a method could be useful then I can put it into Clp.

John Forrest


                                                                                                                    
  From:       "Sonja Friedrich" <sfr83 at gmx.de>                                                                      
                                                                                                                    
  To:         coin-lpsolver at list.coin-or.org                                                                        
                                                                                                                    
  Date:       23.01.2008 10:05                                                                                      
                                                                                                                    
  Subject:    [Coin-lpsolver] Question about the use of pivot()                                                     
                                                                                                                    





Hello,

I've just started using CLP and now I have some little problems. I
hope you can help me. Here are my questions and a short description of
what I want to do:
I have a algorithm that starts at the optimal vertex and then searches
the tree, spanned by the Simplex algorithm over all vertices of my
polyhedron backwards. So it needs all possible bases.
What I want to do is, start at the optimal vertex and then go to all
the adjacent vertices. Currently I'm using pivot(). Pivot() needs
sequenceIn and sequenceOut to be set, but it doesn't allow all
possible combinations. Especially it is not possible to go "backwards"
(with regard to the objective value). Is pivot() the right function
for this tast? Is there any better way to come to every adjacent
vertex?

The next problem is, that pivot() doesn't update the objective value,
which I also need. Maybe it does the update, but I do not know how to
get it. Solution(), getColSolution() and primalColumnSolution() have
their old values, just as before pivot() or are 0. Therefore the
objective Value hasn't got its right value. Is there any chance to get
the right objective value?

Thanks and greetings

Sonja Friedrich
TU Darmstadt
_______________________________________________
Coin-lpsolver mailing list
Coin-lpsolver at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-lpsolver