[Scip] Early Branching issues

Gerald Gamrath gamrath at zib.de
Fri Feb 8 12:11:49 MET 2013


Hi Jose,

if you think that cuts can really help for your problem, I would suggest
you do a restart, because you start again with the root node in this
case, including separation.

My suggestion would be the following:
1) call SCIPrestartSolve() to restart the solving process when you are
done with pricing
2) In the EXITSOL-callback of the pricer, you should be able to call
SCIPdeactivatePricer()
3) set the constraints to be unmodifiable either before 1) or in 2)
4) the solving restarts and even presolving is performed again and can
do more reductions than with pricers enabled and modifiable constraints

Alternatively, you could also create a global copy of the problem using
SCIPcopy(). Don't forget to set the enablepricing flag to FALSE to
switch off pricing, which also set the constraints to not be modifiable.
However, in this case you have to transfer the solution from the copy to
your main SCIP instance, which you can do by giving an empty variable
hash maps to the SCIPcopy() call which is then filled and can be used
for the transformation. For an example of how you can do this, please
have a look at heur_rens.c or presol_components.c.

Best,
Gerald


On 08.02.2013 00:26, Jose L Walteros wrote:
> Problem solved. I was not sure about the default cut generation
> strategy of SCIP. Indeed I am stopping the CG after the root is
> solved. Hence, no cuts. I know that generally generating cuts after
> branching some times reduces the solution efficiency due to the
> overhead of the separation algorithms and the extra rows, but I didn't
> know that SCIP shut it down almost completely. 
>
> Thanks a lot, you were really helpful
>
> -Jose
>
>
>
>
> On Thu, Feb 7, 2013 at 6:19 PM, Gerald Gamrath <gamrath at zib.de
> <mailto:gamrath at zib.de>> wrote:
>
>     Hi Jose,
>
>     when do you want to stop pricing and start cutting? When you are
>     still at the root node? In case you do it after you finished the
>     root node, the explanation is easy: per default, SCIP only
>     generates cutting planes at the root node, and even if you set the
>     separation to aggressive, separators will only be called every 20
>     depth levels. But you can change the frequencies of the separators
>     via the SCIP shell, you just have to change the freq parameters of
>     the separators. Perhaps this helps?
>
>     Best,
>     Gerald
>
>     Am 07.02.2013 22:29, schrieb Stefan Heinz:
>
>         Hi Jose,
>
>         can you send a statistic output of one run please.
>
>         Stefan
>
>
>         On 02/07/2013 07:56 PM, Jose L Walteros wrote:
>
>             Hi Stefan,
>
>             Yesterday I gave up with the pricer deactivation and tried
>             to continue
>             through the (*result= SCIP_SUCCESS) path.
>
>
>             This is the piece of the code I have:
>             if(nconsstree>EARLY_BRANCHING_LIMIT){
>             (*success) = TRUE;
>             for(s=0;s<n;s++)
>             {
>             for(i=0;i<m;i++)
>             {
>             SCIP_CALL( SCIPsetConsModifiable(scip, conss[s][i], FALSE) );
>             }
>             }
>             SCIP_CALL( SCIPsetSeparating(scip,
>             SCIP_PARAMSETTING_AGGRESSIVE, TRUE) );
>             return SCIP_OKAY;
>             }
>
>             I am positive that the constraints I am using are the
>             transformed ones
>             because those are the ones present in the pricer's data
>             structure and as
>             far as I know those have to be the transformed ones,
>             otherwise I would not
>             be able to update them with new columns.
>
>             To make sure they are the transformed ones I also tried:
>
>             SCIP_CONS* cons;
>             if(nnodes>EARLY_BRANCHING_LIMIT){
>             (*success) = TRUE;
>             for(s=0;s<n;s++)
>             {
>             for(i=0;i<m;i++)
>             {
>             SCIP_CALL( SCIPgetTransformedCons(scip, conss[s][i], &cons ));
>             SCIP_CALL( SCIPsetConsModifiable(scip, cons, FALSE) );
>             }
>             }
>             SCIP_CALL( SCIPsetSeparating(scip,
>             SCIP_PARAMSETTING_AGGRESSIVE, TRUE) );
>             return SCIP_OKAY;
>             }
>
>             but no cuts are generated. I am stuck here, I will
>             appreciate some help
>
>             Thank for your help
>
>
>             On Thu, Feb 7, 2013 at 5:32 AM, Stefan Heinz <heinz at zib.de
>             <mailto:heinz at zib.de>> wrote:
>
>                 Hi Jose,
>
>
>
>                 On 02/07/13 04:32, Jose L Walteros wrote:
>
>                     Hi Stefan,
>
>                     I was originally setting a flag inside of the
>                     pricer that acivates when
>                     the number of nodes was above a given threshold k.
>                     Then, once the flag was activated, I was calling:
>
>                     pricer = SCIPfindPricer(scip, PRICER_NAME);
>                     SCIP_CALL( SCIPdeactivatePricer(scip, pricer) );
>                     SCIP_CALL(SCIPrestartSolve(**scip) );
>
>                     for(s=0;s<n;s++)
>                     {
>                     for(i=0;i<m;i++)
>                     {
>                     SCIP_CALL( SCIPsetConsModifiable(scip,
>                     conss[s][i], FALSE) );
>                     }
>                     }
>                     SCIP_CALL( SCIPsetSeparating(scip,
>                     SCIP_PARAMSETTING_AGGRESSIVE, TRUE) );
>
>
>                     I was getting the following error, which I thought
>                     i was because the call
>                     was inside the pricer:
>                     cannot call method <SCIPdeactivatePricer> in
>                     solving stage
>
>                 Instead of deactivation the pricer, just return within
>                 your pricer without
>                 doing anything and pretend that all columns/variables
>                 are generated
>                 (*result = SCIP_SUCCESS). If you are not pretending
>                 that all
>                 columns/variables are there and force an early
>                 branching, then the LP is
>                 officially not solved to optimality. Meaning that all
>                 separators are not
>                 starting since they need an optimal basis.
>
>
>
>
>                     Then, What I tried to do then was to code an event
>                     handler that catches
>                     and SCIP_EVENTTYPE_NODEFOCUSED
>
>                     and then deactivates the pricer. Unfortunately,
>                     I'm still getting the
>                     same error.
>
>                     I checked the reference file and it seems that
>                     deactivate pricer can only
>                     be called in the stages:
>                     SCIP_STAGE_PROBLEM
>                     SCIP_STAGE_EXITSOLVE
>
>
>                     Also, If I just use in the event handler:
>
>                     for(s=0;s<n;s++)
>                     {
>                     for(i=0;i<m;i++)
>                     {
>                     SCIP_CALL( SCIPsetConsModifiable(scip,
>                     conss[s][i], FALSE) );
>                     }
>                     }
>                     SCIP_CALL( SCIPsetSeparating(scip,
>                     SCIP_PARAMSETTING_AGGRESSIVE, TRUE) );
>
>                 Regarding the modifiable flag. Please make sure that
>                 you change the flags
>                 of the transformed constraints and not of the original
>                 once.
>
>                 Best Stefan
>
>                     It does not generate any cuts.
>
>                     Thanks for your help
>
>                     -Jose
>
>
>                     On Wed, Feb 6, 2013 at 6:31 PM, Stefan Heinz
>                     <heinz at zib.de <mailto:heinz at zib.de> <mailto:
>                     heinz at zib.de <mailto:heinz at zib.de>>> wrote:
>
>                           Hi Jose,
>
>
>                           On 02/07/2013 12:20 AM, Jose L Walteros wrote:
>
>                               Hi Stefan,
>
>                               Thanks for your quick response,  I
>                     changed the code as you
>                               suggested (I am
>                               also changing some other parameters and
>                     I guess I confused the
>                               TRUE
>                               parameter as the way to do it, thanks
>                     for the clarification)
>                               but still no
>                               additional cut are generated.
>
>                               I am using now:
>
>                               SCIP_CALL( SCIPsetSeparating(scip,
>                               SCIP_PARAMSETTING_AGGRESSIVE, TRUE) );
>
>                               I also tried the default.
>
>                               For this formulation all the constraints
>                     of the master problem
>                               are Set
>                               Partitioning constraints defined as:
>
>                               SCIP_CALL(
>                     SCIPcreateConsBasicSetpart(**scip, &(conss[s][i]),
>                               name, 0, NULL)
>                               );
>                               SCIP_CALL( SCIPsetConsModifiable(scip,
>                     conss[s][i], TRUE) );
>
>                           One think, if you stop generating new
>                     variables completely, you
>                           should change the "modifiable" flag of the
>                     constraints to FALSE.
>                           Additionally you could turn off your
>                     pricer(s) and force a
>                           restart. That would run presolving for
>                     example again. Check the
>                           method SCIPrestartSolve():
>
>                           http://scip.zib.de/doc/html/**scip_8h.shtml#**
>                     a08e665c374c599f96c4968ce8cf10**8ba<http://scip.zib.de/doc/html/scip_8h.shtml#a08e665c374c599f96c4968ce8cf108ba>
>
>                           I am not sure but the modifiable issue can
>                     be the/a reason for not
>                           executing the separation. Try it and if does
>                     not work, I will
>                           check the code (during the day tomorrow).
>
>                           Best and good night Stefan
>
>
>
>                               I know  that no separators are called
>                     because in the execution
>                               summary the
>                               number of calls to all separators is zero.
>
>                               Is there anything I am missing?
>
>                               Thanks
>
>                               -Jose
>
>
>
>
>
>
>                               On Wed, Feb 6, 2013 at 5:53 PM, Stefan
>                     Heinz <heinz at zib.de <mailto:heinz at zib.de>
>                               <mailto:heinz at zib.de
>                     <mailto:heinz at zib.de>>> wrote:
>
>                                   Hi Jose,
>
>                                   It should be possible to turn on the
>                     separation. The bool
>                                   parameter you
>                                   changed from TRUE to FALSE has
>                     nothing to with turning on
>                                   or off the "OFF"
>                                   mode.
>
>                                  
>                     http://scip.zib.de/doc/html/****scip_8h.shtml#**<http://scip.zib.de/doc/html/**scip_8h.shtml#**>
>                                  
>                     af91abf95639f1bf2022c11d13a032****b10<http://scip.zib.de/doc/
>                     **html/scip_8h.shtml#**af91abf95639f1bf2022c11d13a032**b10<http://scip.zib.de/doc/html/scip_8h.shtml#af91abf95639f1bf2022c11d13a032b10>
>
>
>                                   It does the parameter change "quite"
>                     or not. Meaning with
>                                   or without an
>                                   output via the message handler. You
>                     need to change the
>                                   second parameter to
>                                   one of the followings:
>
>                                   * SCIP_PARAMSETTING_DEFAULT which
>                     are the default values
>                                   of all separating
>                                   parameters
>
>                                   * SCIP_PARAMSETTING_FAST such that
>                     the time spend for
>                                   separating is
>                                   decreased
>
>                                   * SCIP_PARAMSETTING_AGGRESSIVE such
>                     that the separating is
>                                   done more
>                                   aggregative
>
>                                   * SCIP_PARAMSETTING_OFF which turn
>                     off all separating
>
>                                   Probably you want to try
>                     SCIP_PARAMSETTING_DEFAULT first.
>
>                                   Best Stefan
>
>
>                                   On 02/06/2013 09:59 PM, Jose L
>                     Walteros wrote:
>
>                                       Hi all,
>
>                                       I am solving a problem via
>                     Branch and Price. For one
>                                       of my experiments, I
>                                       am interested in stopping the
>                     pricing at a certain
>                                       point in the B&B tree
>                                       to
>                                       heuristically obtain a good
>                     solution. Since I am no
>                                       longer pricing new
>                                       variables, I am wondering if it
>                     is possible to
>                                       activate the separate
>                                       algorithms to add default SCIP
>                     cutting planes after no
>                                       more columns are
>                                       generated.
>
>                                       I tried to play with SCIP_CALL(
>                     SCIPsetSeparating(scip,
>                                       SCIP_PARAMSETTING_OFF, TRUE) );
>                     changing it from TRUE
>                                       to FALSE but I did
>                                       not get the expected beheavior.
>
>                                       Tanks
>
>                                       -Jose
>
>
>
>                                      
>                     ______________________________****_________________
>                                       Scip mailing list
>                                       Scip at zib.de <mailto:Scip at zib.de>
>                     <mailto:Scip at zib.de <mailto:Scip at zib.de>>
>                                      
>                     http://listserv.zib.de/****mailman/listinfo/scip<http://listserv.zib.de/**mailman/listinfo/scip>
>                     <http://**listserv.zib.de/mailman/**listinfo/scip
>                     <http://listserv.zib.de/mailman/**listinfo/scip><http://listserv.zib.de/mailman/listinfo/scip>
>
>
>
>
>         _______________________________________________
>         Scip mailing list
>         Scip at zib.de <mailto:Scip at zib.de>
>         http://listserv.zib.de/mailman/listinfo/scip
>
>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20130208/fc0abf3c/attachment.html


More information about the Scip mailing list