[Coin-lpsolver] Generate all basic solutions

[Francois Margot]

Look at

Avis, David; Fukuda, Komei A basis enumeration algorithm for linear systems with geometric applications.  Appl. Math. Lett.  4  (1991),  no. 5, 39--42. 90C27

Avis, David; Fukuda, Komei A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. ACM Symposium on Computational Geometry (North Conway, NH, 1991).  Discrete Comput. Geom.  8  (1992),  no. 3, 295--313. (Reviewer: Henk J. A. M. Heijmans) 68U05 (52B55 65Y25)

Avis, David; Fukuda, Komei Reverse search for enumeration. First International Colloquium on Graphs and Optimization (GOI), 1992 (Grimentz).  Discrete Appl. Math.  65  (1996),  no. 1-3, 21--46. 05C30 (05A15)

Francois

On Wed, 26 Oct 2005, Matthew Saltzman wrote:

> Sorry, I neglected to copy the list on my first reply.
>
> On Thu, 27 Oct 2005, Spencer Fung wrote:
>
>> Dear Matthew,
>> 
>> Thanks for your quick response. Can you recommend some solvers that can
>> achieve the purpose? Do you think CPLEX does?
>
> CPLEX does not have a built-in function to do this either, but I beleive some 
> of the codes referenced in the LP FAQ use the CPLEX callable library (but not 
> via the COIN-OR OSI).
>
>> 
>> I cannot get the Chvatal's book at the moment, do you know any online
>> materials describe the algorithm you mentioned.
>
> The algorithm in Chvatal's book is a breadth-first search of the graph whose 
> vertices are the vertices of the polyhedron and whose edges are the 
> one-dimensional faces.
>
> Chvatal references the following:
>
> Dyer and Proll (1977), An algorithm for determining all extreme points of a 
> polyhedron, Math Programming 12:81-96.
>
> Matthiess and Rubin (1980), A survey and comparison of methods for finding 
> all vertices of convex polyhedral sets, Math of OR 5:167-185.
>
> Matthiess and Schmidt (1980), Computational results on an algorithm for 
> finding all vertices of a polytope, Math Programming 18:308-329.
>
> Chvatal is from 1983, so there are likely to be later references, but I don't 
> have any handy at the moment.
>
>> 
>> Spencer
>> 
>> -----Original Message-----
>> From: Matthew Saltzman [mailto:mjs at ces.clemson.edu]
>> Sent: Thursday, October 27, 2005 12:05 AM
>> To: Spencer Fung
>> Subject: Re: [Coin-lpsolver] Generate all basic solutions
>> 
>> On Wed, 26 Oct 2005, Spencer Fung wrote:
>> 
>>> Dear all,
>>> 
>>> 
>>> 
>>> Does anyone know how to generate all basic solutions with CLP?
>> 
>> There's nothing built into CLP to do this at the moment, although I am
>> working on some codes for this.  There are a number of codes on the Web
>> that don't use CLP (see the LP FAQ
>> (http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html).
>> If you want to use CLP, it would not be too difficult to implement the
>> algorithm described in Chvatal's book.
>> 
>>> 
>>> 
>>> 
>>> Thanks.
>>> 
>>> 
>>> 
>>> Spencer
>>> 
>>> 
>> 
>> 
>
> -- 
> 		Matthew Saltzman
>
> Clemson University Math Sciences
> mjs AT clemson DOT edu
> http://www.math.clemson.edu/~mjs
>
>