[SCIP] How to freely tune between pricing and cutting ?
Alexandre Dupont-Bouillard
dupont-bouillard at lipn.univ-paris13.fr
Thu Dec 23 16:09:56 CET 2021
Dear Ambros,
We tried this solution but even if we return SCIP_DIDNOTRUN after adding
this dummy column, our separator is not called until no column is added.
Regards,
Pierre and Alexandre
Le 2021-12-19 08:15, Ambros Gleixner a écrit :
> 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
>>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
More information about the Scip
mailing list