help-glpk
[Top][All Lists]

[Help-glpk] Re: finding multiple integer solutions

 From: Andrew Makhorin Subject: [Help-glpk] Re: finding multiple integer solutions Date: Thu, 20 Nov 2003 05:08:54 +0300

>I would like to modify the MIP solver to allow for finding multiple optimal
>solutions, and I would appreciate any comments on a particular approach I am
>contemplating.

There is a two-phase procedure. On the first phase any solution which
is proven to be integer optimal is obtained. Let optimal value of the
objective be Zopt.

To implement the second phase the branch-and-bound should be modified
as follows. Let Zbnd be the objective bound for some subproblem (for
example, optimal solution of its LP relaxation). In the standard
branch-and-bound if Zbnd is not better than the incumbent objective
value (in our case it is obviously Zopt), the corresponding branch is
pruned. However, if Zbnd is not worse than Zopt, the branch can lead
to other integer optimal solutions. Therefore we should solve such
branches to the end, i.e. not prune them until their integer feasible
solutions have been obtained. All these integer feasible solutions sunt
integer optimal solutions of the problem.

To modify the pruning test implemented in lpx_integer you need to
replace two following lines (the first one is for minimization and the
second one is for maximization) in the routine is_better (glpmip1.c);

if (obj > tree->best[0] - eps) better = 0;

if (obj < tree->best[0] + eps) better = 0;

by

if (obj > Zopt + eps) better = 0;

if (obj < Zopt - eps) better = 0;

respectively. (It's better, of course, to switch between tests using a
flag.) Then *all* integer optimal solutions can be catched on handling
the event MIP_V_BINGO.

Note, however, that a mip may have exponentially many integer optimal
solutions, so this procedure is impractical. If due to some reasons a
solution found by mip solver is not appropriate, one should introduce
additional constraints into the problem rather than enumerate all
solutions in the hope to find something more appropriate. This is the
key idea of math programming.

Please note also that the glpk mip solver lpx_integer and corresponding
components (glpies1, glpies2, glpies3, and glpmip1) will be replaced by
a new implementation (based on IOS) and therefore will be removed from
the package.

Andrew Makhorin