<div dir="ltr"><div><div><div><div>Hi Gerald,<br><br></div>Thank you very much for your help.<br><br></div><div>Here is a response to the additional info. I hope it helps debug the problem: <br><br></div><div>- I am using CPLEX 12.4.0.0 as the LP solver <br>
</div><div>- You are right that it seems like the reduced master problem is never re-solved after I finish pricing and add a new variable. I seem to get the same dual values in multiple rounds of pricing. <br></div><div>- I did add the new variable to all the relevant constraints using SCIPaddCoefLinear() function.<br>
</div><div>- When I printed out the value of SCIPgetLPSolstat(scip) inside SCIP_DECL_PRICERREDCOST function, I got 1.<br>- My "display/lpinfo" w already set to TRUE because I had initially copied the various settings from the VRP example code. Also I set the "propagating/rootredcost/freq" parameter to -1 as Gregor had suggested.<br>
</div><div>- I checked if the variable is already present in the LP by checking if SCIP_VAR* var = SCIPfindVar(scip, varName) is NULL or not. The "varName" corresponds to a particular object in my problem. Is this a reasonable way to check if the variable is aleady present in the reduced master problem ? With this check I looked at solution value using SCIPvarGetSol(var, TRUE). The value returned was -0. The reduced cost (computed using my function after extracting dual values) was -2.999<br>
</div><br></div>Here is the log from the first three iterations that I got (I have made the lines that are printed inside my own pricing function SCIP_DECL_PRICERREDCOST bold):<br>*********************************************************************************************************************************************************************<br>
LP Solver <CPLEX 12.4.0.0>: row representation of the basis not available -- SCIP parameter lp/rowrepswitch has no effect<br>transformed problem has 24 variables (24 bin, 0 int, 0 impl, 0 cont) and 4900 constraints<br>
4900 constraints of type <linear><br><br>presolving:<br> (0.0s) probing cycle finished: starting next cycle<br>presolving (1 rounds):<br> 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients<br>
0 implications, 0 cliques<br>presolved problem has 24 variables (24 bin, 0 int, 0 impl, 0 cont) and 4900 constraints<br> 4900 constraints of type <linear><br>Presolving Time: 0.00<br><br> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap<br>
T 0.0s| 1 | 0 | 0 | - |6756k| 0 | - | 24 |4900 | 24 |4900 | 0 | 0 | 0 | -- | 4.000000e+00 | Inf<br>Tried aggregator 1 time.<br>LP Presolve eliminated 4784 rows and 0 columns.<br>Reduced LP has 116 rows, 24 columns, and 2176 nonzeros.<br>
Presolve time = 0.01 sec.<br><br>Iteration log . . .<br>Iteration: 1 Dual objective = 0.500000<br>Initializing dual steep norms . . .<br><b>Inside pricing method<br>SCIP LP status: 1<br> Dual matrix statistics<br>
Sum: -4.0003<br>Max Coeff: -0<br>Min Coeff: -1.0003<br>Sum of positive pixels 4.0003<br>Sum of zero pixels 0<br>Var name being added: E24_24_21X21<br>Computed reduced cost: -2.99924<br>Shot Intensity stats:<br>Sum of values: 441<br>
Min value: 0<br>Max value: 1</b><br>Initializing primal norms . . .<br>Initializing primal norms . . .<br> 0.1s| 1 | 0 | 20 | - |6766k| 0 | 4 | 25 |4900 | 25 |4900 | 0 | 0 | 0 | -- | 4.000000e+00 | Inf<br>
<b>Inside pricing method<br>SCIP LP status: 1<br>Dual matrix statistics<br>Sum: -4.0003<br>Max Coeff: -0<br>Min Coeff: -1.0003<br>Sum of positive pixels 4.0003<br>Sum of zero pixels 0<br>Var name being added: E24_24_21X21<br>
Computed reduced cost: -2.99924<br>Var already in LP with solution value: -0<br>Shot Intensity stats:<br>Sum of values: 441<br>Min value: 0<br>Max value: 1</b><br>Reinitializing primal norms . . .<br>Computed 1 new norms.<br>
Initializing primal norms . . .<br> 0.1s| 1 | 0 | 20 | - |6768k| 0 | 4 | 26 |4900 | 26 |4900 | 0 | 0 | 0 | -- | 4.000000e+00 | Inf<br><b>Inside pricing method<br>SCIP LP status: 1<br>
Dual matrix statistics<br>Sum: -4.0003<br>Max Coeff: -0<br>Min Coeff: -1.0003<br>Sum of positive pixels 4.0003<br>Sum of zero pixels 0<br>Var name being added: E24_24_21X21<br>Computed reduced cost: -2.99924<br>Var already in LP with solution value: -0<br>
Shot Intensity stats:<br>Sum of values: 441<br>Min value: 0<br>Max value: 1</b><br>Reinitializing primal norms . . .<br>Computed 1 new norms.<br>Initializing primal norms . . .<br> 0.2s| 1 | 0 | 20 | - |6801k| 0 | 4 | 27 |4900 | 27 |4900 | 0 | 0 | 0 | -- | 4.000000e+00 | Inf<br>
**********************************************************************************************************************************************************************************<br></div><br>The strange thing here is that dual variables seem be exactly the same from one iteration to the next. I have a matrix of constraints, so I printed out only the sum, min and max for the entire set of dual variables here. Also, the number of variables and problem size seems to be increasing after each pricing round, but there seems to be no change in the dual values.<br>
<div><br></div><div>Hope this helpful. Again thank you very much for your help.<br><br></div><div>Regards,<br><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Jan 11, 2014 at 2:48 PM, Gerald Gamrath <span dir="ltr"><<a href="mailto:gamrath@zib.de" target="_blank">gamrath@zib.de</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
Dear Abde,<br>
<br>
welcome to SCIP and the mailing list!<br>
<br>
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".<br>
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?<br>
<br>
I hope that by this additional information, we will be able to
identify the issue.<br>
<br>
Best,<br>
Gerald<div class="im"><br>
<br>
<div>Am 07.01.2014 18:38, schrieb Abde Ali
Kagalwalla:<br>
</div>
</div><blockquote type="cite">
<div dir="ltr">
<div>
<div>
<div>
<div>
<div>Hi SCIP Developers,<br>
<br>
</div><div><div class="h5">
<div>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.<br>
</div>
<div><br>
</div>
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.<br>
<br>
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.<br>
<br>
</div></div></div><div><div class="h5">
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.<br>
<br>
</div></div></div><div><div class="h5">
<div>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. <br>
</div>
<br>
</div></div></div><div><div class="h5">
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.<br>
<br>
</div></div></div>
Sincere Regards,<br>
</div>
<br>
<fieldset></fieldset>
<br><div class="im">
<pre>_______________________________________________
Scip mailing list
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a>
<a href="http://listserv.zib.de/mailman/listinfo/scip" target="_blank">http://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
</div></blockquote>
<br>
</div>
</blockquote></div><br></div>