[Scip] Slow LP re-optimization after branching

[Xavier Schepler]

Just a precision.

In my model, there is a valid lower bound on the master problem continuous
relaxation value.
I stop column generation when a restricted master problem continuous
relaxation value is equal to this bound,
even if the lagrangian bound is still oscillating.
For instances of practical interest, this bound is always met quickly.
So, as my initialization is good, no columns are generated for a long time
in a B&P execution.
Only LP solving (without CG) and branching ...


2014-02-21 9:55 GMT+01:00 Xavier Schepler <xavier.schepler at gmail.com>:

>  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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140221/b50d70e4/attachment.html>