[Scip] stop condition of pricing routine

[Gerald Gamrath]

Hi Mattia,

since Version 1.2, SCIP supports the early termination of the pricing
process (or "early branching"). That means, the method defined by
SCIP_DECL_PRICERREDCOST now has a result pointer, which should usually
be set to SCIP_SUCCESS (in case you found variables or were able to
prove, that no improving variable exists).
However, in case you want to stop pricing, you can set this pointer to
SCIP_DIDNOTRUN and return without adding new variables. Then SCIP knows
that the optimal objective function value of the current (restricted) LP
relaxation is no valid dual bound and does not update the dual bound of
the current node w.r.t. this value.
Besides, the SCIP_DECL_PRICERREDCOST callback now also has a SCIP_Real*
lowerbound pointer, so that you can define another valid dual bound, in
your case, for example, the value LB of the lagrangian relaxation. This
can be done in each call of the pricing callback, no matter what you set
the result pointer to.

To your other questions:

<1.- is there any way built-in in SCIP to easily manage the degenerancy
of a column-generation approach? In other words, is there a predefined
way to stabilize a generic CG problem?

No, unfortunately, there is no such built-in way.

<2.- if not, a possible solultion should be this: implement myself a
relaxator, which is called at each CG iteration. At this point, if dual
values provided by the LP relaxation at the current iteration are
outside the <trust region, penalty will be applied, so the relaxator
construct a quite NEW problem and find a new bound. Otherwise if dual
values are inside the trust region, no penalty will be applied. Another
probleme <arises: we have to guess the trust region at the beginning. It
may happen that no new variables (columns) are found by the slave
problem (min path) because we are too far from the trust region, and
thus <penalty terms are very high for the dual variables provided at the
current iteration. In this case, the relaxator have to notice that no
new columns have been found, but the trust region is moving (hopefully
<towards the right position), and thus optimize. It must not close the
node because no new columns have been found. It close the node only if
no new columns have been found and the trust region has not <changed
since last iteration (with an epsilon tolerance). How to do this in a
clean and hopefully efficient way?

This sounds like a good way to do this. One way would be to substitute
the LP relaxation by a relaxator plugin, that coordinates LP-solving,
column generation and the stabilization. Another way would be, as you
suggested, to copy the LP in the pricing callback, take care of the
trust region, resolve this modified LP and perform pricing w.r.t. the
dual variables of this LP. I think, this would be a smaller structural
change and less implementational effort. You would, however, need to
take care about the warmstart of the modified problem yourself.

I hope this helps. If you have any more questions about the realization
of the stabilization procedure, please pose them.

Best regards,
Gerald

Am 28.07.2010 11:07, schrieb Mattia Barbieri:
> Hi all,
>   I know that in the pricing process, in a Branch&Price Tree, at each
> node the pricing routine will stop if no variables with negative (min)
> reduced cost are found. What about if I want to stop the pricing (i.e.
> not calling again the slave procedure, SCIP_DECL_PRICERREDCOST) on my
> own conditions? In my case, at each node, I want to stop the pricing
> if  Z_RMP (the objective value of the relaxation, UB) is less than
> L(pi) (the value of the lagrangian relaxation, LB) plus epsilon. No
> matter if no negative reduced cost variables are found, because I am
> introducing a stabilizing scheme, so it is possible that new variables
> are found at the next iteration, when the trust region is updated.
>
>   Best regards
>
> -- 
> Mattia Barbieri
> barbieri.mattia at gmail.com <mailto:barbieri.mattia at gmail.com>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>   

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20100728/5de8fb37/attachment.html