[Scip] Slow LP re-optimization after branching

[Marco Lübbecke]

Hi Xavier,

did you profile your code to check where the time is spent? 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? Do you have a heavily degenerate restricted master problem
(check percentage of basic vars at value zero)?

I do not believe that adding a branching constraint instead of fixing vars
to zero helps. However, you could tell us about your branching rule. Branch
on master vars (uah...) or on other information (like "original" vars)?
Ryan-Foster? Give us a little more detail. [BTW, you fix the *local* UBs of
the vars, right?]

Finally, 80k conss is not a small deal in B&P. Out of curiosity: what is
"time limit" and "a very long time?"

--Marco




2014-02-20 16:22 GMT+01:00 Xavier Schepler <xavier.schepler at gmail.com>:

> Hello,
>
> In a branch-and-price algorithm, to enforce branching constraints,
> I'm fixing variables at 0 in master problems,
> and adding branching constraints in pricing problems.
>
> Master LPs are in general quite big : more than 100k variables at start,
> and more than 80k constraints.
> Note that, most of these variables are no column variables, but static
> variables.
> Some column variables (in general, 1K) are part of initial master LP.
> When a node is opened, to enforce a branching constraint,
> corresponding column variables values in current master problem are fixed
> with SCIPchgVarUb,
> by the constraint handler, setting their Ub values to 0.
>
> Reoptimization of master LPs then may take a very long time,
> causing LP solver to hit time limit, and to use pseudo solution instead.
>
> Could adding a branching constraint : a sum of variables equal to 0,
> in master problems, be faster for LP re-optimization ?
>
> Best regards,
>
> Xavier Schepler
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>
>


-- 
Prof. Dr. Marco Lübbecke
RWTH Aachen University
Chair of Operations Research
Kackertstrasse 7
D-52072 Aachen
Germany

fon / fax: +49 241 80-93362 / 92369
marco.luebbecke at rwth-aachen.de
www.or.rwth-aachen.de/luebbecke

<http://scholar.google.de/citations?user=cYIpR60AAAAJ>
<https://www.researchgate.net/profile/Marco_Luebbecke/>
<http://www.informatik.uni-trier.de/%7Eley/pers/hd/l/L=uuml=bbecke:Marco_E=.html>
<https://www.xing.com/profiles/Marco_Luebbecke>
<https://plus.google.com/u/0/100665281566037430285/>
<http://de.linkedin.com/pub/marco-l%C3%BCbbecke/7b/a2a/77/>
<https://www.facebook.com/OperationsResearchRWTH>
<https://twitter.com/#%21/mluebbecke> <http://klout.com/#/mluebbecke>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140220/563812a9/attachment.html>