[Scip] LP solution status SCIP_LPSOLSTAT_OBJLIMIT

[Gerald Gamrath]

Hi Grit,

you are right, in a branch-and-price algorithm, you cannot cut off a 
node if the objective limit is reached by the LP solver, but you have to 
perform pricing. However, the solution limit was reached while solving 
the LP with the dual simplex, so the current dual solution is feasible 
(while the primal solution is in general not). If you use the current 
dual solution to perform pricing, this gives you a correct algorithm, 
since you need to cut off the current dual solution by adding a variable 
to the primal problem (otherwise, the dual feasible solution gives a 
lower bound for the optimal LP value, and if you cannot cut it off, your 
LP value exceeds the primal bound and the node can indeed be cut off).

Best,
Gerald

Am 16.07.2012 14:20, schrieb Grit Claßen:
> Hello Stefan,
>
> in a Branch-and-Bound algorithm, I would agree with you. But in a
> Branch-and-Price algorithm, the LP solution can decrease in a node when
> more variables are added. Anyway, a node with LP solution infinity in
> one step of the pricing routine is not cut off in my program.
>
> Best,
> Grit
>
> On 07/16/2012 12:30 PM, Stefan Vigerske wrote:
>> Hi,
>>
>> SCIP itself sets the objective limit for the LP to the best known
>> primal bound. That way, solving an LP can be stopped when it is clear
>> that it would have an optimal solution that is worse than the best
>> known solution, in which case the node can be cutoff.
>>
>> Stefan
>>
>> On 07/16/2012 11:55 AM, Grit Claßen wrote:
>>> Hello,
>>>
>>> during my Branch-and-Price algorithm I would like to use the current LP
>>> solution for the calculation of a lower bound. Though, I observed that
>>> the LP solution is sporadically set to infinity. In these cases, the LP
>>> solution status is "SCIP_LPSOLSTAT_OBJLIMIT". Searching the SCIP code, I
>>> realized that the LP solution is set to infinity as soon as the LP
>>> solution exceeds the objective limit. However, I do not set a limit on
>>> the objective value. This is why I do not understand the LP solution
>>> status.
>>>
>>> Can anyone explain what is going on here?
>>>
>>> Thanks and best wishes,
>>> Grit
>>>