[Clp] My suggestion: Re How to get many solutions?

[Alexey Lvov]

//// Danh, I just realized I only sent you a reply , but did not post it to
the mailing list. So I am doing it now (I received your reply on my
personal mail). /////

>> Hi all, I has an lp problem which has more than one solution, and I want
to get all of them. Is there any way in Clp to do that? For example, this
problem:  min x + y subject to x + y >= 3 x >= 0 y >= 0 has two solutions
(0,3) and (3,0) using the simplex method If I want to get to solutions,
which function in Clp should I use?T hanks


  Hi!

I am just a user of CLP, so I only can give an approximate advise.
In general the set of solutions to an LP problem is a convex polyhedron.
This polyhedron can be as complex as the original feasible region. Thus in
general describing the set of all solutions is hard.

But you can get several random solutions by randomly modifying the
objective function by a small epsilon.

I.e. generate a random co-vector with coords in [0,1] ,   in your case (x0,
y0). Add         epsilon * (x0, y0)    to the objective function:  MIN  (1
+ 0.000001*x0) * x + (1 + 0.000001*y0) * y. Solve. You have a random
optimal solution to the original problem{ x , y } .  If your epsilon is
small enough the solution is _EXACT_, not approximate (you only need to
recompute the value of the original objective function) .
Repeat as many times as you want to get more random solutions.

 - Alexey


----------------------------------------------------
          Dr. Alexey Lvov
IBM T.J. Watson Research Institute
1101 Kitchawan Rd. (Rt. 134) Office 34-159
Yorktown Heights  NY  10598
Tel: (914)-945-3732
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20090512/dcf8b2ec/attachment.html>