Re: [Help-glpk] Binary integer programming

[Sebastian Pokutta]

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
>  e-mail: address@hidden
>  web page: http://www.inf.uth.gr/~gathanas
> <image001.png>
>
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk