[Coin-discuss] clp alternate basis / seed

[bremner at unb.ca]

>>>>> "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

David

-------------- next part --------------
-- 
David Bremner                        Associate Professor, UNB Computer Science
bremner at unb.ca                              Cross Appointment, UNB Mathematics
+1 (506) 447 3300                     Atlantic Scientific Director, MITACS NCE
http://www.cs.unb.ca/~bremner                             http://www.mitacs.ca