[Coin-symphony] tracking cuts

[Michael Hennebry]

On Thu, 7 Jul 2005, Ted Ralphs wrote:

> Michael Hennebry wrote:
>
> > '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.
>
> What do you mean by "removing the rounded solution from further
> consideration"? The rounded solution is feasible, right? How can it be
> cut off? If you are somehow cutting off the rounded solution and not the
> fractional solution, this could cause problems. All cuts must violate
> the current fractional solution or they will be discarded.

The idea is to cut off the fractional solution
that rounds to a nearby integer solution.
The assumption is the a heuristic solution from
user_is_feasible is not checked against any constraints.
The definition of "nearby" is narrow enough that a
cut the cuts off the rounded solution also cuts off
the fractional solution.

> > 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
>
> It's certainly possible to rediscover cuts in a different node. In fact,
> the purpose of the cut pool is to enable this to happen. Am I
> understanding you correctly?
>
> > I want is to set parameters so that a
> > rediscovered cut is proof of an error somewhere.
>
> I'm not sure I see why it would be if it is in a different node, unless
> it is a descendant.

Perhaps I should have written "regenerated".
user_is_feasible was being passed a fractional
solution that violated a previously generated cut.
user_is_feasible regenerated the cut and stored it in
the problem data structure for later use by user_find_cuts.

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