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

[E. van der Veen]

Hi Tobias (and all who are interested),

Thanks for your e-mail last week. It really helped me! I 
now use the set packing constraints to cover my "branching 
decisions", which cause SCIP to indeed conclude whenever 
one variable of a constraint is set to 1 (due to a 
branching) all other variables in this constraint have to 
be 0.

Concerning my other issue, SCIP indeed never left the root 
node, because SCIP did some cut generation after which 
some of my "branching variables" (which we indicated by 
y_it in previous mails) got fixed and after which SCIP 
concluded it had found an optimal solution (which is not 
optimal for my problem), because there are no columns with 
negative reduced cost anymore.

However, when I do not call SCIPincludePresolDualFix() in 
the SCIPincludeDefaultPlugins() call, this problem is 
fixed and branching occurs according to my own branching 
rule/scheme!
To be on the save side I also set sepa_maxrounds, 
sepa_maxroundsroot, sepa_maxcuts, and sepa_maxcutsroot to 
0, because in the output of the SCIPprintStatistics() call 
I saw that some seperators are called (which cause no 
problems in the instance I have now, but I'm not sure 
whether they'll do this for larger/other instances) and 
after I set this parameters to 0 there are no separators 
called anymore.

However, I'm left with one minor issue.. Sometimes SCIP 
generates the same column twice in a row (i.e. pricer 
generates a column, immediately after that the pricer is 
called again and then it generates the same column again). 
I think this is caused by the fact that the dual problem 
is not updated correctly after the first call to the 
pricer. I conclude this from the fact that the dual 
solution is still the same after adding the first column 
to the master, which should not be the case because an 
extra column is generated for the primal/master problem 
and hence an extra constraint is generated for the dual by 
which the previous dual solution is not allowed anymore. 
However, after generating the same column again the pricer 
is called once more and then it does not generate that 
same column again, because now the dual solution is as it 
should be. So, I'm a little confused here. How can such a 
thing happen? I did make the appropriate calls to 
SCIPgetTransformedCons() and set presol_maxrestarts to 0.
Even more strange, to me at least, this 'behaviour' does 
not occur everytime, because for some of the generated 
columns the dual costs are updated as I expected. The only 
difference I saw, between this case (*) and the case where 
the same column is generated twice in a row (**), is that 
in the case (*) there are no constraints on variables in 
the pricing problem which are due to branching decision 
(and in case (**) some variables of the pricing problem 
_are_ fixed due to branching decisions).
Does anyone have any clue on whats going on overhere? Hope 
my explanation is clear, or if you need some specific 
details, please say so.

Thanks in advance for any help you can provide me with!

Best regards,
Egbert


On Thu, 04 Sep 2008 18:36:54 +0200
  Tobias Achterberg <achterberg at zib.de> wrote:
> 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
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip