[SCIP] resolve without pricing first in price&cut loop
Jens Leoff
jens.leoff at itwm.fraunhofer.de
Thu Dec 10 10:06:44 CET 2015
Hi Gerald,
thank you for clarification. Everything seems to work out, however
results were not as good as expected.
I then changed my pricer to be called whenever the LP objective is
greater than the node dual bound, and I return SCIP_SUCCESS without
pricing if they are already equal (by duality the LP solution is already
optimal, it may just violate some further constraints).
This improved performance by a lot for me.
I still check if separation will find a violated constraint in the case
where I would otherwise price. I count how often this occurs and do up
to k consecutive early terminations before pricing is called again. This
further improves performance, albeit not by much.
I am a bit surprised that the pricer is even called if objective value
and dual bound agree, I had expected different default behaviour.
I only realized that this is the case because of my troubles in the
price&cut loop, but the same does happen for the pricing loop.
At least for me these pricing calls are unnecessary, is there in general
a case where they are needed?
Best
Jens
On 03.12.2015 15:41, Gerald Gamrath wrote:
> Hi Jens,
>
> what you need is an external method in your separator, which returns
> whether it will find a cut to separate the current LP solution (not
> whether one was created in the last round). Then, what happens is the
> following:
>
> 1) LP is solved with Pricing to optimality (-> I guess you want to
> solve the first LP at a node to optimality with pricing?)
> 2) The separator finds a violated constraint which is added to the
> formulation
> 3) LP is re-optimized
> 4) The pricer is called and calls the external method of the separator
> to check if the current LP solution will be separated anyway.
> a) The LP solution will be separated: the pricer returns
> SCIP_DIDNOTRUN, although there might be negative reduced cost
> variables which do not get added.
> b) If no cut will be added for the current LP solution: the pricer
> runs normally and tries to generate improving variables. If variables
> were added, we go to 3), otherwise, we continue to 5).
> 5) The separator is called again. If we were in case 4a) before, the
> LP solution did not change so a cut will be added and we will go to
> 3). If we were in case 4b), no cut can be added and we are done.
>
> Since we go into case 4a) only if we already know that a cut will be
> added in the following, we made sure that also pricing is called
> again. You should however be careful that the cut is really added (set
> the force flag to TRUE), and that the limit on the number of
> separation rounds is not hit (or check that as well in the external
> separator method).
>
> I hope this is clearer now. And I hope that it will really work. :-)
> Please tell us if you have further questions or any problems come up.
>
> Best,
> Gerald
>
> On 03.12.2015 14:41, Jens Leoff wrote:
>> Dear Jakob,
>>
>> I only now find time to try your proposed solutions.
>> I think ensuring that the pricer runs for infeasible LPs should be
>> okay, I just won't change anything for calls to pricer_farkas. Using
>> the result from separation to decide if the pricer can be called via
>> an external method is an easy to implement idea, thanks.
>> Following this approach I wonder if this is sufficient to ensure that
>> the LP's are solved optimally.
>> If I read the Price&Cut loop correctly, I expect the following:
>> 1) LP is solved with Pricing to optimality
>> 2) The separator finds a violated constraint which is added to the
>> formulation
>> 3) The pricer is called and returns SCIP_DIDNOTRUN, based on 2).
>> However there are negative reduced cost variables which do not get
>> added.
>> 4) LP is resolved, but is suboptimal.
>> 5) The separator is called again and does not find a violated
>> constraint.
>> 6) The Price&Cut loop is terminated early, we do not use the dual bound.
>>
>> If this is correct, do you have a suggestion how I could arrange for
>> the pricer to be called again after 5)?
>>
>> Best
>>
>> Jens
>>
>>
>>
>> On 23.10.2015 18:48, Jakob Witzig wrote:
>>> Hi Jens,
>>>
>>> your idea is not so easy to realize with SCIP.
>>>
>>> A possible way could be to do not price variables and to return
>>> SCIP_DIDNOTRUN. The problem is, that every time cuts are added to
>>> the LP your prices will be called. That means you have to decide
>>> within your pricer whether you want to price or not. Moreover, you
>>> have to ensure that your pricer runs if the LP is infeasible.
>>>
>>> Another possible solution could be to extend your separation method
>>> with an external method that returns whether cut were added to the
>>> LP or not. Afterwards, based of the return value of the method your
>>> pricer can decide if new variables are needed.
>>>
>>> Best,
>>> Jakob
>>>
>>>
>>> On 20.10.2015 09:48, Jens Leoff wrote:
>>>> Hi,
>>>>
>>>> I have a Branch, Price & Cut algorithm and in some cases I observe
>>>> the following behaviour:
>>>> When solving the LP for some node I end up in a loop where
>>>>
>>>> 1 violated constraint is found and added to the lp.
>>>> The LP is resolved with column generation, but no new variables are
>>>> found.
>>>>
>>>> As pricing takes a lot longer than separation in my case, solving
>>>> the lp takes very long.
>>>> Often no new variables are added in pricing, so I expect
>>>> considerable speed up when solving the Price & Cut loop the
>>>> following way:
>>>>
>>>> After separation the LP is solved without pricing and a new
>>>> separation round is started.
>>>> Only if the lower bound increased or no further violated
>>>> constraints are detected the lp is resolved with pricing.
>>>>
>>>> Is this currently possible with SCIP?
>>>>
>>>> Kind regards
>>>>
>>>> Jens Leoff
>>>>
>>>
>>
>
--
Jens Leoff
Fraunhofer-Institut für Techno- und Wirtschaftsmathematik ITWM
Fraunhofer-Platz 1, 67663 Kaiserslautern, Germany
Telefon: +49 (0)631 / 31600-4708
More information about the Scip
mailing list