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

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

Benoit Hudson wrote:
> <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.

Well, that went without saying ;-).  But in my test case it did work, so 
the only effect of the bug would be making things artifically fast.

City center is accounted for in food and shields I think but not in trade.

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

We were going to rename is_city_center as is_free_city_center.  In 
theory the city center may not always be free.

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

OK...

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

Well, I basically cloned estimate_fitness and changed it to handle 
rounding better.  Estimate_fitness contains a WAG fudge-factor to give a 
bonus to luxury.

Then I found I needed minimum_fitness and did the same thing again.  The 
three functions should all be merged IMO.

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

Interesting.  Is there an LP library we can use?

jason