[Freeciv-Dev] (PR#11156) prune CM branches by fitness

["Benoit Hudson" <bh@xxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=11156 >

> [jdorje - Tue Nov 23 08:06:29 2004]:
> 
> I found a bug causing maximum fitness to be too large. Fixing that makes
> things much faster (about 0.15s for "Boston").  However I think there
> may be another bug that I'm forgetting to account for the city center in
> init_min_production.  This would make things slower again.

Actually, it'd make things be incorrect: you'd prune things you
shouldn't prune, because now you risk being slightly below the true
upper bound.  I should make a patch that puts in the DP solver (clearing
the cache every time) and checks against it, for 'proof' that we get the
right solution.

> jason

Nice; I'd thought of pruning by fitness, then got worried it wasn't
sound, but your approach definitely is (except for missing the city
center; probably we should add another tile_type_vector in the search
state that has the list of free tiles, so that we don't have to think
too hard about the city center every time we make a change).  Certainly
it makes the "best" solution more than window-dressing now.

I think your code should go into a separate function:
compute_fitness_upper_bound.  This would separate the two reasons for
pruning:
- prune because some stat is underproduced (can't possibly meet the
requirements)
- prune because we can't beat the best found so far (can't possibly
improve the objective function)

I'm confused as to how max_fitness and estimated_fitness differ.  Are
they equal up to rounding?  We could probably merge the two; also, that
would allow us to merge lattice and lattice_by_max_fitness.

For a tighter bound, you can enforce lexicographic order and prerequisites.

For an even tighter bound, maybe we should just give up and implement an
LP solver and solve the LP relaxation of our problem.  That would tell us:
- an fairly tight upper bound on fitness
- a stricter check on satisfiability of the constraints (currently, if
we can fill either food or shields, but not both, we don't prune.  The
LP might be able to prune.)