[Scip] Pricing method keeps generating same column

[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,
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140107/7c6f648a/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: log_summarySCIP
Type: application/octet-stream
Size: 14219 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140107/7c6f648a/attachment.obj>