[Scip] Making a deep copy of SCIP

Ambros Gleixner gleixner at zib.de
Wed Nov 14 14:35:18 MET 2012 

Hi Stefan,

Am 14.11.2012 14:29, schrieb Stefan Lörwald:
> Hi Ambros,
>
> what do you mean by "a public method like fork() does not exist"? I'm
> talking about the built-in (linux) function fork, see
> http://linux.die.net/man/2/fork. This creates an exact copy of the
> process no matter what SCIP does in the background.

I meant "does not exist in SCIP", because I thought about the tree 
search.  Your high level approach might just be the solution that Pierre 
is looking for.

Thank you,
Ambros


> Best wishes,
> Stefan
>
> 2012/11/14 Ambros Gleixner <gleixner at zib.de>:
>> Hi Stefan,
>>
>> maybe you underestimate the complexity of SCIP's tree search. Furthermore, a
>> public method like fork() does not exist.
>>
>> SCIP's probing mode allows for something similar, but note that, although it
>> allows to discard temporary branching and return to the original state of
>> the tree, meanwhile global information is learnt and hence the state of SCIP
>> itself and the future behaviour of the solving process is affected.
>>
>> Best regards,
>> Ambros
>>
>>
>> Am 14.11.2012 11:42, schrieb Stefan Lörwald:
>>
>>> Hi Pierre,
>>>
>>> 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?
>>>
>>> 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
>>
>>
>> --
>> ____________________________________________________________
>> Ambros M. Gleixner
>> Zuse Institute Berlin - Matheon - Berlin Mathematical School
>> http://www.zib.de/gleixner

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

More information about the Scip mailing list