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

nikolaj@crt.umontreal.ca nikolaj at crt.umontreal.ca
Tue Aug 24 15:26:13 MEST 2010


On Fri, August 20, 2010 5:48 pm, Gerald Gamrath wrote:
> Hi Nikolaj,
>
>
Hello Gerald and the others,

Thank you very much for your answer. I prefer to reply within your message
as I find this easier.

> you do not need to implement constraint handlers, separators should be
> sufficent if you just want to add some cuts to your problem.

Ok, great.

>
> First of all, cuts that you generate during the branch-cut-and-price
> process should be defined for all variables, i.e. also for the huge set of
> variables treated implicitly by the pricer. Thus, you do not have to
> update your separators after creating new variables, but you have to
> respect the cuts within the pricing process, that means you should handle
> the dual variables corresponding to the cuts in your pricing problem and
> you should add the new variables not only to the initial constraints, but
> also to the cuts (by calling SCIPaddVarToRow()).

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?

>
> For your second question: What you describe is partially done
> automatically by SCIP, so cuts are stored in a separation storage and after
> each separation round, SCIP chooses the best of these cuts (wrt. to
> strength and numerics), adds them to the LP and discards the others. If
> you want to choose the the cuts wrt. another criterion, then you could do
> two things: Either you implement a "master separator" that has an array of
> rows stored in its data and methods to add new rows to this array,  that
> you can use in  the other separators instead of adding the rows to the cut
>  pool. The "master separator" should have a very high priority, so that it
> is called after all other separators. It then chooses the "best" rows from
> this array and adds them to SCIP's separation storage (note that you can
> set the "forcecut" parameter in the SCIPaddCut() method to TRUE,  so that
> SCIP does not select only the best cuts).
> The second possibility would also need a master separator, but you could
> add the cuts by SCIPaddCut() to SCIP's  separation storage and then use the
> methods SCIPsepastoreGetCuts() and SCIPsepastoreGetNCuts() to access
> SCIP's separation storage, SCIPsepastoreClearCuts() to remove the cuts
> from the separation storage (you should capture the rows before, so that
> they are not deleted) and again add the cuts with the forcecut parameter
> set to TRUE.

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)?

Thank you again for your help. I would like to add that I'm using SCIP
since two years now and I'm very happy with it. Thank you very much for
giving us such a great tool.

Have a nice day/night,

Nikolaj
>
> Best,
> Gerald
>
>
>







More information about the Scip mailing list