[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## 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*
>* 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*