[Scip] Pricing method keeps generating same column

[Gerald Gamrath]

Dear Abde,

welcome to SCIP and the mailing list!

This sounds very strange and should not happen, but I need some more 
information to identify the issue. Which LP solver did you use? What is 
somehow strange is that all the primal LPs did not need any LP 
iterations. Did you add the variables to the constraints? Can you please 
check the LP solution status within the scip_redcost method by calling 
SCIPgetLPSolstat(scip)? And please activate the LP solver output by 
changing "display/lpinfo" to TRUE, or in the shell "set disp lpinfo T".
Also, if you find that the variable you would like to create is already 
in the problem, can you check the reduced cost of this variable and its 
solution value?

I hope that by this additional information, we will be able to identify 
the issue.

Best,
Gerald

Am 07.01.2014 18:38, schrieb Abde Ali Kagalwalla:
> Hi SCIP Developers,
>
> I am a graduate student at UCLA, and I recently came across your 
> wonderful API for solving branch and price problems. Thank you very 
> much for this work. I am hoping to use this in my research.
>
> I am currently working on an integer problem for an academic research 
> project where all variables are binary. The number of binary variables 
> (let's call it N) is very large for my problem, so I decided to 
> implemented a simple branch and price method using SCIP in C++. I am 
> facing some issues in correctly using the API and would really 
> appreciate your help. Sorry for the longish email describing the 
> details of my approach.
>
> I initially added a small number of variables/columns to the master 
> problem which ensures that the initial RMP is feasible. Then, I 
> implemented a simple pricing method by modifying the 
> SCIP_DECL_PRICERREDCOST(ObjPricerMF::scip_redcost) function. In order 
> to check if I am using the API correctly or not, I first implemented a 
> simple pricing method: I iterate over all the N potential columns and 
> pick the best one with minimum reduced cost. If the minimum reduced 
> cost is positive, no new variable is inserted. Of course, this would 
> be slow, but I am trying this out just to ensure that I am using the 
> SCIP API correctly.
>
> But what I found in my log is that the pricing problem seems to pick 
> the same column in every iteration. As a result the number of 
> variables in the master LP keeps growing by one in every iteration but 
> there is absolutely no change in the values of the dual variables. The 
> reduced cost of the inserted variable also does not change at all. As 
> a result, the program never terminates.
>
> To prevent re-insertion of the same variable, I then tried to keep 
> track of already added variables to ensure that the same variable is 
> not added twice. I did this by defining a map STL as a member of 
> ObjPricer class. With this approach the optimization finishes, but it 
> returns a non-optimal result. Basically, it only seems to use the 
> columns I inserted initially before pricing.
>
> Any ideas on what the issue could be ? I am attaching the summary 
> results from SCIP I got when I ran the first scenario where the same 
> column kept getting inserted. Note that I had to press Ctrl + C to 
> terminate. I would really appreciate any help/suggestions to resolve this.
>
> Sincere Regards,
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

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