[Scip] Pricing method keeps generating same column
Gerald Gamrath
gamrath at zib.de
Fri Jan 17 08:44:46 CET 2014
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
> <mailto: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 list
>> Scip at zib.de <mailto: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/20140117/7f5402af/attachment.html>
More information about the Scip
mailing list