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

[Jens Leoff]

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