[Coin-discuss] clp alternate basis / seed

[Matthew Saltzman]

On Thu, 26 Oct 2006, John J Forrest wrote:

> Leo,
>
> You should be able to to use CoinSeedRandom(int) for seed.
>
> For degenerate bases you could pass all basic variables to primalRanging
> and pick up which pivots would not move solution.  You could repeat the
> process as long as you check you are not revisiting previous bases.  On a
> large problem might take a long time.

I have a student starting to work on an OSI-based code for this problem.

There's a fair bit of literature on it.  Systematic searches are necessary 
to avoid revisiting vertices.  Chvatal's LP book describes a depth-first 
traversal of the edge graph of the optimal face.  There's also an 
algorithm based on the representation theorem that builds the vertex list 
and the inequality list in parallel.

>
> John Forrest
>
>
>
> "Leo Lopes" <leo at sie.arizona.edu>
> Sent by: coin-discuss-bounces at list.coin-or.org
> 10/25/2006 11:28 PM
> Please respond to
> Discussions about open source software for Operations Research
> <coin-discuss at list.coin-or.org>
>
>
> To
> "Discussions about open source software for Operations Research"
> <coin-discuss at list.coin-or.org>
> cc
>
> Subject
> [Coin-discuss] clp alternate basis / seed
>
>
>
>
>
>
> Is there a simple way to get CLP to iterate between different optimal
> degenerate basis? Also, is there a way to give it a seed so that
> debugging is a little easier?
>
> Thanks,
> Leo.
>
>

-- 
 		Matthew Saltzman

Clemson University Math Sciences
mjs AT clemson DOT edu
http://www.math.clemson.edu/~mjs