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

[Gerald Gamrath]

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
>