[Coin-symphony] tracking cuts

[Michael Hennebry]

On Wed, 29 Jun 2005, Ted Ralphs wrote:

> 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.

'Tain't tolerance.
I have 0-1 variables and all-integer constraint data.
user_is_feasible can be broadminded about what constitutes an integer.
It can calculate a bound on how close to integer the variables have
to be to ensure that rounding to exact integers will preserve
constraint satisfaction.
If they're not close enough, the solution is declared infeasible.
If they are close enough, the rounded solution might be a new improved
solution (IP_HEUR_FEASIBLE) or not (IP_INFEASIBLE).
In either case, user_is_feasible can find a cut that will remove
the rounded and fractional solutions from further consideration.

One problem turned out to be that user_is_feasible was finding a cut
and user_find_cuts wasn't always adding them.
Fixing that cured the repetitive solution problem,
though the previous behaviour still seems mysterious.

Cuts are still being rediscovered though.
I think that they are in different nodes.
There are output lines like:
Cuts in the local pool: 22

I want is to set parameters so that a
rediscovered cut is proof of an error somewhere.

I've been calling cg_add_explicit_cut with send_to_cp=true.

parameters:
time_limit 2400
touches_until_deletion 100000000
verbosity 11
ineffective_constraints 0

> 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

Is there a way to do that with cg_add_explicit_cut?

-- 
Mike   hennebry at web.cs.ndsu.NoDak.edu
"There are three kinds of people,
those who can count and those who can't."