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

[Andrew Makhorin]

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