[Scip] Column generation, meaning of the output from CPLEX after a column is added

[Xavier Schepler]

Here's the meaning of this message.
The third line seems to indicate that heavy computations are performed.

"
These messages refer to steepest edge norms for the primal simplex 
method.   Since you are adding columns to your master LP, you presumably 
invoke the primal simplex method because the previous basis remains 
primal feasible as long as 0 is in the domain of your newly added 
variable.   CPLEX has already calculated steepest edge norms for the 
columns in your previous master LP.   The addition of the new column 
doesn't affect the validity of those norms relative to the current 
basis, but CPLEX needs to compute a new norm for this newly added 
column.   That explains the first two lines of output, which I suspect 
do not take much time.

The third line about initializing primal norms surprises me a bit.   
This indicates that CPLEX decided to reinitialize all the steepest edge 
norms.   This involves a nontrivial amount of work that could amount to 
roughly m/2 simplex iterations. So, I presume the long time you see 
occurs after this third message.   While there are reasons to 
reinitialize the steepest edge norms, I don't see off the top of my head 
why it would need to do that here.  It would be interesting to see 
whether the norms are reinitialized immediately after the one new norm 
was computed, or later on.   If you set the simplex display level to 2, 
you can see whether any simplex iterations occur between the first two 
messages and the third one.   That may shed some light on the issue.

Regarding more info on steepest edge pricing and the maintenance and 
updates of the norms, some of the more computationally oriented LP text 
discuss this.   You could try 'Computer Solution of Linear Programs' by 
Larry Nazareth, and I'm sure there are others.
"

Best,

Xavier

Le 11/03/2014 18:04, Gerald Gamrath a écrit :
> Hi Xavier,
>
> I can only guess what it means: Probably, the steepest edge norm for 
> the new column is computed, because we use the steepest edge pricing 
> method within CPLEX by default. Is there any more output? But probably 
> the time is spent for solving the LP after the norms were initialized, 
> CPLEX does not always print output for that.
>
> You can also try to change the CPLEX pricing method to something else, 
> e.g., devex pricing by setting the parameter "lp/pricing = d" and see 
> how this changes the behavior.
>
> Best,
> Gerald
>
> On 11.03.2014 16:49, Xavier Schepler wrote:
>> Hi,
>>
>> What does the following message mean :
>>
>> Reinitializing primal norms . . .
>> Computed 1 new norms.
>> Initializing primal norms rowwise . . .
>>
>> produced each time a column is added ?
>> So much time (several seconds) is spent between each of this line.
>> It appears at each column generation iteration.
>> Then the LP is re-optimized.
>>
>> Best,
>>
>> Xavier
>>
>>
>>
>>
>> _______________________________________________
>> Scip mailing list
>> 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/20140312/9ac8f0b3/attachment.html>