help-glpk
[Top][All Lists]

## Re: [Help-glpk] Binary integer programming

 From: Sebastian Pokutta Subject: Re: [Help-glpk] Binary integer programming Date: Wed, 22 Jul 2009 05:36:15 +0300

```Hello George,

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.

All the best,
Sebastian

On 21.07.2009, at 12:16, George Athanasiou wrote:

> Hello,
>
> 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?
>
> Thank you,
>
> George Athanasiou
>
> <image001.png>
>
>  George Athanasiou
>  Ph.D. Candidate
>  University of Thessaly
>  Department of Computer and Communications Engineering
>  Centre for Research and Technology Hellas
>
>  Glavani 37 & 28 Oktovriou
>  38221, Volos, Greece
>  Tel:  +30 24210 74553
>  Fax: +30 24210 74668
>  web page: http://www.inf.uth.gr/~gathanas
> <image001.png>
>
>
> _______________________________________________
> Help-glpk mailing list