[Scip] Pricing method keeps generating same column
Abde Ali Kagalwalla
abdeali.iitb at gmail.com
Sun Jan 12 00:56:02 CET 2014
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 methodSCIP LP status: 1 Dual matrix statisticsSum:
-4.0003Max Coeff: -0Min Coeff: -1.0003Sum of positive pixels 4.0003Sum of
zero pixels 0Var name being added: E24_24_21X21Computed reduced cost:
-2.99924Shot Intensity stats:Sum of values: 441Min value: 0Max 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 methodSCIP LP status: 1Dual matrix statisticsSum:
-4.0003Max Coeff: -0Min Coeff: -1.0003Sum of positive pixels 4.0003Sum of
zero pixels 0Var name being added: E24_24_21X21Computed reduced cost:
-2.99924Var already in LP with solution value: -0Shot Intensity stats:Sum
of values: 441Min value: 0Max 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 methodSCIP LP status: 1Dual matrix statisticsSum:
-4.0003Max Coeff: -0Min Coeff: -1.0003Sum of positive pixels 4.0003Sum of
zero pixels 0Var name being added: E24_24_21X21Computed reduced cost:
-2.99924Var already in LP with solution value: -0Shot Intensity stats:Sum
of values: 441Min value: 0Max 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/20140111/89f020e5/attachment.html>
More information about the Scip
mailing list