Re: [Help-glpk] Binary integer programming

[Michael Hennebry]

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   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."