[Scip] Making a deep copy of SCIP

[Ambros Gleixner]

Dear Pierre,

I have not implemented the copy functionality myself, but I will try to 
address your questions.  :)

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?

> 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?

> 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.

> 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.

> 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.

> 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 ...

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


>
> Sorry for the long read. Thanks in advance.
>
> Pierre _______________________________________________ Scip mailing
> list Scip at zib.de http://listserv.zib.de/mailman/listinfo/scip
>

-- 
____________________________________________________________
Ambros M. Gleixner
Zuse Institute Berlin - Matheon - Berlin Mathematical School
http://www.zib.de/gleixner