Re: [Help-glpk] Multiple solutions for a binary MIP problem?

[Pavel Klinov]

On Mon, Feb 1, 2010 at 12:44 AM, Andrew Makhorin <address@hidden> wrote:
>
> Glpk does not have a feature to generate diverse solutions. However,
> if your instance is not hard, the following technique can be used.
> Let, for example, there be five binary variables, and you have obtained
> optimal solution x = (0, 1, 1, 0, 1). Then you can add to the instance
> the following covering inequality:
>
>   x1 + (1 - x2) + (1 - x3) + x4 + (1 - x5) >= 1
>
> which cuts off the optimal point from the polytope. Solving the instance
> with the constraint added you can obtain another solution, etc.
>

Andrew, Michael, thanks a lot for the replies.

Andrew, this is roughly what I meant by "searching around". The only
difference is that I also modify the objective function to maximize
diversity and add another constraint to make sure that all subsequent
solutions are within some neighborhood of the optimal one.

The method works OK, the only problem is performance. Basically
finding K solutions amounts to solving K MIP problems. I was hoping
that I could sort of hook up inside GLPK and keep track of solutions
(similarly to what Michael suggested). A naive thought was to use a
callback routine and store solutions when handling GLP_IBINGO events.
I guess that diversity might be really poor then (even if I relax my
requirements and ask only for a set of sub-optimal solutions, i.e.
those within a certain distance from the optimal).

Also, can you point me to where I can read about how GLPK performs
re-optimization after adding new inequalities? I'm now playing with
various presolver options. It looks like it makes sense to turn off
the MIP presolver and simply call glp_simplex. However, I'm not sure
if LP relaxation *itself* is reoptimized or solved from scratch.

Again, thanks a lot for the help and excuse my ignorance. I'm very new
to this area and use GLPK as a tool that helps me solve SAT in a
certain logic.

Pavel



-- 
cheers,
--pavel
http://www.cs.man.ac.uk/~klinovp