<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
Hi Abde,<br>
<br>
if the variable names identify the variables and their meaning
uniquely, searching for a variable with that name should be ok to
check whether it already exists.<br>
<br>
You can verify that the duplicate variable is already in the LP by
SCIPvarIsInLP().<br>
It looks like CPLEX sees immediately that no improvement is possible
and therefore, does not do any simplex iterations. You could check
with SoPlex as LP solver, which should give you some more output.
This would also explain why your dual solution does not change.<br>
That CPLEX is finished immediately seems to indicate that there
might be some error in your reduced cost computation. Please check
by SCIPgetVarRedcost() which reduced costs SCIP (or the LP solver)
computed for the already existing duplicate variable.<br>
<br>
Best,<br>
Gerald<br>
<br>
<div class="moz-cite-prefix">Am 12.01.2014 00:56, schrieb Abde Ali
Kagalwalla:<br>
</div>
<blockquote
cite="mid:CAKis+K+mOdBXHHpBX=j78YacCcgJJ_oOMP_Wb-yenKmR655+8w@mail.gmail.com"
type="cite">
<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 moz-do-not-send="true"
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 moz-do-not-send="true" href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a>
<a moz-do-not-send="true" 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>
</blockquote>
<br>
</body>
</html>