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

[Andreas Gebauer]

Hi Gerald,

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

Simple but surprisingly effective! That was the very thing.

Thanks a lot!

Best regards,
Andreas

Am 03/22/13, schrieb Gerald Gamrath  <gamrath at zib.de>:

> 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
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip