[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: [Help-glpk] Binary integer programming

From: Giampaolo Tomassoni
Subject: RE: [Help-glpk] Binary integer programming
Date: Wed, 22 Jul 2009 08:21:40 +0200

> 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
> (with brunch techniques). I know that my problem has more than one
> (with equal cost). Is there any way to get complete set of solutions with

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.


> Thank you,
> George Athanasiou

reply via email to

[Prev in Thread] Current Thread [Next in Thread]