[Coin-symphony] tracking cuts

[Ted Ralphs]

Michael Hennebry wrote:
> On Wed, 13 Jul 2005, Ted Ralphs wrote:
> 
> 
>>Yes, that is the idea of the global pool, but the pool is not checked
>>every iteration by default (this is configurable) and it is not checked
>>until after user_is_feasible() is called in the LP processing loop.
>>Furthermore, cut generation is still performed, even when the pool is
>>checked. For classes of inequalities for which there is an exact
>>separation algorithm (such as subtour constraints), this means that the
>>pool will not have any effect because any violated cuts previously
>>generated will be re-generated by the cut generation routines before
>>they are found in the pool. Generally speaking, one should not store
>>cuts that are "easy" to re-generate in the pool. In particular, this
>>includes any class for which there is efficient exact separation. For
>>classes that are difficult to separate or for which only heuristic
>>separation is possible, the pool will be much more effective. Hope this
>>helps. Let me know if you find out there really is a bug in there somewhere.
> 
> 
> As I understand the above, the sequence is
> check feasibility
> generate cuts
> fetch cuts from pool.

Yes, that's correct, but even if you fetched the cuts from the pool 
first, duplicates might still be generated sine there is really no way 
of preventing this from happening with the current implementation. I 
suppose an interesting experiment would be to fetch the cuts from the 
pool first and then not to generate cuts if any violated cuts were found 
in the pool. That would probably be easy to implement, at least in the 
sequential version. In the parallel version, cuts are fetched from the 
pool simultaneously with generation.

Ted
-- 
Dr. Ted Ralphs
Assistant Professor
Industrial and Systems Engineering
Lehigh University
(610)758-4784
tkralphs at lehigh.edu
www.lehigh.edu/~tkr2