[Scip] Branching decisions not enforced in master problem during a Branch-and-Price implementation

[Tobias Achterberg]

Hi Egbert,

I can answer your first question, and may help a little bit on your second one.


> I've implemented extra constraints, like Tobias 
> Achterberg, suggested to "store" my branching decisions:
> I've added constraints
> 
> -y_it + \sum_{s covers time t} x_s <= 0
> 
> to the master problem. where y_it is a binary variable 
> capturing "worker i works during period t".
> 
> Now, I get the following. While I fixed one of the y_it to 
> 0, a variable x_s appearing in the corresponding 
> constraint has value 0.5, but by the above constraint this 
> is not allowed (I obtained this value via 
> SCIPgetLPBranchCands) However, I'm pretty sure the fixing 
> went well, because in my pricing problem I included 
> constraints like "if y_it = 0, then in the to be created 
> shift period t cannot be a working period" and I see these 
> constraints appearing in my pricing problem after fixing 
> the y_it. So why is it then that 'the' x_s variable has 
> value 0.5 (like it had initially, i.e. before any 
> branching/pricing had been done)? Do I have to create some 
> kind of domain propagation method and how does one do 
> that, or is there something I am overlooking?

I understand that you created these constraints in addition to your

   \sum_{s covers t} x_s <= 1

constraint, and that you marked the additional constraints of not going into the LP (in 
order to not destroy your pricing problem).

Because of the negative coefficient for y_it you had to add this constraint as a linear 
constraint. Since the constraint is marked as "modifiable" (you want to add more x_s 
variables during the pricing process), the domain propagation cannot conclude

    y_it = 0  =>  x_s = 0

because (since it is a modifiable linear constraint) there may be additional columns with 
negative coefficients. In other words, SCIP has to assume that you (the evil pricer) 
generates, for example, variables that make the constraint into

   -y_it + x_s - z <= 0

and thus, y_it = 0 does not necessarily mean that x_s = 0, because you could set z = 1 to 
still allow for x_s.


By using

    y_it + \sum_{s covers t} x_s <= 1  (or == 1 if you like)

and adding this as a modifiable set packing (or partitioning) constraint, SCIP now knows 
that the only additional coefficients that can be added are +1 coefficients on binary 
variables. Now, it can safely conclude

    y_it = 1  =>  x_s = 0

and you are back in business.


> As an alternative, I tried implementing the above 
> constraint as a set packing constraint like
> 
> y_it + \sum_{s covers time t} x_s <= 1
> 
> where y_it is 1 if worker i is not working during period 
> t, and 0 otherwise.

As explained above, this is exactly what you need to do.#


> However, now I'm faced with some other problems and I'm 
> not sure what the cause is.. It seems that due to some 
> propagation methods or seperation methods (both performed 
> on the setpcc constraints), my branching rule is never 
> called. The former I conclude from the values under 
> '#Propagate' which is displayed in the following 
> information (which I got via SCIPprintStatistics()).
> 
> Constraints:  Number  #Separate #Propagate #EnfoLP #EnfoPS 
> Cutoffs DomReds  Cuts   Conss   Children
>    integral :       0          0          0       1 
>       0       0       0     0       0          0
>    setppc   :       9          0         26       1 
>       1       0       1     3       0          0
>    linear   :       3          0         26       0 
>       0       0       0     0       0          0

Hmm... the statistics say that there are not any children at all, so no branching took 
place. This means that you are in the root node all the time, right?

So, I do not quite understand the issue. What is the unexpected behavior?

Maybe, SCIP did some clever things in presolving. Since it now knows that there are set 
packing constraints involved, it can do some stuff even if the constraints are marked as 
"modifiable". For example, the variables in each constraint still form cliques, and 
consequentially, you can separate clique cuts.

Maybe, you just need to turn off certain SCIP features like presolving or cut generation. 
It would help if you can specify your situation a little bit more in detail and if you can 
send the complete output of the SCIPprintStatistics() call (maybe with a larger line wrap 
value to allow for longer lines or as an attachment).


> Now my problem is how to 'turn this behaviour off', 
> because now pricing problem instances are created which I 
> cannot explain, and which lead to repeatedly generating 
> the same column over and over again, which should not 
> occur during column generation (theoretically). Generating 
> this column over and over again also does not lead to a 
> final solution.
> Does anyone have a clue on this?

You should be able to turn this behavior off via parameter settings. But in order to do 
so, we first have to find out which component causes the behavior.


Best, Tobias