[Top][All Lists]

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

Re: [Help-glpk] MIP Qestion

From: Andrew Makhorin
Subject: Re: [Help-glpk] MIP Qestion
Date: Wed, 21 Aug 2002 00:51:24 +0400

>Now my question is where do I add the upper bound check to fathom branches?

If your heuristic is used only once before integer optimization and
gives you an upper bound of the integer optimal solution (which, most
probably, is an objective value of some integer feasible, non-optimal
solution, isn't it?), you can just use this upper bound to initialize
the best known solution. In order to do that you need to replace the
following two lines in the file 'glpbbm.c' (they are placed within the
routine 'initialize' and have numbers 190 and 191 in glpk-3.1 and more
recent versions):

      bb->found = 0;
      bb->best = 0.0;


      if (!cp->extub_flag)
      {  bb->found = 0;
         bb->best = 0.0;
      {  bb->found = 1;
         bb->best = cp->extub + 1e-6 * (1.0 + fabs(cp->extub));

The effect of this change is the same as the solver would have found an
integer feasible solution with the objective value extub, so it will
prune all nodes, where the objective value is worse (greater) than extub,
until it has found something better. (Don't forget to restore the
original code of 'bbm1_driver' and 'dual_monit'.)

If this won't help, don't hesitate to contact me.

(Please note that I plan to include a new implementation of the MIP
solver, which is based on the branch-and-cut framework, in the next
version of the package. This new solver allows using the event-driven
application procedure to perform application specific actions, in
particular, to pass bounds obtained from primal heuristics to the

reply via email to

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