[Scip] How to deal with "branching decisions"

[Tobias Achterberg]

Hi Egbert,

you are facing a very common problem in B&P, which you can deal nicely with using SCIP.

You have several options, some of which you already proposed yourself.


1. Add binary variables y_it for capturing "worker i works during period t". You mentioned 
the problem that they are fixed in presolving, and this is certainly valid, because they 
do not appear in any constraints. The correct way of dealing with this issue is to add the 
constraints that describe their meaning, i.e., to add constraints

    -y_it + \sum_{s covers time t} x_s <= 0

I bet that you already have constraints

    \sum_{s covers time t} x_s <= 1

in order to model that you cannot choose two shifts that cover the same time slot. The 
constraint with the y_it is the natural replacement for these constraints.

Of course, this may change your pricing problem, but in order to not generate shifts that 
contain (or that do not contain) the time slots on which you branched, you have to be able 
to deal with this anyway.

In fact, it would be more elegant to invert the role of y_it to get

    y_it + \sum_{s covers time t} x_s <= 1. (*)

Then, you have a set packing constraint, and the domain propagation of the set packing 
cosntraint handler will automatically fix all x_s to zero if y_it = 1. You can interpret 
the y_it variables as additional shifts, that occupy a single time slot but do not satisfy 
any demand.

If you do not want to modify your constraint by including the y_it variable (for example, 
because you cannot interpret the dual variables anymore in your pricing), you can also use
constraints (*) in addition to your original formulation. Mark them as "initial=FALSE" and 
"separate=FALSE" to forbid them to enter the LP. Domain propagation will again make sure 
that the x_s variables are fixed to zero if y_it = 1.



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.



3. You can also use event handlers, but I think that this is not appropriate in your 
application. Anyway, I will briefly explain what this means.

An event handler can watch for events like local bound changes on variables. So, if your 
pricer wants to be informed whenever a local bound of a certain variable changes, add an 
event handler, catch the corresponding events of the variable, and in the event handler's 
execution method adjust the data structures of your pricer accordingly.

Most constraint handler use an event handler to speed up their domain propagation and 
presolving capabilities. For example, the set packing constraint handler deals with 
constraints

   x_1 + ... + x_k <= 1

on binary variables x_j. Its associated event handler catches events for tightenings of 
the lower bounds of the involved variables. If such an event occurs, it knows that this 
variable has been fixed to 1 and informs the constraint handler that it can fix all other 
variables to zero in its next domain propagation call. If such an event does not occur, 
the constraint handler knows that it does not make sense to look at the constraint in the 
domain propagation and therefore can save the time to process this constraint.



I hope that this helps. In my view, alternative 1 is the best suited for your problem, in 
particular if you can just modify your packing constraints to include the additional variable.


Best, Tobias


E. van der Veen wrote:
> Hi,
> 
> Thanks for your help last time with my question on 
> "Deleting/fixing a SCIP variable". However, I'm now facing 
> another problems with my Branch-and-Price (B&P) 
> implementation in SCIP.
> I know now how to fix variables (via 
> SCIPchgVarLbNode()/SCIPchgVarUbNode()), but I would like a 
> way to store "branching decisions". I can probably best 
> explain what I would like to do by first explaining the 
> most important concepts of my problem and my solution 
> approach first.
> 
> I have a rostering problem, which I'm trying to solve with 
> a B&P approach. In my master problem I've got shifts which 
> employees can work. Each employee has his own set of 
> shifts he can work (due to unavailabilities/preferences 
> employees can have), of course an employee can work only 
> one shift max. In my pricing problem I first choose an 
> employee and than generate the best additional shift for 
> this employee (if this improves the solution of the master 
> problem), via shadow prices of the demand constraints in 
> the master problem. I continue with generating shifts 
> until no more 'improving' shifts are found. However, the 
> solution of the master problem we now get need not be 
> integral (e.g. an employee works two times half a shift). 
> In this case branching has to be applied. I would like to 
> branch on whether employee $i$ works/doesn't work during 
> some period $t$. All shifts violating this should not be 
> worked (and thus variables corresponding to them fixed to 
> 0). Shifts generated for employee $i$ after this branching 
> decision should have a working period in period $t$. The 
> branching/pricing is continued until an optimal (integer) 
> solution is found.
> 
> Generating shifts (via a pricer) is no problem for me. 
> However, the branching is. The problems I'm facing:
> 1. How to remember branching decisions (i.e. $i$ 
> should/should not work during $t$) in subnodes of the 
> current node.
> 2. How to include this branching decisions in the 
> pricer/pricing problem.
> 
> I have thought about this (and tried some approaches) for 
> quite a while. What I've tried is adding variables to the 
> model to "store" branching decisions, i.e. adding 
> variables which tell the problem whether $i$ should/should 
> not work during $t$. However, these variables are not 
> included in any constraint in my master problem and 
> (hence) SCIP fixes them during presolving. Perhaps I could 
> switch the fixing of variables during presolving off, but 
> I' not sure whether this is a good idea. I can imagine 
> that fixing variables can speed up the solution process, 
> which I of course would like.
> 
> Furthermore, I've been investigating whether I can 
> implement my branching rule via constraint handlers. I 
> think it is possible (seen something about constraint 
> handlers being valid only 'locally'), but how do you add a 
> constraint (handlers) only locally (i.e. in some node) or 
> does SCIP do that automatically after calling 
> SCIPcreateChild()? I also looked at the TSP example to get 
> some feeling about the constraint handlers in SCIP, and 
> basically understand how they work. However, I do not 
> (yet) see how to apply it in a B&P approach, because in 
> the TSP example no branching is applied, but 'only' 
> constraints are added (as far as I can see it).
> And, furthermore, is there a way in which I can provide 
> these branching decisions to the pricer (pricing problem)? 
> I think I cannot simply add it to the pricing problem, 
> because when the problem moves out of the current node (or 
> generates a trip for another employee) this constraint is 
> no longer valid. Does anyone have a clue on this?
> 
> I'm sorry for the long e-mail/question. Hope anyone can 
> provide me with some answers to my questions. Any help is 
> appreciated very much. So if you have parts of answers to 
> my questions or have some example code which might be 
> useful to me, I would be very happy with it.
> 
> Thanks in advance.
> Best regards,
> 
> Egbert
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip