[Scip] Using reoptimization

Jakob Witzig witzig at zib.de
Mon Jul 6 21:22:04 CEST 2015


Hi Andrei,

Am 06.07.2015 um 19:57 schrieb Andrei Braga:
>   Dear all,
>
>   I have successfully used reoptimization in solving a subsequence of 
> P_0, P_1, P_2, ... with the property that the feasible region of the 
> programs is never enlarged. Therefore, the previous segmentation fault 
> might indeed be related to not having this property.
Very good :-) Nevertheless, I will add more checks and warnings to avoid 
such segmentation faults and unclear behavior.

>
>   My problem now is that too much memory is consumed. For some of the 
> programs, there are more than 200000 of nodes in the B&B tree. When 
> reoptimization is enabled, memory consumption is more than 8GB. I've 
> ajusted parameters limits/memory and memory/savefac, but the memory 
> consumption is still of the same order.
Indeed, the reoptimization has a large memory consumption because the 
complete search frontier and all interior nodes were strong branching 
was performed need to be stored. Therefore, you can limit the size of 
the stored tree (reoptimization/maxsavednodes) or use the compression 
heuristics to rearrange and resize the stored tree. You can enable the 
compression with the parameter "compression/enable". If you use the 
compression heuristics SCIP calls these heuristics after presolving and 
before solving the root node.

Best,
Jakob

