[Scip] Making a deep copy of SCIP

[Pierre Le Bodic]

Hi everyone,

> did you consider using fork()? It should be fairly easy to let a
> child
> process do some calculations with a modified problem, while the
> parent
> process just waits for the result (and may fork again if the result
> is
> not satisfying). I don't see the point of messing around with SCIP
> internal structures if you only want the exact same state.
> 
> Am I missing a vital piece of information which makes this approach
> impossible?
I have modified my code to use fork instead of SCIPcopy. This seems to be doing exactly what I want, with "free" parallel execution as a cherry on top. Thank you for your input, Stefan, you saved me and my computer a lot of coding and execution time, respectively. Thanks also to Ambros and Michael.

Best wishes,
Pierre


> 
> Yours,
> Stefan
> 
> 2012/11/14 Ambros Gleixner <gleixner at zib.de>:
> > Dear Pierre,
> >
> > On 14.11.2012 02:48, michael.winkler at zib.de wrote:
> >> 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.
> >
> > I'll start guessing a bit what your motivation for this experiment
> > might
> > be.  In a naive solver, you would expect that the branching
> > decisions at
> > A only influence the subtree at A, but not nodes outside.
> >
> > In a sophisticated solver that collects global information (pseudo
> > costs, conflicts, primal solutions) this does not hold anymore.
> >
> > So your motivation might be that the global information gathered
> > during
> > solving the subtree at A differs when choosing a different
> > branching
> > candidate and influences the global search.
> >
> > To test this, as Micha pointed out, you cannot use a local copy of
> > SCIP
> > and neither would a global copy help you.
> >
> > The only solution I can imagine that is relatively easy to
> > implement is
> > time consuming.  (But if your interest is theoretical, that might
> > be ok.)
> > 0. i = 1
> > 1. Solve SCIP until reaching A (detected by your branching rule).
> > 2. If number of candidates < i, stop.
> > 3. Perform the branching for the i-th candidate.
> > 4. Complete the solve (without further interference of your
> > branching rule).
> > 5. SCIPfreeTransform(); i++; goto 1.
> >
> > This assumes that you can safely identify A repeatedly.
> >
> > If you would want to speed up (warmstart) the execution of point 5.
> > followed by 1., you would need to extend src/scip/tree.c and other
> > things.  This would include making a snapshot of the global solving
> > data
> > at point 3, certainly a lot of work to implement.
> >
> > Best regards,
> > Ambros
> >
> >
> >>>> 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
> >>>
> >>
> >
> > --
> > ____________________________________________________________
> > Ambros M. Gleixner
> > Zuse Institute Berlin - Matheon - Berlin Mathematical School
> > http://www.zib.de/gleixner
> > _______________________________________________
> > Scip mailing list
> > Scip at zib.de
> > http://listserv.zib.de/mailman/listinfo/scip
>