Please let me know if there are some algorithms to get all extreme solutions (vertices) of a linear programming? (I don't know if we can use Cplex to get this solution set? )

[SonTA]

[A.L.]

On Wed, 29 Aug 2012 06:42:04 -0700 (PDT), SonTA
<taanh...@gmail.com> wrote:

Yes. It is named google

A.L.

[SonTA]

I know that the simplex method can use for solving this problem, however I do not know how to use CPLEX to get another extreme solution from the one?

[Paul]

Short answer: Change the objective function.

Slightly longer answer: This is a (somewhat) Frequently Asked Question. Search the group for previous answers about enumerating vertices. (As A. L. suggests, you can also use Google, which will turn up links to several journal articles on the subject.)

A. L.: Good to see you're still around!

[SonTA]

Many thanks!

[A.L.]

Look for Chernikova algorithm

http://www.mathnet.ru/links/d7d0006729a5900ca4c6f22757f5f2de/zvmmf7204.pdf

Unfortunately, teh above link leads to artiucle in Russian :) However,
there is enough information about this algorithm in English. Use
google

A.L.

[Gordon Sande]

Try the work of either David Avis or Komei Fukuda. They both
collaborate and do their own things.

Davis has a reverse search algorithm called lrs now at version 4.2. He
is at McGill.

Fukuda has an enumeration package called cdd based on the double
description method. There
seem to be several versions. He is at ETH Zurich.

Chernikova, cdd, etc are all descendents of Fourier elimination. They
vary in how they
do the bookkeeping and avoid redundency.

[SonTA]

In fact, my problem come from solving a Mix 0-1 linear programming by combined with a cutting plane method, but in worst case, the valid inequality which uses to generate the cutting plane is identical with a face of the polyhedron (the worst problem is that I don't know if there exists a 0-1 feasible vertex in this face of polyhedron or not?) and I try to escape form this point.

I will take a look in your reference documents!

Many thanks!