[SCIP] How to freely tune between pricing and cutting ?
Gerald Gamrath
gamrath at zib.de
Fri Dec 31 13:26:25 CET 2021
Dear Pierre and Alexandre,
how did you set the maxrounds parameter of your separator? It should be
at -1 to always call it. The global maxrounds should be at -1 as well.
The same for maxbounddist, that should be 1.0 for both your separator
and the global setting.
Finally, there is the maxstallrounds parameter, which you should
probably set to -1 as well in order to avoid that SCIP stops generating
cutting planes because the dual bound is not increasing after each round.
Best,
Gerald
On 12/31/21 11:28 AM, Alexandre Dupont-Bouillard wrote:
> 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
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
More information about the Scip
mailing list