[Scip] How to update separators/constraint handlers in a branch and cut and price?

[Gerald Gamrath]

Hi Nikolaj,

> There is something I don't understand here. I thought I could concentrate
> on the core model (the initial constraints) without taking into account
> the added cuts (the additional and non mandatory constraints) to find and
> add new variables. Some cuts (i.e. \sum_i x_i <= 1 for example) don't even
> need to be updated (they could be replaced later by a new updated version
> found by a separator with more variables if needed) while some difficult
> to generate cuts could be updated with the new generated variables. Do you
> mean it is better (or mandatory?) to generate new variables with respect
> of the dual variables of ALL the constraints (the initial and added ones)?
> If this is the case, doesn't this complicate the process to find violated
> dual constraints/primal variables with negative reduced cost?
>
> What am I missing here?
>   
You are right. Cutting plane separation complicates the column
generation process in most cases. But there is actually no other way, if
you want to combine both.

If you concentrate on the core model, then the added cuts are somehow
ignored, i.e. if you add a cut x_1 + x_2 <= 1 and this cut really cuts
off the current LP solution, the pricing process would in most cases
give you a variable similar to x_1 or x_2 (but without coefficient in
the cut) because by adding this variable to the LP and increasing its
value, the old LP solution can actually be restored. Thus, the cut has
no effect on the actual solution.
Normally, the reduced costs ensure that variables are created at most
once, but then, you would have to respect the dual variables of all rows
in the LP. Otherwise, forbidding the re-creation of a variable is not so
easy, you would need to forbid some solution in the pricing problem and
look for the k-th best solution which is often much harder than finding
an optimal solution.
> I was thinking about a solution like that. If I'm not wrong, when I try to
> add cuts (SCIPaddPoolCut) with the flag modifiable set to TRUE, SCIP
> returns an error. What is the difference between the separation storage
> (SCIPaddCut) and the global cut pool (SCIPaddPoolCut)?
>
>   
Yes, you are not allowed to add modifiable cuts to the cut pool. The cut
pool is a storage for globally valid cuts, that are possibly not helpful
for the current seperation round, but costly to find, so you store them
in the cut pool and check these cuts in subsequent separation rounds
whether they can then cut off the current solution. What you need to do
is to add the cut to the separation storage by calling SCIPaddCut(). The
separation storage stores all cuts created in one separation round and,
after the round, selects a subset of these cuts, w.r.t. efficacy,
orthogonality to each other and parallelism to the objective function
and adds these cuts to the LP.

So your separators should either add the cuts to the separation storage
and let SCIP choose which cuts are added to the LP or you should try one
of the approaches proposed in my previous mail and select the cuts
yourself, but even in this case, you finally have to add the cuts to the
separation storage (possibly with the forcecut parameter set to TRUE),
so that SCIP takes them from the separation storage and adds them to the
LP after the separation round.

Best regards,
Gerald