[Scip] Using reoptimization

Mon Jul 6 19:57:43 CEST 2015

  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.

  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.

  Best regards,

On Mon, Jul 6, 2015 at 12:29 PM, Andrei Braga <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> 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 listScip at zib.dehttp://listserv.zib.de/mailman/listinfo/scip
>>
>>
>>
>
>
> --
> Andrei Braga
>

-- 
Andrei Braga
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150706/ab5c2dd4/attachment.html>