[Top][All Lists]

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

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

From: Andrew Makhorin
Subject: Re: [Help-glpk] Multiple solutions for a binary MIP problem?
Date: Mon, 1 Feb 2010 03:44:57 +0300

> I wonder if glpk can provide me with several optimal solutions for a
> 0-1 IP instance (seems not, but I thought I'd ask). I assume I could
> use glpk as an oracle that only returns one solution and simply search
> around (as suggested in, e.g., [1]), but a more direct way would be
> super useful.

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.

reply via email to

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