[Scip] BRANCH-AND-CUT-AND-PRICE

[Benjamin Müller]

Hi Diego,

sorry for the late response we were quite busy during the last weeks.

Yes, you can use your own separator if you know how the generated cuts 
affect your pricing problem(s). If you can express your cuts only with 
original variables then this does not influence the pricing problem(s) 
and adding your own separator should be easy. If your cuts depend on the 
reformulated variables things get complicated. If you have found new 
columns during the pricing you have to add those to the generated cuts. 
For this it is necessary to set the flag 'modifiable' to TRUE. Do you 
modify the Gomory cuts after pricing new variables? Otherwise your cuts 
are not valid for your master problem.

Probably you already know this but in the SCIP Optimization Suite there 
is a Generic-Cut-and-Price framework (GCG) which performs a 
Dantzig-Wolfe decomposition and solves the LP relaxation via column 
generation. On the web page of GCG:

http://www.or.rwth-aachen.de/gcg/

you might find some interesting papers like this one:

http://www.or.rwth-aachen.de/research/publications/sea2015-basiscuts_01.pdf

which explains how to obtain cuts for the original variables by using 
basis information of the Simplex algorithm.

Unfortunately, I am not an expert for branch-cut and price. Maybe 
someone else can add some useful information or things I missed.


Best regards,

Benny


On 07/09/2015 02:34 PM, dponce at us.es wrote:
>
> Hello scip,
>
> I'm implementing a column generation algorithm for a Binary Linear 
> Problem and I have a few questions about how could work a separator on 
> a B&P framework. In the FAQ (Specific questions about Column 
> Generation and Branch-And-Price with SCIP,9) it is said that in most 
> cases one should deactivate separators. But for a 
> Branch-and-Cut-and-Price I would like to implement my own separator 
> plugin. Which will be the main staff to take care of?
>
> By the moment I've try to use Gomory cuts and what happens is that it 
> is called in every node but no cuts are added.
>
> If I know how these valid inequalities affect my pricing problem, 
> could I implement the separator?
>
> Regards and thanks in advance.
>
> Diego Ponce.
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-- 
______________________________
Benjamin Müller
Zuse Institute Berlin
Takustr. 7, 14195 Berlin
benjamin.mueller at zib.de
+49 30 841 85-195

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150728/594b3d6c/attachment.html>