[Scip] How to deal with "branching decisions"

[Tobias Achterberg]

This is easy: use the constraints as you do, but instead of fixing the variables to zero 
in the scip_active() method, do so in the scip_prop() method, i.e., the domain propagation 
callback. This is exactly where this stuff belongs to. Just make sure that your constraint 
handler has a propagation frequency of 1, such that the propagator is always called.


Tobias

E. van der Veen wrote:
> Hi Tobias,
> 
> Thanks for the quick repsonse.
> 
> The approach you outlined (the one with "just call SCIPchgVarUbNode()") 
> is something I tried at first. However, this does not work for my 
> Branch-and-Price implementation, because after a branching took place, 
> it might happen that additional variables are generated in one node, 
> which are not valid in another node which is created, but not yet 
> entered and processed.
> 
> For example (in my rostering problem with time horizon one day) I branch 
> on a period in which an employee starts working (and if this is already 
> fixed on a period in which he stops working).
> SCIP starts solving and if the pricer, which generates shifts does not 
> find a profitable shift the branchrule creates several childs, for one 
> of the employees (call it emp) that is working a fractional shift. To be 
> precise, for every period a child is created, where a period is marked 
> as start period.
> 
> Suppose the node where period 1 is a starting period is entered first. 
> Vars corresponding to shifts not starting in period 1 are fixed to 0 
> (via the scip_active method). Now, the pricer is called, which generates 
> shifts starting in period 1 (at least for emp). Now, if this node is 
> left, and the node where period 2 is the starting period for emp is 
> entered, the additional variables that are created in the first node, 
> have to be set to 0, because they are not valid there.
> 
> This is why the approach you outline in your e-mail below does not work 
> for me (at least I think it doesn't). That's why I tried the approach 
> you suggested earlier when I didn't know how to deal with enforcing 
> "branching decisions".
> 
> I hope you understand what my problem is, and also have some idea on how 
> I can tackle this, without using SCIPchgVarUb() or SCIPchgVarUbNode().
> 
> Thanks in advance!
> 
> Best regards,
> Egbert
> 
> 
> 
> On Thu, 20 Nov 2008 15:53:28 +0100
>  Tobias Achterberg <achterberg at zib.de> wrote:
>> You cannot call SCIPchgVarUbNode() from the scip_active() method. The 
>> first time the node is entered, this will be okay since then the node 
>> is the current focus node (the node that is currently processed). But 
>> if you later leave this part of the tree and then enter it again, the 
>> node is already a fork node and cannot be modified anymore.
>>
>> In fact, a second change to the bound is also not necessary, since 
>> your first change is already added to the node's bound change list and 
>> thus redone automatically if the node is entered again.
>>
>> If the only purpose of these constraints is to fix the bounds of some 
>> variables to zero, then you actually do not need these constraints. 
>> You can just fix the bounds of the variables in the child node of the 
>> branching (i.e., instead of calling SCIPaddConsNode(), just call 
>> SCIPchgVarUbNode()).
>>
>> My suggestion to add such dummy constraints was because I thought that 
>> you also need to update some internal data structure, for example a 
>> graph. Maybe, if you branch on an edge, then in the left child, you 
>> want to remove this edge locally from the graph, while in the right 
>> child you want to shrink the edge (i.e., replace the two nodes by one 
>> big node). If you need something like this, then such dummy 
>> constraints are handy, since with the scip_active() and 
>> scip_deactive() methods you can implement the "do" and "undo" 
>> operations on your graph. But as I said, local changes to the bounds 
>> of the variables are automatically tracked by SCIP, and you do not 
>> need to add dummy constraints for this purpose.
>>
>>
>> Best,
>>
>> Tobias
>>
>>
>> E. van der Veen wrote:
>>> Hi all,
>>>
>>> To enforce branching decisions in SCIP, I applied an approach 
>>> suggested by Tobias (which is described below).
>>>
>>> I created a class derived from ObjConshldr for this. When a branching 
>>> node is created one or multiple constraints are added to the created 
>>> node. When the node is entered the scip_active (==CONSACTIVE) method 
>>> is called. In this method variables which are not valid in the node 
>>> are fixed to zero, via SCIPchgVarUb().
>>> Now, when I run SCIP it runs for a few seconds, in which branches are 
>>> created, where constraints are added, and also UBs of vars are set to 
>>> 0, and released again, but at some point when a node is entered SCIP 
>>> prompts the following assertion failure:
>>>
>>> Assertion failed: (SCIP_NODETYPE)node->nodetype == 
>>> SCIP_NODETYPE_FOCUSNODE || (S
>>> CIP_NODETYPE)node->nodetype == SCIP_NODETYPE_PROBINGNODE || 
>>> (SCIP_NODETYPE)node-
>>>> nodetype == SCIP_NODETYPE_CHILD || (SCIP_NODETYPE)node->nodetype == 
>>>> SCIP_NODETY
>>> PE_REFOCUSNODE || node->depth == 0, file 
>>> d:\egbertv\thesis\databases_en_software
>>> \scip\zibopt\scip-1.00\src\scip\tree.c, line 1541
>>>
>>> and I do not quite see what the issue is here. Some details (but I'm 
>>> not sure which details you need, but anyways):
>>> -It happens after a certain node is activated for the 2nd time (so 
>>> node is activated once, deactived once, and after it is activated 
>>> again I get the error; I defined SCIP_DEBUG in tree.c)
>>> -I tried SCIPchgVarUbNode() iso SCIPchgVarUb() (for which I included 
>>> the node where the constraint is added in the consdata), but I see 
>>> that this eventually also (just like SCIPchgVarUb()) calls 
>>> SCIPnodeAddBoundinfer() in tree.c where the assertion failure occurs; 
>>> In both cases (with SCIPchgVarUbNode() and SCIPchgVarUb()) the same 
>>> thing happens.
>>> -The scip_deactive (==CONSDEACTIVE) method of my class only contains 
>>> SCIP_OKAY, since I figured if SCIP leaves a node bounds of vars are 
>>> automatically reset, due to the stickingatnode = TRUE flag I set for 
>>> my constraints
>>> (the other parameters of the constraints are set to:
>>> (initial=FALSE separate=FALSE enforce=FALSE check=FALSE 
>>> propagate=TRUE local=TRUE modifiable=FALSE dynamic=TRUE 
>>> removable=FALSE) in my constraint handler class I (only) defined 
>>> scip_delete, scip_trans, scip_enfolp, scip_enfops, scip_check, 
>>> scip_prop, scip_lock, scip_active, scip_deactive.
>>>
>>> Because, I think it might be useful, I added some debugging 
>>> information which I get by including #define SCIP_DEBUG to the tree.c 
>>> file. If you need more debugging information in order to help me, 
>>> please say so and I'll provide it.
>>>
>>> NB. I also tried another approach suggested by Tobias for enforcing 
>>> my branching decisions with set packing constraints, but this is not 
>>> valid anymore due to a remodelling of my problem, where I had to 
>>> remodel binary vars as general non-negative integer vars. Hence, I'm 
>>> now trying this approach.
>>>
>>> Any help is very much appreciated!
>>>
>>> Best regards,
>>> Egbert van der Veen
>>>
>>>
>>> ===
>>>> 2. Sometimes, pricing algorithms need to update their internal data 
>>>> structures (for example, a graph) after the branching and undo these 
>>>> updates if the search leaves the child node again.
>>>>
>>>> To do this in SCIP, I usually recommend to add "marker constraints" 
>>>> to the branching nodes. Create a new constraint handler with 
>>>> constraint data that can store the information necessary to do/undo 
>>>> the changes in the pricer's data structures. All methods of the 
>>>> constraint handler (check, enforcing, separation, propagation, ...) 
>>>> should be empty (which means to always return status = SCIP_FEASIBLE 
>>>> for the fundamental callbacks), just as if all constraints of this 
>>>> type are always feasible. The important callbacks are the CONSACTIVE 
>>>> and CONSDEACTIVE methods.
>>>>
>>>> The CONSACTIVE method is always called when a node is entered on 
>>>> which the constraint has been added (i.e., the child node on which 
>>>> you applied your branching). Here, you will apply the changes to 
>>>> your pricing data structures. The CONSDEACTIVE method will be called 
>>>> if the node is left again. Since the CONSACTIVE and CONSDEACTIVE 
>>>> methods of different constraints are always called in a stack-like 
>>>> fashion, this should be exactly what you need.
>>>>
>>>> If you have such a constraint handler, just create and add 
>>>> constraints of this type to the child node of your branching. Make 
>>>> sure to set the "stickingatnode" flag to TRUE in order to prevent 
>>>> SCIP from moving the constraint around in the tree.
>>>
>>> ===
>>>  
>>>
>>>
>>> ------------------------------------------------------------------------
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> http://listserv.zib.de/mailman/listinfo/scip
>