[SCIP] How to freely tune between pricing and cutting ?
Alexandre Dupont-Bouillard
dupont-bouillard at lipn.univ-paris13.fr
Fri Dec 31 11:28:44 CET 2021
Dear Tobias
Thank you your interesting remark.
Unfortunately, our problem does'nt happen after a separation iteration
but after a pricing iteration (our separator is not called). Within a
few word, our question is "how to obtain a price-and-cut loop where
there is always a separation iteration after a pricing iteration".
Regards,
Pierre and Alexandre
Le 2021-12-23 16:09, Alexandre Dupont-Bouillard a écrit :
> 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
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
More information about the Scip
mailing list