[SCIP] resolve without pricing first in price&cut loop

[Jens Leoff]

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