[Scip] LazyConstraints and Dual Bound

[michael.winkler@zib.de]

Hi Martin,

I want to add some more possibilities for you. The problem is, that even
after adding a global constraint or cut, the root LP is not solved again.
(And such a cut would, despite the fact of increasing your lowerbound,
also lead to bad pseudo costs.)

Even if you only would change the dual-/lowerbound of the root node, the
dual-/lowerbound of all children are not updated. ( So this does not help
either.)

For now, maybe a better idea should be to not add a cut but therefor
remember the implied dual-/lowerbound, which would be the result of your
cut. Then implement an event handler which catches the
SCIP_EVENTTYPE_BESTSOLFOUND event, see the examples/Eventhdlr/src
directory in the SCIP project (and
http://scip.zib.de/doc/html/EVENT.html).

If you then encounter a best solution you should check the cutoffbound
(SCIPgetCutoffbound) which was already corrected, against your
dual-/lowerbound.
(I don't know if you are allowed (and if it's possible) the get solutions
which are below your dual-/lowerbound. This you may need to handle.)

If SCIPisLE(scip, cutoffbound, lowerbound) (i.e. cutoffbound <= lowerbound)
you could cutoff the root node by calling SCIPcutoffNode(scip,
SCIPgetRootNode(scip)) or the developer version you could change the
dual-/lowerbound via SCIPupdateNodeDualbound()/SCIPupdateNodeLowerbound()
to your value which will also cutoff the given node.

Best, Michael

> 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
>>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>