On Wed, 22 Jul 2009, Sebastian Pokutta wrote:
there is a trick in the case of binary program that does the job:
If x* in {0,1}^n is the obtained solution after the first run, add the
inequality:
sum{i in I} x_i + sum{i in [n] \ I} (1-x_i) >= 1
where I = { i in [n] | x*_i = 0}.
This additional inequality cuts off *exactly* the solution x*. Then
when solving it the second time you get the next solution. This
process can be repeated iteratively until you cut off all the optimal
solution and you found a sub-optimal one.
On 21.07.2009, at 12:16, George Athanasiou wrote:
I’m trying to solve a binary integer programming problem. I’m using
matlab (bintprog function) and the problem is that I get a single
optimal solution (with brunch techniques). I know that my problem
has more than one solutions (with equal cost). Is there any way to
get complete set of solutions with GLPK?
Sebastian's technique is rather expensive.
I infer that you have integer data.
Otherwise, knowing that you have multiple
optimal solutions would be difficult.
Once you have an optimal solution, you know the optimal cost.
That gives you an additional equlaity constraint.
For guidance purposes, the objective can be replaced with something arbitrary.
Does GLPK have a hook to let you apply a user-defiend feasiblilty test?
If so, the test should always fail after
adding the testee to the list of solutions.
As the size of the list could be exponential,
any technique could take a while.
--
Michael [email protected]
"Pessimist: The glass is half empty.
Optimist: The glass is half full.
Engineer: The glass is twice as big as it needs to be."
_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
