[freeciv-ai] (PR#6595) Optimize/reimplement CM

["Guest" <rt-guest@xxxxxxxxxxx>]

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

> [glip - Tir. 11. Nov. 2003 16:35:06]:
> 
> On Tue, 11 Nov 2003, Guest wrote:
> 
>> <URL: http://rt.freeciv.org/Ticket/Display.html?id=6595 >
>> 
>>> Gregory wrote:
>>> 
>>> This is right.  This is precisely the difference between integer and
>>> continuous linear programming: the best solution for 2 workers might
>>> be disjoint from the best solution for 1 worker
>>>
>>>   An example: 4 tiles available:  1f/0t, 5f/0t, 3f/3t, 0f/5t
>>>   condition: city doesn't starve + maximize trade
>>>
>>>   for 1 citizen 3f/3t tile is the best option
>>>   for 2 citizens 5f/0t + 0f/5t is the best
>>>
>>> so incrementing one citizen leads to a displacement of the first.
>> 
>> Actually, the best solution (since the food box can act as a buffer)
>> is to always use the 3f/3t tile and alternatingly using 5f/0t or
>> 0f/5t. Of course, this solution might not fit into what is currently
>> possible, but maybe it should?
> 
> Well spotted!
> 
> But I think the optimization task is hard as it is.
> 
> G.

Actually, if the implementation allows for such a solution, then the
optimization will be much easier. You could just solve the problem using
continuous linear programming, and then realize this solution by using
the food box as a buffer. The only case I can think where this is not
possible, is if one tile by itself produces more food than the food box
can contain, since the food box then cannot act as a buffer.

Of course, this approach blurs the difference between long-term and
short-term/immediate goals, but if the implementation allows for such
planning, it will at least result it better use of tiles. It will also
shorten the shorter execution time needed to find an 'optimal' solution,
since you don't need to consider integer programming, but instead you
have to keep a record of the planned tile usage and use time to update
the city tiles every turn (possibly). I don't know what the net effect
on execution time would be, but the idea will at least solve the
potensially very difficult integer programming problem.

JJ