[SCIP] How to freely tune between pricing and cutting ?
Ambros Gleixner
gleixner at zib.de
Sun Dec 19 08:15:25 CET 2021
Dear Pierre and Alexandre,
I don't have a solution, but a quick idea for a possible workaround:
Instead of returning SCIP_DIDNOTRUN, can you add a dummy column with an
expensive objective coefficient such that it never appears in the LP?
This may not be the best solution for performance, but maybe it is not
too bad if it does not happen often. (In a second step, you could try
to make SCIP delete such columns at the the end of the node.)
Best,
Ambros
Am 17.12.21 um 16:46 schrieb Alexandre Dupont-Bouillard:
> Dear Steve and Gerald,
> Many thanks for the two ideas you give us to our question, and sorry for
> the false hope.
> Unfornately, either the two solutions or a mix of the two appears
> sometimes to raise a bug into SCIP.
> Our aim is still to freely decide to stop the pricing phase in order to
> add some inequalities before pricing convergence.
> The Steve's idea was to use SCIP_DITNOTRUN return value at the end of
> the pricing Callback.
> The Gerald's idea was to previously perform the separation algo within
> the pricing Callback in order to be sure to generate a cut in the next
> separator Callback: unfortunately, when no column is added in the
> pricing callback, the current relaxation is taken as a lower bound which
> induces bad decisions in the following.
> We tried to mix the two idea and we then use SCIP_DITNOTRUN with
> Gerald's idea.
> Unfortunately, as Eddie has noticed with his own code, for some
> instances, the use of SCIP_DITNOTRUN in the pricing Callback appears to
> stop the whole SCIP BCP process before convergence was reached.
> If someone wants to test our code, please find here a link to an
> instance which always fails. When SCIP stops, the convergence is not
> reached: this can be seen with our second code where all the columns and
> all the inequalities that have been produced in the first code, have
> been added till the beginning... and in that case SCIP doesn't stop!
> (but stops a few iteration later without reaching the convergence).
> We guess that using several SCIP_DITNOTRUN can raise a bug for some
> instance.
> Perhaps the case Eddie indicates correspond to the fact that
> SCIP_DITNOTRUN is not to be used when the solution to be priced is
> integral. Unfortunately the bug is reached for our code with a
> fractional value.
> If you wanna check what happends, there is our code
> : https://github.com/alexandredupontbouillard/B-C-P-coloring
> You can find in the readme explanations on how to reproduce the bug.
> Regards,
> Pierre and Alexandre
>
>
> Le 2021-11-24 21:23, Alexandre Dupont-Bouillard a écrit :
>
>> Dear Gerald,
>>
>>
>> It now works as we wanted, many thanks for your precious help.
>>
>>
>> Regards,
>>
>> Pierre and Alexandre
>>
>>
>> Le 2021-11-11 15:22, Gerald Gamrath a écrit :
>>
>> Hi Alexandre,
>>
>> what you could do to avoid changing the SCIP code would be to
>> check within your pricer if your separator will find cuts for the
>> current LP solution. For example, you could have an external
>> function that you can call from your pricer which returns whether
>> a cut can be generated. If that check may be expensive, you could
>> buffer the generated cut so that the separation call can directly
>> add that cut. I could imagine that having this close relation
>> between cutting and pricing implemented in your plugins could be
>> beneficial anyway, e.g., if you want to make the decision whether
>> or not to continue pricing depend on the strength of the cuts that
>> your separator would generate.
>>
>> Best,
>> Gerald
>>
>> Am 08.11.21 um 20:11 schrieb Alexandre Dupont-Bouillard:
>>
>> 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
>> <mailto: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
>> <mailto:scip-bounces at zib.de>> on behalf of Alexandre
>> Dupont-Bouillard
>> <dupont-bouillard at lipn.univ-paris13.fr
>> <mailto:dupont-bouillard at lipn.univ-paris13.fr>>
>> *Sent:*25 October 2021 09:54
>> *To:*scip at zib.de <mailto:scip at zib.de><scip at zib.de
>> <mailto: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 <mailto: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
>> <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 <mailto:Scip at zib.de>
>> https://listserv.zib.de/mailman/listinfo/scip
>> <https://listserv.zib.de/mailman/listinfo/scip>
>>
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de <mailto:Scip at zib.de>
>> https://listserv.zib.de/mailman/listinfo/scip
>> <https://listserv.zib.de/mailman/listinfo/scip>
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> https://listserv.zib.de/mailman/listinfo/scip
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de <mailto:Scip at zib.de>
>> https://listserv.zib.de/mailman/listinfo/scip
>> <https://listserv.zib.de/mailman/listinfo/scip>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>
More information about the Scip
mailing list