[Coin-discuss] clp alternate basis / seed

[Matthew Saltzman]

On Thu, 26 Oct 2006 bremner at unb.ca wrote:

>>>>>> "Matthew" == Matthew Saltzman <mjs at ces.clemson.edu> writes:
>    >> John J. Forrest writes:
>    >>
>    >> 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.
>
>    Matthew> I have a student starting to work on an OSI-based code
>    Matthew> for this problem.
>
>    Matthew> There's a fair bit of literature on it.  Systematic
>    Matthew> searches are necessary to avoid revisiting vertices.
>    Matthew> Chvatal's LP book describes a depth-first traversal of
>    Matthew> the edge graph of the optimal face.  There's also an
>    Matthew> algorithm based on the representation theorem that builds
>    Matthew> the vertex list and the inequality list in parallel.
>
> Hi all;
>
> There are two pretty robust research codes (cdd by Fukuda and lrs by
> Avis) for enumerating all extreme rays and vertices of a convex
> polyhedron. Lrs will also find you all lex-positive bases
> of each vertex (corresponding to a triangulation of the polar facet).
>
> Both of these work in exact arithmetic (for pivoting based enumeration
> of bases/vertices, I believe experience in extremely degenerate cases
> with floating point was pretty unpromising).  They use gmp, which is
> fast, given that it works in arbitrary precision, but nowhere near as
> fast as hardware floating point.
>
> lrs only computes lexico-positive bases (one can think of
> these as bases of a perturbed system).  If you really want all bases,
> then you will have to implement the kind of basis graph traversal the
> John alludes to. The advantage of lrs over this is that it does not
> store the many bases generated. Another alternative would be to look
> at the old version of lrs, called rs. I believe it used bland's pivot
> rule, and hence (I hope I'm not saying something idiotic here) visited
> all bases.  I don't see it around, but if you ask David Avis he might
> be able to help you.
>
> Cdd, as far as I remember, has really no concept of bases.
>
> http://cgm.cs.mcgill.ca/~avis
> http://www.ifor.math.ethz.ch/~fukuda/cdd_home/cdd.html

Thanks for the information.  I knew of these codes and we are planning to 
build on the techniques in them.  Among other things, we wanted seamless 
integration with other COIN codes.

>
> David
>
>

-- 
 		Matthew Saltzman

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