[Scip] How to deal with "branching decisions"

[E. van der Veen]

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.

===
  
-------------- next part --------------
A non-text attachment was scrubbed...
Name: output.zip
Type: application/x-zip-compressed
Size: 39345 bytes
Desc: not available
Url : http://listserv.zib.de/mailman/private/scip/attachments/20081120/4061cd04/output.bin