>
>   Best regards,
>
>
> On Mon, Jul 6, 2015 at 12:29 PM, Andrei Braga <andreisampaio at gmail.com 
> <mailto:andreisampaio at gmail.com>> wrote:
>
>       Dear Gerald,
>
>       Thanks for your quick reply. I'm sorry for my late answer.
>
>     On Fri, Jul 3, 2015 at 8:25 AM, Gerald Gamrath <gamrath at zib.de
>     <mailto:gamrath at zib.de>> wrote:
>
>         Dear Andrei,
>
>         I'm happy to hear that you tried the new reoptimization
>         feature. As far as I can see, you are using it within
>         branch-and-price to solve the pricing problems, which was
>         actually one of the major motivations for this feature.
>
>
>       You're right that I'm trying to use reoptimization to solve
>     pricing problems within a branch-and-price. I think it would be
>     very useful for my application.
>
>
>         It currently only supports sequences of binary problems in
>         which the objective function is changed from one problem to
>         the next or in which the feasible region is restricted when
>         proceeding in the sequence.
>
>
>       By the note at the end of reoptimization's documentation page
>     (http://scip.zib.de/doc/html/REOPT.php), which says "Currently,
>     the reoptimization feature only supports pure binary and mixed
>     binary programs. [...]", I though that I could use this feature
>     for programs with both binary variables and continuous variables
>     with unrestricted bounds. Now, this doesn't seem true.
>
>         Since the (frontier of the) tree needs to be collected in the
>         first run and will be rebuild in subsequent runs, you need to
>         enable the reoptimization feature before solving P_0.
>         Infeasible subproblems are disregarded in subsequent runs
>         which is not valid anymore if you enlarge the feasible region.
>         This might be the reason for the segmentation fault.
>
>
>         It seems that we still have to add some more checks in the
>         reoptimization code and give more expressive warning/error
>         messages. :-)
>
>         One positive answer: Objective coefficients equal to zero are
>         totally ok.
>
>
>         Understood.
>
>
>         Jakob (CC), the main developer of the optimization feature, is
>         out of office today but will have a closer look on Monday.
>         Perhaps you could send your problems P_0 and P_1 directly to
>         us so that we can reproduce the issue?
>
>
>       Yes, I'll do this. Thank you very much.
>
>
>         Best,
>         Gerald
>
>
>
>         Am 02.07.2015 um 21:01 schrieb Andrei Braga:
>>           Dear all,
>>
>>           I'm trying to use the reoptimization feature added to SCIP
>>         3.2 in solving a sequence of mixed binary programs P_0, P_1,
>>         ..., P_k. Programs P_i and P_i+1 differ by the objective
>>         coefficients and by the bounds of some binary variables. It
>>         is possible that some binary variable is fixed to 1 (resp. 0)
>>         in P_i and to 0 (resp. 1) in P_i+1. Does this invalidate the
>>         use of the reoptimization feature?
>>
>>           I want to enable reoptimization after solving P_0. I've
>>         done that (by calling SCIPenableReoptimization). However,
>>         I've got the following assert fail:
>>         src/scip/scip.c:12795: SCIPtransformProb: Assertion
>>         `scip->origprimal->nsols == 0' failed.
>>
>>           I've also tried to enable reoptimization before P_0. In
>>         this case, even compiled in debug mode, my program produced a
>>         segmentation fault; in valgrind's (memory checker) output I
>>         can see the following
>>
>>         ==1966== Invalid read of size 8
>>         ==1966==    at 0x6BD682: reoptSimilarity (reopt.c:378)
>>         ==1966==    by 0x6CAF03: reoptSaveNewObj (reopt.c:3807)
>>         ==1966==    by 0x6CC685: SCIPreoptAddRun (reopt.c:4313)
>>         ==1966==    by 0x700772: SCIPsolve (scip.c:14644)
>>         ==1966==    by 0x4350F0: pricerRedcostForest
>>         (pricer_forest.c:4242)
>>         ==1966==    by 0x6AA19C: SCIPpricerRedcost (pricer.c:372)
>>         ==1966==    by 0x6AA513: SCIPpricerExec (pricer.c:456)
>>         ==1966==    by 0x785385: SCIPpriceLoop (solve.c:1927)
>>         ==1966==    by 0x7866A3: priceAndCutLoop (solve.c:2189)
>>         ==1966==    by 0x7895B1: solveNodeLP (solve.c:2835)
>>         ==1966==    by 0x78BB8F: propAndSolve (solve.c:3494)
>>         ==1966==    by 0x78CE01: solveNode (solve.c:3793)
>>         ==1966==  Address 0x8109450 is 0 bytes after a block of size
>>         896 alloc'd
>>         ==1966==    at 0x4C2B6CD: malloc (in
>>         /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
>>         ==1966==    by 0xB816CE: BMSallocMemoryArray_call (memory.c:406)
>>         ==1966==    by 0x6CAB2B: reoptSaveNewObj (reopt.c:3767)
>>         ==1966==    by 0x6CC685: SCIPreoptAddRun (reopt.c:4313)
>>         ==1966==    by 0x700772: SCIPsolve (scip.c:14644)
>>         ==1966==    by 0x43FFA1: heurExecInitforest
>>         (heur_init_forest.c:437)
>>         ==1966==    by 0x5BC84A: SCIPheurExec (heur.c:1010)
>>         ==1966==    by 0x77FF36: SCIPprimalHeuristics (solve.c:316)
>>         ==1966==    by 0x78C8EA: solveNode (solve.c:3716)
>>         ==1966==    by 0x78FDBB: SCIPsolveCIP (solve.c:4431)
>>         ==1966==    by 0x700C67: SCIPsolve (scip.c:14688)
>>         ==1966==    by 0x75AFB7: fromCommandLine (scipshell.c:99)
>>
>>           Final question: Is there a problem to have objective
>>         coefficients equal to zero during reoptimization?
>>
>>           Many thanks in advance,
>>
>>         -- 
>>         Andrei Braga
>>
>>
>>         _______________________________________________
>>         Scip mailing list
>>         Scip at zib.de  <mailto:Scip at zib.de>
>>         http://listserv.zib.de/mailman/listinfo/scip
>
>
>
>
>     -- 
>     Andrei Braga
>
>
>
>
> -- 
> Andrei Braga
>
>
> _______________________________________________
> 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/20150706/9fee368e/attachment.html>


More information about the Scip mailing list