[Coin-lpsolver] Generate all basic solutions

[Matthew Saltzman]

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