[Cbc] Global cuts

[John Forrest]

Francois,

Explanations not guaranteed - but close to truth.

On Tue, 2011-02-22 at 13:54 -0500, Francois Margot wrote:
> Hi:
> 
> I am trying to understand the cut management mechanism in cbc,
> particularly for global cuts (i.e. OsiRowCuts with parameter
> setGloballyValid set to true when they are generated in a
> CglCutGenerator). I would like to know the following:
> 
> 1) If I generate a global cut at node k, is this cut present at all
> nodes that are generated after node k, or is it also present at all
> nodes that were generated before node k and are not yet processed?
> 

Yes - when a node is being evaluated all global cuts are scanned and
those violated (or if cut effectiveness is COIN_DBL_MAX) added in
temporarily to local cuts with generator number -1.

> 2) Can global cuts be removed by cbc as local cuts can be? If yes, is
> there a way to tell cbc not to remove some cuts?
> 

No - well not when added in to local cuts - can be removed in later
passes at that node (again I am fairly sure they will not be removed if
effectiveness COIN_DBL_MAX).

> 3)  If a global cut is generated at pass p at node k, is it present at
> pass > p at node k?
> 

See above

> 4) Finally, there seem to be a bug in the way active cuts are computed.
> At the end of the run, cbc prints a message
> 
>    generator was tried 4837 times and created 697 cuts of which 0 were
>    active after adding rounds of cuts
> 
> and no matter what cuts I generate (including cuts that force all nodes
> to be immediately pruned), the number of active cuts is always 0. 

There is one pool for global cuts with no way of telling how it was
generated.  So when added temporarily to local cuts, generator number is
-1 and it will not be added to counts.  It would be simple to have them
added to a "miscellaneous" cuts.

> As a
> side note, what is the definition of an "active" cut? A cut in the
> formulation? A cut whose dual variable is positive in the optimal basis?
> I understand that this is computed once per node, after the last pass of
> cutting. Is this also done for nodes pruned by infeasibility?
> 

An active cut is one whose slack is not in basis at end of evaluating
node.  I suspect there may be a bug when node is pruned.


> Francois
> 
> 
Hope that helps,

John