[SCIP] How to freely tune between pricing and cutting ?

Mon Nov 8 20:11:53 CET 2021

Dear Steve

Many thanks for your answer.
The question of free alternation between cut and price seems to be a new
strategy since it's not classical for SCIP!

Unfortunately, as said by Edward, your proposal seems not to work.
Indeed, setting the result as SCIP_DIDNOTRUN in PRICERREDCOST callback
appears to exactly work as artificially saying that no column is
produced.

This brings the problem you point out: no pricing round is launched
after a cutting
round with no generated cut.
This a problem for us because the previous pricing round has been
artificially
inhibit in order to launch a cutting phase.
Indeed, when there is no generated cut in a cutting round, a
supplementary exact
pricing round is needed to assert convergence (and potentially to go on
with the
price&cut process).

A solution appears  to turn off the test stopping the price&cut process
when no cut have been generated during a cutting round
With such a deleted test, the price&cut iterations will have no end
since
the cutting and pricing rounds will call each other in a never ending
loop.
A way to stop this loop is to add a test having the memory of the
previous round
in order to stop when two successive non-inhibited price and cut rounds
have produced
nothing. 

Regards,
Pierre and Alexandre

Ps: Another disturbing problem for us was that a cutting round is
launched only
if the current solution is not integer: this is a problem for us because
an integer
solution can appear (before convergence) right after a pricing round.
In this case, it is mandatory for us to do a second pricing round, even
if our strategy
is to alternate with a cutting round (our cutting procedure cannot
produce cuts for integral solutions).
We add a test at the beginning of the PRICERREDCOST callback for
no-inhibiting the pricing
when the current solution is integer.

Le 2021-11-08 11:25, Edward Lam a écrit :

> I have tried this. It sounds like this would work according to the documentation but this does not work. Sometimes it skips pricing and separation and goes straight to branching. I guess branching is technically okay if the master problem is fractional but sometimes its integral and gets messy quickly.
> 
> Cheers
> Eddie 
> 
>> On 8 Nov 2021, at 7:10 pm, Maher, Stephen <S.J.Maher at exeter.ac.uk> wrote: 
>> 
>> Hi Alexandre, 
>> 
>> Sorry about the delay in response to this question. This happens to be a question that we have not encountered before, so we needed to work out how to actually achieve this. 
>> 
>> I am not sure whether this would work, since I don't have an example to test with. I believe that by setting the result in your PRICERREDCOST callback to SCIP_DIDNOTRUN, you will terminate pricing and then continue with the rest of the node processing. The separation round will begin after you terminate the pricing round. 
>> 
>> There are two things to note here. The first is that if you add a cut, then the node processing will enter back into pricing. So you may want to keep returning the result of SCIP_DIDNOTRUN from your pricer while you want to keep generating cuts. The second is that if you don't add a cut during the separation round, then you will not enter back into the pricing round. So you must ensure that you have completely finished pricing before the final separation round. 
>> 
>> Since this is untested, please let us know if it works for your setting. If not, then we can think of a different approach. 
>> 
>> Cheers, 
>> 
>> Steve 
>> 
>> -------------------------
>> 
>> FROM: Scip <scip-bounces at zib.de> on behalf of Alexandre Dupont-Bouillard <dupont-bouillard at lipn.univ-paris13.fr>
>> SENT: 25 October 2021 09:54
>> TO: scip at zib.de <scip at zib.de>
>> SUBJECT: [SCIP] How to freely tune between pricing and cutting ? 
>> 
>> CAUTION: This email originated from outside of the organisation. Do not click links or open attachments unless you recognise the sender and know the content is safe.
>> 
>> Hi
>> 
>> We try to build a BCP method where cuts are added through a separator.
>> We would like to have a free hand on the alternation between pricing and
>> cutting phases.
>> 
>> We haven't found how to add parameters to choose for instance to begin
>> by a cutting phase
>> or to stop pricing before convergence to add some inequalities and come
>> back to pricing
>> and so on...
>> 
>> The best would be to be able to switch from cutting to pricing (and from
>> pricing to cutting) using a test done by an algorithm.
>> 
>> Does someone know how to perform such alternation?
>> 
>> Thanks
>> Pierre and Alexandre
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Flistserv.zib.de%2Fmailman%2Flistinfo%2Fscip&data=04%7C01%7CS.J.Maher%40exeter.ac.uk%7Ce1f9ee8f46304091c1a308d99796bbb3%7C912a5d77fb984eeeaf321334d8f04a53%7C0%7C0%7C637707496323265507%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=BjaINZ3HZglnha70BFGyyDMOEtBY9ygHd9Nz%2F6VsGGM%3D&reserved=0 _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> https://listserv.zib.de/mailman/listinfo/scip
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20211108/b2e2e8ba/attachment.html>