[Scip] Postprocessing

[Gerald Gamrath]

Hi Mathieu,

we are currently thinking about modifying the propagation concept in a 
way that propagation can be performed also after the LP solving (and 
also without reoptimizing the LP).

Until then, you could try two things:
1) Do the postprocessing in a separator as you described, and add a 
method to your pricer to store that you just did postprocessing and the 
pricer does not need to search for improving variables, but can just set 
the result pointer to  SCIP_SUCCESS and return. Then, just the LP is 
solved again, which should not be very expensive.
2) You could try to implement a heuristic, that is called after the node 
(e.g. SCIP_HEURTIMING_AFTERLPNODE) and just does your bound tightening 
by calling SCIPchgVarUb(). In general, this could lead to wrong results, 
but in your special case, it should be possible, because the LP solution 
stays feasible and optimal.

Best,
Gerald and Michael

Am 24.05.2011 18:04, schrieb Mathieu Larose:
> Hi Gerald,
>
> The aim of my postprocessing is to reduce the upper bound of the non 
> basic variables which are at their lower bound. So the postprocessing 
> only affects the descendants of the current node.
>
>
> Regards,
> Mathieu
>
> On Tue, May 24, 2011 at 11:26 AM, Gerald Gamrath <gamrath at zib.de 
> <mailto:gamrath at zib.de>> wrote:
>
>     Hi Mathieu,
>
>     what is the aim of your postprocessing? In SCIP, the propagation
>     is done to get tighter bounds of the variables und thus
>     (hopefully) better dual bounds. Therefore, the LP is solved again
>     after bounds are reduced. If this would not be done, the LP
>     solution would also not necessarily be feasible for the current
>     subproblem.
>
>     Could you describe in detail why and how you want to do the
>     postprocessing?
>
>     Best,
>     Gerald
>
>     Am 22.05.2011 19:50, schrieb Mathieu Larose:
>>     Hi Timo,
>>
>>     I implemented a separator which does the bound strenghtening, but
>>     I don't see how it can act like a postprocessing procedure (i.e.
>>     called once after the price-and-cut loop).
>>
>>     The best I can do is to set the "priority" to a negative value,
>>     set "delayed" to true and do some tests whether it should run or
>>     not (taken from sepa_redcost.c lines 115-137).
>>
>>     So the separator acts almost like a postprocessing procedure. But
>>     if it is sucessful (i.e. the domain of at least one variable is
>>     reduced), another round of pricing and separation occurs which I
>>     do not want. How can I prevent this?
>>
>>
>>     Regards,
>>     Mathieu
>>
>>
>>     On Fri, May 20, 2011 at 3:07 AM, Timo Berthold <berthold at zib.de
>>     <mailto:berthold at zib.de>> wrote:
>>
>>         Hi Mathieu.
>>
>>         Bound strenghtening techniques are automatically applied in the
>>         propagation callbacks of certain constraint handlers (linear,
>>         knapsack,
>>         quadratic,...) which interacts with the price-and-cut loop of
>>         SCIP,
>>         basically in the following way: propagate->solve
>>         LP->price->cut->(if new
>>         vars or cuts found, start again). Also, reduced cost
>>         strengthening (which
>>         actually is a form of propagation/bound strenghtening) is
>>         applied only
>>         during the separation round. The reason is that this one
>>         first needs the
>>         LP to be solved to optimality.
>>         If you just use SCIP as a blackbox solver, I hope this
>>         answered your
>>         question.
>>
>>         If you like to set up your own domain propagation routine (node
>>         pre-processing), you will have to implement a propagation
>>         plugin (see How
>>         to add propagators in the Doxygen-Docs) or the propagation
>>         callback of a
>>         constraint handler (see How to add constraint handlers). If
>>         you need a
>>         solved LP for your method (hend it rather is a
>>         post-processing), you
>>         probably better implement a separator (How to..., see also
>>         src/scip/sepa_redcost.c) or the separation callbac of a
>>         constraint
>>         handler.
>>
>>
>>         Best regards,
>>         Timo
>>
>>         > Hello everybody,
>>         >
>>         > My apologies if this is obvious, but how can I do some
>>         postprocessing work
>>         > (bound strenghtening) after the price-and-cut loop has run?
>>         >
>>         >
>>         > Regards,
>>         >
>>         > Mathieu
>>         > _______________________________________________
>>         > Scip mailing list
>>         > Scip at zib.de <mailto:Scip at zib.de>
>>         > 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
>
>
>     _______________________________________________
>     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/20110614/89b4642a/attachment.html