[Top][All Lists]

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

Re: [Help-glpk] Binary integer programming

From: Michael Hennebry
Subject: Re: [Help-glpk] Binary integer programming
Date: Wed, 22 Jul 2009 11:53:43 -0500 (CDT)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

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

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   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."

reply via email to

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