[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