Re: [Help-glpk] Re: How to create the copy of a node ?

[Andrew Makhorin]

> I don't quite understand how to implement your suggestion below.

> I'm not sure what exactly you mean by 'problem object' or 'callback
> routine'. It is probably clear to you by now that I am not a very
> experienced C-programmer.

> Here is a written example of exactly what I want GLPK to do:

> I have solved the initial LP relaxation, and am deciding my branching
> variable and direction (within my custom made 'static void
> branch_hybrid' subroutine, similar in structure to 'branch_mostf' and
> others). I run two branching variable selection algorithms, one at a
> time in this subroutine. While still in this subroutine I want to
> compare the two branching variable choices before actually deciding
> which one of my two algorithms to continue solving the MIP with. What I
> want to do is compare the II_sum of the two algorithms given that I
> make their branching variable choices and solve the resulting LP
> relaxation. Then, while still in my subroutine, I will compare the two
> II_sums and select the best to proceed with for this branching
> decision. Then I will allow GLPK to leave my branching subroutine to
> branch_on the winning method's variable and direction.

> This process is repeated every time there is a branching decision being
> made in the MIP.

> On a high level, I am trying to collect these characteristics of the
> node so that I can determine in what cases one algorithm is better than
> another.

> So basically, I am looking for a chunk of code that I can execute
> within my branching variable selection subroutine that will temporarily
> expand a node, solve the LP relaxation and output the resulting II,
> then get rid of the fact that that node was ever expanded (to keep the
> original tree's integrity), and repeat for the second algorithm choice.

> I originally was just trying to clone the current node, create its
> child, solve the lp relaxation, and then delete the node, but that
> didn't seem to be working for me either. So my professor suggested I
> try copying the entire LP, solve the next node LP relaxation and then
> delete the copy of the LP. Either way, as long I can get my  II_sum for
> the two choices, and then revert to the original parent node and carry
> on without GLPK crashing, I will be very happy.

> Given this more detailed information can you provide me with any code
> that I could try to achieve my goal?

As I understand, you change the glpk code to implement your own
branching strategy. This, however, is not a good idea. The glpk mip
solver (glp_intopt) allows the application using the callback routine,
which is passed to the solver and then called at various points of
the branch-and-cut algorithm. For detailed description please see the
glpk reference manual, chapter "Branch-and-Cut API Routines".

Your code might look like follows.

#include <glpk.h>

int main(...)
{  glp_prob *mip;
   glp_iocp parm;
   ...
   glp_init_iocp(&parm);
   parm.cb_func = foo;
   parm.cb_info = ...;
   glp_intopt(mip, &parm);
   ...
}

void foo_bar(glp_tree *tree, void *info)
{  /* callback routine called from glp_intopt */
   ...
   if (glp_ios_reason(tree) == GLP_IBRANCH)
   {  /* request for branching */
      ...
      /* choose variable to branch upon */
      glp_ios_branch_upon(tree, ...);
   }
   ...
}

If, to choose a branching variable, you need to perform a local tree
search, you can copy the problem object corresponding to current node
subproblem (glp_ios_get_prob, glp_copy_prob) and then call glp_intopt
(within foo_bar) to start a new search independently of the search
currently being performed, where the copy of the current subproblem
will be the root problem. If you need to control that new search, you
again may pass to glp_intopt yet another callback routine similar to
foo_bar.