help-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] problems with multiple solutions in glpk


From: Jordan Atlas
Subject: Re: [Help-glpk] problems with multiple solutions in glpk
Date: Mon, 07 Jan 2008 10:01:07 -0500
User-agent: Mozilla Thunderbird 1.0.2 (Windows/20050317)

Hello all,

Sorry for the multi-post, but I found a reference that answers the question I posted below (and also discusses the method Sebastian mentioned). Please see:

Jung-Fa Tsai, Ming-Hua Lin, Yi-Chung Hu, European Journal of Operational Research 184 (2008) 802–809, "Finding multiple solutions to general integer linear programs".

Thanks again,

--Jordan


Jordan Atlas wrote:

Hi Sebastian,

Thank you for your suggestion. I like it a lot. I'm working with a MIP that has all the variables constrained to being integers >= 0. Can you suggest a cut that might work for this sort of problem? One analogous to the one you suggested doesn't seem to work because it can eliminate valid solutions --> I'm having trouble thinking of a way to eliminate only the single solution point.

Thanks,

--Jordan

Sebastian Pokutta wrote:

IF you have a 0-1 program you can try to cut off the solution (point) as follows to check the presence of other solutions with same cost.

Say the solution is x and let I be the support of x, i.e. x_i = 1 iff i \in I and let J be the zero-support, i.e. x_i = 0 iff i \in J. Note that I \cup J \subseteq [n] where n is the dimension but equality does not necessarily hold as we have a mixed-0-1-program. Now you can add the cut \sum_{i in I} (1-x_i) + \sum_{i ⁄in J} x_i >= 1/2 to cut-off exactly that solution. All other valid solutions y will "survive" because there is at least one coordinate y_i \neq x_i. Hence, if i \in I then x_i = 1 and so y_i = 0 and the sum above is >= 1/2. Similar holds if i \in J.

Now you can re-optimize with this cut added and if you obtain a valid solution with the same solution value then there are more than one solution. You could (theoretically - it is rather impraticable though) even enumerate the solution with same cost using this "trick".

For general mixed-integer program the same procedure works as well, though you have to find a cut that cuts-off your solution which might be a bit harder in this case.








_______________________________________________
Help-glpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk







reply via email to

[Prev in Thread] Current Thread [Next in Thread]