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

[Gerald Gamrath]

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
>>>
>>
>