[Coin-symphony] heuristic solutions

[Michael Hennebry]

 On Tue, 26 Jul 2005, Ted Ralphs wrote:

> Michael Hennebry wrote:
> > Is there a mechanism other than user_is_feasible
> > for providing heuristic solutions?
>
> Not currently. What do you suggest?

I don't have one at the moment.
I'm still dealing with my rather tight coupling
between feasibility checking, heuristic generation,
and cut generation.

Currently under consideration:
Generate heuristic solution within cut generation code
and store it until it can be returned from user_is_feasible.

In user_is_feasible:

Check whether heuristic, if any, is better than incumbent, if any.
If not, remove heuristic.

Check whether heuristic, if any, would fathom current node.
If so, return heuristic.

Check whether fractional solution is integer enough.
If not, return heuristic, if any.

Round the fractional solution with little subtlety.
If rounded solution costs as much as the heuristic, if any,
return the heuristic.
If rounded solution is feasible, return rounded solution
else return heuristic, if any.

return infeasible

In cut generator:

try to generate cuts and heuristic, much subtlety is allowed
store heuristic, if any, in user data

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