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

[Andrew Makhorin]

> I have implemented my application into GLPK v 4.33 in order to make use
> of the glp_copy_prob function. I want a copy of the tree, so that I can
> perform a 'strong branching' effect, where I expand the parent node
> using one variable branching technique, record the sum of the integer
> infeasibilities, then discard the copy of the tree, and repeat using a
> different branching technique. After I have exhausted my branching
> techniques I will select the lowest integer infeasibility branching
> technique to actually branch on the tree.

> However, I have run into a problem simply copying the tree using the
> function glp_copy_prob. GLPK executes the function without problem, but
> then when I try to branch on the copied tree, it gives me a
> segmentation (access) violation. I have a feeling that I am not using
> the glp_copy_prob routine properly by defining something wrong, and I
> am hoping you can help me. Here is some of the code I am trying within
> a branching technique called hybrid1:

> static void branch_hybrid1jp(glp_tree *tree)
> {
>      glp_prob *lp = tree->mip;

>     /* Decide what is my current candidate variable and branching
> direction */
>     //my code here...
>     jj = my candidate variable;
>     next = corresponding branching direction;

>     /* Make a copy of the current tree, so I can test out a different
> candidate variable without wrecking the tree */
>     glp_prob *lp2;   //create a new empty lp
>       lp2 = glp_create_prob();
>       glp_copy_prob(lp2, lp, 0);   //copy the current tree into the new
> lp
>       glp_ios_branch_upon(lp2->tree, jj, next);

> }

> When my code tries to execute the glp_ios_branch_upon subroutine, it
> returns the segmentation error. It appears as if lp2->tree == NULL.

> Any help you could provide me with would be greatly appreciated.

The segmentation fault happens because lp2->tree is NULL, as you
noticed. The point is that the search tree is a separate object built
by glp_intopt, and glp_copy_prob "knows" nothing about it. Lp->tree is
a pointer to the tree, which is set by glp_intopt and recognized by some
api routines (like glp_add_rows to set a reoptimization flag). Note that
using glpk internal data structures out of api is not a good idea, even
you have complete understanding about the program logic.

As to copying the tree, I think this is not needed. You may copy the
problem object (in the callback routine) corresponding to the current
subproblem and then call glp_intopt (in the callback routine!) to start
another search using a copy of the current subproblem as the root of
a new tree. The effect will be the same as if you would temporarily
"expand" the current node. Once the auxiliary search is finished, you
may obtain necessary information to choose a branching variable and
then continue the original search. (I think you are trying to implement
something like "local branching", because "strong branching" does not
need a tree search. Or I am mistaken?)


Andrew Makhorin