[Scip] LazyConstraints and Dual Bound

[Kati Wolter]

Hi Martin,

for minimization problems, the global dual bound is defined as the minimum
dual bound of all open (unprocessed) nodes. A newly created node inherits
its initial local dual bound from the parent node. Later on, when the node
is processed and the LP relaxation is solved, the local dual bound is
updated w.r.t. to the LP solution. This way the children (if any) get a
higher initial local dual bound and this way the global dual bound may
improve.

If you are somewhere down in the tree and add your information to SCIP (as
GLOBAL constraint or row -- I did not really get this from your mail),
this will not automatically update the initial local dual bounds of all
open nodes. Only after the LP relaxation (with this new row) of a node is
solved, your information is processed locally. This means, you have to
wait until all nodes which were open when you added your information were
processed (i.e., their LP relaxations were solved).

In order to speed this up, you have to somehow touch all open nodes and
update their local dual bounds. You could try the following:

- access all open nodes ( SCIPgetLeaves(), SCIPgetChildren(), and
SCIPgetSiblings())
- update their dual bound (SCIPupdateNodeDualbound() or
SCIPupdateNodeLowerbound() depending on whether your value is valid for
the original or transformed problem)

But I'm not sure whether this is really a good idea. For example, the
local dual bounds are important for node selection and branching; so if
they are all equal, at least for a while, you have some information loss.


Best regards,
Kati



> Hallo
>
> I have the following problem. Lets say I have a mixed integer problem
> running and I am somewhere in the branch and bound tree. Suddenly I find a
> feasible constraint, limmiting my potential objective value (e.g. for a
> minimization problem: objective >= a). If I add this constraint (via a
> "lazy"-constraint-handler and ScipAddCut), all following solutions have an
> objective value bigger than a, but if I ask for SCIPgetDualbound, this
> value is still LOWER than a (It was not adapted?). Resulting, if a
> solution with objective value equal to a is found, the solution process
> does not terminate, because of the (lower than a) dualbound.
>
> What could I have done wrong? Or what could I do, sucht hat scip adapts
> it's dual bound if such constraints are added?
>
> Best regards
>
> Martin Tieves
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>