[Scip] Making a deep copy of SCIP

Stefan Heinz heinz at zib.de
Thu Nov 22 09:23:59 MET 2012


Hi all

On 11/14/2012 09:03 PM, Pierre Le Bodic wrote:
> Dear Stefan,
>
>> I'm glad that it is working as expected. A word of warning though:
>> Make sure not to build a fork bomb. A not carefully placed fork()
>> might be called recursively and thus spawning processes exponentially
>> as well as polluting RAM. In the worst possible case, this can damage
>> your hardware.
> Thank you for the warning. I included the piece of code from the branching rule containing the fork call. This could even be of interest to other readers.
>
> Note that the public method SCIPvarGetName should be used instead of ->name if you want to be in good standing with the dev team ;) (but really it's also better practice, and I should change that at some point).
A quick comment to SCIPvarGetName(var) and "var->name". Frequently, we 
see such codes (which are not bad at all)  and people usually are not 
aware of, that they are using SCIP in slightly "wrong" way. The 
advantage of using SCIPvarGetName() and all similar methods is, that in 
*debug* mode certain consistency checks are performed, to detect 
problems before a segmentation fault arises. In *opt* all these methods 
are basically inlined such that there is no preference issue at all. 
Seeing these code also tells me that most of the user are not aware of 
the *debug* mode. Compiling SCIP in debug mode ("make OPT=dbg" if you 
are using the SCIP Makefile system) has again the advantage that a lot 
of additional checks are performed, to see if stuff is consistent. I 
strongly recommend to compile SCIP in debug mode and run once in awhile 
a short test. If you compile SCIP in debug mode the compiler should 
complain about "var->name" since this variable struct is not visible in 
debug mode (on purpose). The solution is *not* to include the 
"struct_var.h". You just should use the corresponding method.

Best Stefan




replaced by   since everything compiles.
>
> Best wishes,
> Pierre
>
> ----- Original Message -----
>> From: "Stefan Lörwald" <stefan.loerwald at gmail.com>
>> To: "Pierre Le Bodic" <lebodic at gatech.edu>
>> Cc: scip at zib.de
>> Sent: Wednesday, November 14, 2012 2:15:19 PM
>> Subject: Re: [Scip] Making a deep copy of SCIP
>>
>> Dear Pierre,
>>
>> I'm glad that it is working as expected. A word of warning though:
>> Make sure not to build a fork bomb. A not carefully placed fork()
>> might be called recursively and thus spawning processes exponentially
>> as well as polluting RAM. In the worst possible case, this can damage
>> your hardware.
>>
>> Best wishes,
>> Stefan
>>
>> P.S.: A simple example of a fork bomb for illustration:
>>
>> void badFunction()
>> {
>>     fork();
>>     badFunction();
>> }
>>
>> int main()
>> {
>>     badFunction();
>> }
>>
>> Without the fork, this is an infinite loop which blocks just one
>> Processor. The version with fork will cause at least a system freeze
>> unless you limit the number of processes.
>>
>> 2012/11/14 Pierre Le Bodic <lebodic at gatech.edu>:
>>> 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
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip



More information about the Scip mailing list