[Scip] How to deal with "branching decisions"

[E. van der Veen]

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