[Scip] checking bounds to stop solving a node before ending column generation

[Alessia Violin]

Hello Gerald,

thanks a lot for your help, I was already multiplying the objective 
function value of newly generated variables by -1, but then I got a bit 
confused with the bounds of my original problem and the transformed one 
used by scip. Now it works!

Best,

Alessia


On 03/22/2013 02:48 PM, Gerald Gamrath wrote:
> Hi Alessia,
>
> in each pricing call, you can set the lowerbound pointer in the
> pricerredcost callback to a valid lower bound which you computed. If
> this is higher than the node's current dual bound, it will be updated.
> However, I just noticed that pricing is not stopped in the current
> version of SCIP, because the lower bound is only updated after the
> complete pricing round. Thus, it was right to just create no new
> variables (and possibly also set the result-pointer to SCIP_DIDNOTRUN),
> so SCIP stops pricing. I corrected this in our development version, so
> in the next release, pricing will be stopped as soon as you provide a
> lower bound which is higher than the cutoff bound.
>
> I'm talking about lower bounds all the time although you have a
> maximization problem, where the dual bound is an upper bound. The reason
> for this is that the transformed problem on which the solving process is
> done is always a minimization problem (SCIP automatically converts a
> maximization problem into a minimization problem by multiplying the
> objective with -1). Therefore, all data you get from the LP corresponds
> to this minimization problem. In particular, you also need to multiply
> the objective function value newly generated variables by -1, see the
> warning in the documentation of SCIPcreateVar():
> http://scip.zib.de/doc/html/scip_8h.shtml#aadcc57e6efe08c07a23643d0e7fb3151
>
> If you can generate a lower bound for the optimum in the transformed
> space, you can check it against the upper bound in the transformed
> problem which you get by SCIPgetUpperbound() or the cutoffbound, which
> you get by SCIPgetCutoffbound()
> http://scip.zib.de/doc/html/scip_8h.shtml#a348c2e9e1c59b4664b128b79ba0cca92
> http://scip.zib.de/doc/html/scip_8h.shtml#ab87340eb66d6fddb826bf07bf4a650ec
>
> Note that SCIPgetLowerbound() and SCIPgetUpperbound() do the same as
> SCIPgetDualbound() and SCIPgetPrimalbound(), but with respect to the
> transformed problem space.
>
> You can convert an objective value from the original to the transformed
> space and vice versa by SCIPtransformObj() and SCIPretransformObj(),
> respectively:
> http://scip.zib.de/doc/html/scip_8h.shtml#a5a61c75e77b23d6c459bc78d513cb41d
>
> So I guess you did not get the correct solution at the end because you
> computed a lower bound in the transformed space and this being smaller
> than the primal bound did not mean that you can cutoff the current node.
>
> Best,
> Gerald
>
> On 21.03.2013 14:28, Alessia Violin wrote:
>> Hello,
>>
>> I am solving a maximization problem with branch&price, and for the
>> moment I am able to solve it correctly.
>>
>> Now I am trying to add the following: if when solving a certain node
>> with column generation, the current dual bound (that I calculate with
>> dual variables and reduced cost values) on the node solution becomes
>> smaller than the current best known integer solution (global primal
>> bound) I might directly stop solving this node (without finishing the
>> column generation), as I am sure there will not be good integer solution
>> for it or the subtree from it.
>>
>> How do I implement this? I tried just not generating columns when this
>> happens, the node solving is stopped but I don't get the correct optimal
>> solution at the end.
>>
>> Do I need to tell scip something more (cut the node, update bounds, ...)?
>>
>> I hope my question is clear, if not I can try to give more details.
>>
>> Thanks in advance for any help,
>>
>> Alessia
>>

-- 
Alessia Violin
Service Graphes et Optimisation Mathématique (G.O.M.)
Université Libre de Bruxelles
C.P. 210/01
Boulevard du Triomphe
B-1050 BRUXELLES
Tel: 02 650 58 80 - Fax: 02 650 59 70
Email: aviolin at ulb.ac.be
Webpage: http://homepages.ulb.ac.be/~aviolin/