[Scip] Slow LP re-optimization after branching

[Timo Berthold]

Hi Xavier,

assuming that by "the third one", you mean strange_1.txt, I see the
following:
1. You imposed a time limit of half an hour to SCIP.

2. The initial LP already has 154898 variables and 91061 constraints.
None of them are of set covering type, which is unusual for Branch&Price.
I guess this is due to all of them being modifiable. Nevertheless, when
you create them on your own, you should consider using the specialized
versions of linear constraints (setppc, logicor, kanpsack...)

3. You are not using SoPlex as LP solver, but Cplex. Also, you seem to do
some postprocessing with Cplex as standalone MIP solver.

4. Not to solve a 100kx100k LP within 20 minutes is unusual, unless it is
really ill-conditioned. It would be interesting to see how any LP solver
behaves on it standalone.
Is it possible that you write it to a file and upload it somewhere
(definitely too large for a mail attachment) such that we can have a look?
Dumping should work as follows:
SCIP_CALL( SCIPprintTransProblem(scip, "prob.lp", NULL, FALSE) )
somewhen after you created and transformed the problem (e.g., after
SCIPsolve(), but before SCIPfree(), maybe with a
SCIP_CALL( SCIPsetLongintParam(scip,"limits/nodes", 1) )
to stop after the root.

5. It is conspicuous that your own output of initialization time pretty
much fits the difference between this 1/2 hour and the time SCIP needs for
the root LP. So might it be that this is called when SCIP is already
running and we just the output in different order because it comes via
different streams?
So or so, you might want to add a SCIP_CALL( SCIPprintStatistics(scip) )
after SCIP's termination to see where time went within SCIP.

Timo

> Please find attached to this mail 3 logs.
> Two of them are complete logs for 2 instances.
> The third one is a log without SoPlex output, where the message "LP solver
> hit time limit" appears several times.
> CG iteration #1 indicates a new node.
>
> Best regards,
>
> Xavier Schepler
> PhD student,
> University of Le Havre
>
>
> 2014-02-21 10:25 GMT+01:00 Xavier Schepler <xavier.schepler at gmail.com>:
>
>> Thanks Dr. Gerald for your quick response.
>>
>> I will send you a complete log today.
>>
>>
>> 2014-02-21 10:09 GMT+01:00 Gerald Gamrath <gamrath at zib.de>:
>>
>>  Dear Xavier,
>>>
>>> if you don't set a timelimit, then the LP solver should normally not
>>> have
>>> a time limit either which it can hit. Could you send me the complete
>>> log?
>>>
>>> A few minutes for LP solving might happen, especially if there are some
>>> numerical troubles. Anyway, it is definitely not what one would hope
>>> for,
>>> especially not for a branch-and-price approach.
>>>
>>> You can set "display/lpinfo" to TRUE in order to see the SoPlex output
>>> and "display/verblevel" to 5 to get a bit more output, in particular
>>> about
>>> numerical problems.
>>>
>>> We are currently finishing the next SCIP release and hope to get it
>>> done
>>> today. I would suggest you switch to that when it is available, because
>>> there has been some improvement for branch-and-price in there, in
>>> particular for the master problem reoptimization.
>>>
>>> Best,
>>> Gerald
>>>
>>> Am 21.02.2014 09:55, schrieb Xavier Schepler:
>>>
>>>  Hi professor Lübbecke,
>>>
>>> The B&P is working fine on small instances.
>>>  For some bigger instances, most of the computing time is spent in
>>> solving linear relaxations of restricted master problems.
>>>
>>>   Can you plot the objective function values (over iterations) of the
>>> restricted master problem (to check whether you have strong tailing
>>> off)?
>>>
>>>   Did you check dual variable development (you can plot this as well)
>>> to
>>> check whether you have unstable duals?
>>>
>>>  Tailing off is a real problem, since an optimal value to the linear
>>> relaxation of a master problem (v_mp) is attained in a few column
>>> generation iterations,
>>> but, the lagrangian bound is very far away, and needs many more
>>> iterations to meet v_mp .
>>>
>>>    However, you could tell us about your branching rule. Branch on
>>> master vars (uah...) or on other information (like "original" vars)?
>>> Ryan-Foster?
>>>
>>> Branching is done on original variables, and branching constraints are
>>> added to the structural constraints,
>>> as it is described in Gerald Gamrath thesis.
>>>
>>>   Give us a little more detail. [BTW, you fix the *local* UBs of the
>>> vars, right?]
>>>
>>>   Well, I fix local upper bounds.
>>>
>>>   Out of curiosity: what is "time limit"
>>>
>>> I don't know exactly what the time limit is, but SCIP outputs :
>>> LP solver hit time limit.
>>>
>>>   and "a very long time?"
>>>
>>> Maybe several minutes, which seems quite long for LP re-optimization.
>>>
>>>  I would like SoPlex to display information ...
>>>
>>>  Best regards,
>>>
>>> Xavier
>>>
>>>
>>> _______________________________________________
>>> Scip mailing
>>> listScip at zib.dehttp://listserv.zib.de/mailman/listinfo/scip
>>>
>>>
>>>
>>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>