[Scip] Pricing performs apparently useless rounds in column-and-row generation approach

[Gerald Gamrath]

Hi Andreas,

when you create the constrains in your pricer, do you set their initial
flag to TRUE?

If you create them with initial=FALSE, the following might have
happened: You create variables and constraints, but the rows are not
immediately added to the LP. SCIP continues pricing until no new
variables are found, after that, separation is performed, where some of
the previously created constraints add their rows to the LP (thus, the
number of rows is increased). This invalidates the current LP solution,
the LP is reoptimized and pricers are called again.

In you second example, there are three columns added from the first to
the second line, so here, the variable pricer might have added
something. Another reason could be that a propagator tightened some
domains after an LP was solved, which also causes another pricing round.

However, you cannot really see what happens just from the output you
posted, because the display lines of SCIP are only printed every 100
pricing calls or if you set the verblevel to full. You can do that to
get some more output (if you did not already do it). Furthermore, to be
sure, you could call SCIPprintDisplayLine() within the pricerredcost
callback, so you could see what is really added by pricing (the
difference between the line printed in the pricer and the line
afterwards, which is printed after vars and rows were added).
Moreover, you could print the statistics by SCIPprintStatistics() in
each pricer call to see propagations, or you could even enable debugging
output by adding "#define SCIP_DEBUG" at the top of src/scip/solve.c

If you need help to analyze the output, please send it to me directly,
it might be quite a lot.

Best,
Gerald


On 21.03.2013 14:55, Andreas Gebauer wrote:
> Hi all,
>
> I'm working on a simultaneous column-and-row-generation approach.
> When testing with various instances, SCIP behaves in a way I don't understand.
>
> After adding new variables (with SCIPaddPricedVar) and constraints (with SCIPaddCons) in the ObjPricer redcost method, SCIP performs a LP-iteration (as it should be).
> Sometimes, the next pricing round does not find solutions with negative reduced costs. 
> Normally, the pricing should be aborted (delay flag is set to TRUE) but SCIP reruns the pricer with dual variables that differ from the last ones.
> Now, solutions with negative reduced costs are found and the process continues normally.
>
> I observed that this behaviour comes along with divergent numbers of vars and cols or cons and rows.
> The best (and only) explanation I have is that there is something wrong with the way I add the constraints (or variables) in solving status.
> Does anybody of you have an idea what a typical mistake might be?
>
> Some display lines are attached at the end of the mail that hopefully make clear what the problem is about.
>
> Best regards,
> Andreas
>
> 1.Example:
>  time | node  | left  |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr|  dualbound   | primalbound  |  gap   
>   4.6s|     1 |     0 |   567 |     - |3523k|   0 |   0 |1017 | 977 |1017 | 952 |  92 |   0 |   0 | 2.304000e+02 | 2.314000e+02 |   0.43%
>   4.6s|     1 |     0 |   567 |     - |3523k|   0 |   0 |1017 | 977 |1017 | 952 |  92 |   0 |   0 | 2.304000e+02 | 2.314000e+02 |   0.43%
> [a pricing round is performed without adding new variables (since objective value of best pricing solution is 0)]
>   4.7s|     1 |     0 |   616 |     - |3529k|   0 |   0 |1017 | 977 |1017 | 964 | 104 |   0 |   0 | 2.304000e+02 | 2.314000e+02 |   0.43%
>   4.7s|     1 |     0 |   616 |     - |3529k|   0 |   0 |1017 | 977 |1017 | 964 | 104 |   0 |   0 | 2.304000e+02 | 2.314000e+02 |   0.43%
> [now, new variables with negative reduced costs are found]
>
>
> 2.Example:
>   0.1s|     1 |     0 |    13 |     - |1925k|   0 |   0 | 504 | 514 | 501 | 501 |   0 |   0 |   0 | 1.600000e+02 | 2.000000e+02 |  25.00%
> [a pricing round is performed without adding new variables (since objective value of best pricing solution is 0)]
>   0.1s|     1 |     0 |    15 |     - |1925k|   0 |   0 | 504 | 514 | 504 | 501 |   0 |   0 |   0 | 1.600000e+02 | 2.000000e+02 |  25.00%
> [now, new variables with negative reduced costs are found]
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip