[Scip] Making a deep copy of SCIP

michael.winkler@zib.de michael.winkler at zib.de
Wed Nov 14 02:48:09 MET 2012


Hi Pierre,

I have some more questions and comments.

>> Are you creating a global or a local copy?
> I initially made local copies, but switching to global copies did not
> change the objective values.

In my understanding, it seems to make sense to copy the local SCIP problem
data in your case. You can retransform any solution value from the copied
SCIP to the original value, if necessary.

> My intent is to do the following:
> -Stop at a given node A
> -for each LP candidate x at A
> --make a deep copy of SCIP
> --call SCIPsolve on the copy
> --at the first branched node, i.e. A, branch on x (using a custom
> branching rule)
> --after that, completely solve the copy problem using default plugins,
> thus solving nodes that are in general outside the subtree rooted at A.
> --free the copy
> -endfor

If you would have done a local copy, how do you think it is possible that
some nodes are outside the subtree rooted by A? All branching decisions
which led to A and also all other local boundchanges derived by
propagation on the way to A and some more information are copied and when
you then branch in this copied problem on one branching candidate of A,
all newly created nodes will be in the subtree of A.

>> This is not allowed and not possible--you must have included
>> non-public
>> header files, right?
> Indeed. But they looked as public as the other ones.

All methods in scip.h and pub_*.h are the public methods that are allowed
to be used.

Best, Michael

> Dear Ambros,
>
>> I have not implemented the copy functionality myself, but I will try
>> to
>> address your questions.  :)
> Thank you.
>
>> On 13.11.2012 20:33, Pierre Le Bodic wrote:
>> > Hi,
>> >
>> > I would like to be able to interrupt the B&B tree search at a
>> > branching node, say A, and try different branching variables. At A,
>> > for each variable that I try, I would like to be able to solve the
>> > problem to optimality. With a basic implementation, this would mean
>> > I
>> > have to solve the entire problem for each variable I try to branch
>> > on. However, the tree search before reaching node A would always be
>> > identical. It would therefore make sense to make a deep copy of
>> > SCIP
>> > at node A, solve the rest of the problem on the SCIP copy for a
>> > variable, and do this for each variable. I have coded the latter
>> > implementation.
>> >
>> > I have used a method called SCIPcopy
>> > (http://scip.zib.de/doc/html/scip_8h.shtml#ae0f9695c2985d240e1f09ec6a6fb640a),
>> > which supposedly "copies a source SCIP to a target SCIP".
>> > However, it
>> > does not seem possible to warm start the copy.  As a matter of
>> > fact,
>> > and this is consistent with the documentation, the stage of the
>> > SCIP
>> > copy in not copied from the original SCIP.
>>
>> Yes, the copied SCIP is always in problem creation stage.
>>
>> > Therefore, when calling
>> > SCIPsolve on the copy, the whole solving process is started all
>> > over
>> > again (but it's faster, probably because the preprocessing doesn't
>> > have to be done from scratch).
>>
>> No, the preprocessing is always performed, unless you change the
>> parameters of the sub-SCIP.  It may be faster, if
>>
>> a) it is a local copy, because then the local bounds are used and
>> many
>> variables may be fixed;
>>
>> b) it is a global copy, but some primal solution was copied, hence
>> preprocessing is stronger.
>>
>> > More importantly, the reported optimal
>> > solution values are not equal to the optimal value you get from
>> > solving the problem with the vanilla scip program. My hypothesis is
>> > that scip reports the optimal solution in the subtree rooted at A.
>>
>> Are you creating a global or a local copy?
> I initially made local copies, but switching to global copies did not
> change the objective values.
>
>>
>> > If I just try to manually set the current stage of the SCIP copy
>> > that
>> > I get from SCIPCopy,
>>
>> This is not allowed and not possible--you must have included
>> non-public
>> header files, right?
> Indeed. But they looked as public as the other ones.
>
>>
>> > then an assertion fails and indicates that the
>> > pointer to the event handler should not be NULL. If I try to
>> > correct
>> > this, then the following assertion fails as well, indicating that
>> > the
>> > pointer to the tree should not be NULL. It seems copies of these
>> > fields in the original SCIP were not copied during SCIPcopy.
>>
>> Yes, SCIPcopy() does only copy the problem (defined by the local or
>> global constraints, variables, and bounds); if I understand
>> correctly,
>> you expected SCIPcopy() to yield a copy of the whole solving process,
>> i.e., the tree as well.
> This was my initial interpretation of the SCIPcopy documentation.
>
>>
>> > So,
>> > apparently, SCIPcopy is neither a shallow copy (because the pointer
>> > to the tree should then point to the old tree) nor a deep copy
>> > (because then there should be a new tree on which to point).
>>
>> SCIPcopy() yields a *deep* copy of the problem and *no* copy of the
>> solving data.
> Ok.
>
>>
>> > I would
>> > like to know what kind of copy is actually done during SCIPcopy,
>> > and
>> > what can be done with such a copy.
>>
>> The primary use of SCIPcopy() within SCIP's default plugins is for
>> large
>> neighbourhood search heuristics such as RENS, RINS, DINS, Undercover,
>> etc.  They all create a copy of the problem, fix some variables, and
>> solve.  They are not interested in having the old solving
>> information.
> Understood.
>
>>
>> > Also, are there any way to make a
>> > warm-startable deep copy of SCIP without modifying the source?
>>
>> By warmstarting I intuitively understand
>> 1. Solve a MIP.
>> 2. Change the MIP slightly.
>> 3. Solve the modified problem.
>>
>> Do I understand correctly that you mean by warmstarting from node A
>> something slightly different or rather more specific:
>> 1. Make a branching decision to create a child A1.
>> 2. Solve the subtree under A1 (completely).
>> 3. Remove the subtree and the branching decision.
>> 4. Make a different branching decision to create a child A2.
>> 5. Solve the subtree under A2 ...
> My intent is to do the following:
> -Stop at a given node A
> -for each LP candidate x at A
> --make a deep copy of SCIP
> --call SCIPsolve on the copy
> --at the first branched node, i.e. A, branch on x (using a custom
> branching rule)
> --after that, completely solve the copy problem using default plugins,
> thus solving nodes that are in general outside the subtree rooted at A.
> --free the copy
> -endfor
>
>
>>
>> This may be difficult to realize via SCIPcopy(), since the LP basis
>> cannot be set in problem creation stage and other relevant
>> information
>> like branching statistics are not copied.
>>
>> An alternative (but not really) could be SCIP's probing mode.  Maybe
>> first you could let us know whether I understood you correctly.
>>
>> Best regards,
>> Ambros
>
> If there are no ways to deep copy the resolution data behind SCIP using
> built-in methods (and warm start the copy), then I should probably use the
> simple and costly method I described in my first email.
>
> Please let me know if you see a way to proceed with my initial idea.
> Thanks again for your help.
>
> Pierre
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>



More information about the Scip mailing list