[Scip] How to deal with "branching decisions"

E. van der Veen E.van.der.Veen.7 at student.rug.nl
Wed Aug 27 12:14:30 MEST 2008


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


More information about the Scip mailing list