RE: [Help-glpk] Binary integer programming

[Giampaolo Tomassoni]

> 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?

I had the very same problem and the solution I found was:

        1) run the GLPK solver;
        2) if there isn't any feasible solution, stop;
        3) otherwise, save/print the solution found;
        4) add further constraint(s) to the problem in such a way to mask
that solution;
        5) go to point 1).

This may be quite expensive and is probably suitable only for small to
middle scale problems, but it works to me.

However, point 4) is kind of an art: in my own case, I was solving simple
MIPs in which the problem's structural variables where basically binary
options, grouped in a well-known number of non-overlapping sets and in each
set there could be one and only one "selected" option. This way point 4) is
really easy to implement: I only needed to put a upper-bound (the number of
disjoined sets - 1) to the sum of the selected options and GLPK wouldn't
choose that exact solution again...

What is the probability your problems are from the same class of mines?
1/1000000? ;)

Hope this can help, anyway.

Giampaolo


> 
> Thank you,
> 
> George Athanasiou