[Coin-symphony] tracking cuts

[Ted Ralphs]

Michael Hennebry wrote:
> My Symphony-derived solver keeps
> finding the same cuts over and over.
> 
> I check to see whether each generated cut
> violates the current fractional solution.
> It does.
> Old fractional solutions keep coming back.
> Sometimes I generate the same cut even
> with a different fractional solution.
> Having generated a cut once, I shouldn't
> have to do it again.  Generating a cut
> should cut off any fractional solution
> that would cause its regeneration.

Hmmm, this is strange. In theory, it should not be possible to get the 
same fractional solution back again or to generate the same cut again 
with default settings, at least not during the processing of a single 
search tree node. The same cut could, of course, be generated in a 
different node. If the same solution comes back again, then the code 
would go into an infinite loop, at least until tailing off was detected. 
Is this what is happening? Without more information, it's difficult for 
me to guess what's going on, but I would say it sounds like tolerance 
issues. Perhaps violated cuts are somehow being removed erroneously 
because of inaccuracies in the LP solution.

I would suggest turning up the verbosity to 11 so that all status 
information is printed out every iteration and looking at exactly what 
is happening. You should be able to see what cuts are being marked 
ineffective and what cuts are being deleted, whether the lower bound is 
monotone, whether it is going into an infinite loop, etc. If you post 
the output for an example node where this happens, I should be able to 
help spot the problem. Also, please post exactly what parameters you are 
using. It is possible that changes in the parameters from defaults are 
contributing to the problem.

Another option is to change the criteria by which constraints are 
determined to be ineffective, i.e., deletable.

> Is there a way I can tell Symphony
> to not delete any cuts ever?

Yes, there are two options. If you want to turn off deletion of cuts 
universally, then set the parameter "ineffective_constraints" to 
NO_CONSTRAINT_IS_INEFFECTIVE (0). By default, it is set to 
BASIC_SLACKS_ARE_INEFFECTIVE. See

http://www.branchandcut.org/SYMPHONY/man/node257.html

You can also disallow deletion of any particular cut. In the cut_data 
data structure, there is a field "deletable." If this is set to FALSE 
when the cut is passed to SYMPHONY, then the cut will never be deleted. 
In fact, if you calloc the cut_data structure, then by default, the cut 
will never be deleted. See

http://www.branchandcut.org/SYMPHONY/man/node208.html

> Is there a way I can tell Symphony
> to check all its cuts whenever it
> checks cuts?

I'm not sure what you mean by this. It is possible to force all cuts 
into the global pool and then to tell SYMPHONY to check to global pool 
every time. This will effectively check every cut that has ever been 
generated every iteration. Is this what you mean?

> Is there a way for me to get an identifier
> when adding a cut so that I can later ask
> Symphony what it thinks that cut is?

I'm not sure what you mean by this either. SYMPHONY does assign a global 
index to cuts that are active in the final LP relaxation of a node 
before branching, i.e., when the final node description is passed back 
to the tree manager. However, this index probably won't help you, since 
I think you are interested in what is happening during the processing of 
a single node. Generally, SYMPHONY determines whether two cuts are 
identical using a comparison function that compares the coeff array and 
other fields. It should be possible to get a list of the cut 
descriptions for the cuts currently active and to do the comparison 
yourself. Is this what you're after? I would first play around with the 
parameters above and print out all the information you can. It should be 
fairly easy to see what's going on. Let me know what you find.

Cheers,

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