[Coin-discuss] multiple solutions for LP

[Matthew Saltzman]

On Thu, 2009-09-10 at 09:38 -0400, Kampas, Frank wrote:
> One approach I’ve used with other optimizers is to 
> 
> run the optimization, 
> 
> convert the objective function to an equality constraint equal to the
> objective function value, 
> 
> create a new objective function,
> 
> optimize over and over again with max iterations equal to one.
> 
> Each optimization will give you new solution with the original
> objective function value.
> 
> It won’t give all the degenerate solutions but will give some of them.

This can be done systematically and in a way that reaches all optimal
vertices by forcing each nonbasic variable in turn into the basis using
a depth-first search.  See, e.g., Chvatal's LP book for an algorithm.

Alternatively, we have a code that enumerates all extreme points and
directions of a polyhedron (using a different algorithm).  It's not
publicly available yet, but contact me offline if you are interested.

> 
>  
> 
>  
> 
>  
> 
> From:coin-discuss-bounces at list.coin-or.org
> [mailto:coin-discuss-bounces at list.coin-or.org] On Behalf Of hela masri
> Sent: Wednesday, September 09, 2009 6:39 PM
> To: coin-discuss at list.coin-or.org
> Subject: [Coin-discuss] multiple solutions for LP
> 
> 
>  
> 
>  
> 
>  
> 
> I'm using CoinMp to solve some linear programs.
> is there anyone who knows how can I check if the problem have multiple
> solutions, and in this case how to get the set of solutions.
> I used to use GetAndCheckSolution() 
> 
> Thank you,
> Hela Masri
> 
> 
>  
> 
> 
>  
> 
> 
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
-- 
                Matthew Saltzman

Clemson University Math Sciences
mjs AT clemson DOT edu
http://www.math.clemson.edu/~mjs