[Scip] Pricing method keeps generating same column
Abde Ali Kagalwalla
abdeali.iitb at gmail.com
Wed Jan 29 19:09:32 CET 2014
Hi Gerald,
I finally figured out the problem. It turns out that in my code, when I
added a new variable I was modifying the untransformed constraints. Since
transformed constraints was not updated, I kept getting the same dual
values. Thanks for all your help with debugging the issue.
Regards,
Abde Ali
On Thu, Jan 16, 2014 at 11:44 PM, Gerald Gamrath <gamrath at zib.de> wrote:
> Hi Abde,
>
> 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.
>
> You can verify that the duplicate variable is already in the LP by
> SCIPvarIsInLP().
> 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.
> 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.
>
> Best,
> Gerald
>
> Am 12.01.2014 00:56, schrieb Abde Ali Kagalwalla:
>
> Hi Gerald,
>
> Thank you very much for your help.
>
> Here is a response to the additional info. I hope it helps debug the
> problem:
>
> - I am using CPLEX 12.4.0.0 as the LP solver
> - 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.
> - I did add the new variable to all the relevant constraints using
> SCIPaddCoefLinear() function.
> - When I printed out the value of SCIPgetLPSolstat(scip) inside
> SCIP_DECL_PRICERREDCOST function, I got 1.
> - 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.
> - 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
>
> 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):
>
> *********************************************************************************************************************************************************************
> LP Solver <CPLEX 12.4.0.0>: row representation of the basis not available
> -- SCIP parameter lp/rowrepswitch has no effect
> transformed problem has 24 variables (24 bin, 0 int, 0 impl, 0 cont) and
> 4900 constraints
> 4900 constraints of type <linear>
>
> presolving:
> (0.0s) probing cycle finished: starting next cycle
> presolving (1 rounds):
> 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened
> bounds, 0 added holes, 0 changed sides, 0 changed coefficients
> 0 implications, 0 cliques
> presolved problem has 24 variables (24 bin, 0 int, 0 impl, 0 cont) and
> 4900 constraints
> 4900 constraints of type <linear>
> Presolving Time: 0.00
>
> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols
> |rows |cuts |confs|strbr| dualbound | primalbound | gap
> T 0.0s| 1 | 0 | 0 | - |6756k| 0 | - | 24 |4900 | 24
> |4900 | 0 | 0 | 0 | -- | 4.000000e+00 | Inf
> Tried aggregator 1 time.
> LP Presolve eliminated 4784 rows and 0 columns.
> Reduced LP has 116 rows, 24 columns, and 2176 nonzeros.
> Presolve time = 0.01 sec.
>
> Iteration log . . .
> Iteration: 1 Dual objective = 0.500000
> Initializing dual steep norms . . .
>
>
>
>
>
>
>
>
>
>
>
>
>
> *Inside pricing method SCIP LP status: 1 Dual matrix statistics Sum:
> -4.0003 Max Coeff: -0 Min Coeff: -1.0003 Sum of positive pixels 4.0003 Sum
> of zero pixels 0 Var name being added: E24_24_21X21 Computed reduced cost:
> -2.99924 Shot Intensity stats: Sum of values: 441 Min value: 0 Max value: 1*
> Initializing primal norms . . .
> Initializing primal norms . . .
> 0.1s| 1 | 0 | 20 | - |6766k| 0 | 4 | 25 |4900 | 25
> |4900 | 0 | 0 | 0 | -- | 4.000000e+00 | Inf
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> *Inside pricing method SCIP LP status: 1 Dual matrix statistics Sum:
> -4.0003 Max Coeff: -0 Min Coeff: -1.0003 Sum of positive pixels 4.0003 Sum
> of zero pixels 0 Var name being added: E24_24_21X21 Computed reduced cost:
> -2.99924 Var already in LP with solution value: -0 Shot Intensity stats:
> Sum of values: 441 Min value: 0 Max value: 1*
> Reinitializing primal norms . . .
> Computed 1 new norms.
> Initializing primal norms . . .
> 0.1s| 1 | 0 | 20 | - |6768k| 0 | 4 | 26 |4900 | 26
> |4900 | 0 | 0 | 0 | -- | 4.000000e+00 | Inf
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> *Inside pricing method SCIP LP status: 1 Dual matrix statistics Sum:
> -4.0003 Max Coeff: -0 Min Coeff: -1.0003 Sum of positive pixels 4.0003 Sum
> of zero pixels 0 Var name being added: E24_24_21X21 Computed reduced cost:
> -2.99924 Var already in LP with solution value: -0 Shot Intensity stats:
> Sum of values: 441 Min value: 0 Max value: 1*
> Reinitializing primal norms . . .
> Computed 1 new norms.
> Initializing primal norms . . .
> 0.2s| 1 | 0 | 20 | - |6801k| 0 | 4 | 27 |4900 | 27
> |4900 | 0 | 0 | 0 | -- | 4.000000e+00 | Inf
>
> **********************************************************************************************************************************************************************************
>
> 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.
>
> Hope this helpful. Again thank you very much for your help.
>
> Regards,
>
>
>
> On Sat, Jan 11, 2014 at 2:48 PM, Gerald Gamrath <gamrath at zib.de> wrote:
>
>> 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 listScip at zib.dehttp://listserv.zib.de/mailman/listinfo/scip
>>
>>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140129/48026c51/attachment.html>
More information about the Scip
mailing list