[Scip] Making a deep copy of SCIP

[Pierre Le Bodic]

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