I am trying to find all optimal solutions of my LP problem. Is it

possible to find all alternate optimal solutions?

\

In my humble opinion, a LP either has a unique solution, or has a

continuum of solution in case of degeneracy.

In the latter case, there are an infinity of solutions. Hence finding

“all alternate optimal solutions” might be tedious.

However, providing different starting points may end up in different

solutions, in some cases.

There must be better approaches to this.

On 10 nov, 14:46, halegk wrote:

I am trying to find all optimal solutions of my LP problem. Is it

possible to find all alternate optimal solutions?

\

Hi Dax,

I think, ‘different starting points’ is a good idea. But I want to

make this automatically. In detail,

My LP problem sometimes do not have a unique optimal solution set.

There are more than one optimal solution set giving the same optimal

objective value. And I must find the solution set (x). Optimal

objective value is not enough for me.In other words, I want to find

all vertices of my feasible solution set. But I can find only one

solution x.

Tavallali sent me the paper ‘Recursive MILP model for finding all the

alternate optima in LP models for metabolic networks’ for my problem.

It seems to me a bit of complicated, but I will try to solve it.

thanks for your answer.

regards,

hale.

On 11 KasÄ±m, 11:53, Dax wrote:

In my humble opinion, a LP either has a unique solution, or has a

continuum of solution in case of degeneracy.

In the latter case, there are an infinity of solutions. Hence finding

“all alternate optimal solutions” might be tedious.

However, providing different starting points may end up in different

solutions, in some cases.

There must be better approaches to this.On 10 nov, 14:46, halegk wrote:

I am trying to find all optimal solutions of my LP problem. Is it

possible to find all alternate optimal solutions?

\

Hale,

The problem of enumerating all solutions or vertices of a polyhedron

(LP feasible region) is quite well studied. See

D. Avis and K. Fukuda. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Comput. Geom., 8:295-313, 1992.

of course for large polyhedra this may be practically impossible, but there is other software like POLYMAKE that implements the enumeration.

J. De Loera

On Thu, 11 Nov 2010, [ISO-8859-1] Hale Gonce KÃ¶Ã§ken wrote:

Hi Dax,

I think, ‘different starting points’ is a good idea. But I want to

make this automatically. In detail,My LP problem sometimes do not have a unique optimal solution set.

There are more than one optimal solution set giving the same optimal

objective value. And I must find the solution set (x). Optimal

objective value is not enough for me.In other words, I want to find

all vertices of my feasible solution set. But I can find only one

solution x.Tavallali sent me the paper ‘Recursive MILP model for finding all the

alternate optima in LP models for metabolic networks’ for my problem.

It seems to me a bit of complicated, but I will try to solve it.thanks for your answer.

regards,

hale.On 11 KasÃ„Ä…m, 11:53, Dax wrote:

In my humble opinion, a LP either has a unique solution, or has a

continuum of solution in case of degeneracy.

In the latter case, there are an infinity of solutions. Hence finding

“all alternate optimal solutions” might be tedious.

However, providing different starting points may end up in different

solutions, in some cases.

There must be better approaches to this.On 10 nov, 14:46, halegk wrote:

I am trying to find all optimal solutions of my LP problem. Is it

possible to find all alternate optimal solutions?–

To post to this group, send email to gamsworld@googlegroups.com.

To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.

For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.

–

To post to this group, send email to gamsworld@googlegroups.com.

To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.

For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.

\