Re: (PR#11509) a greedy CM

<URL: http://bugs.freeciv.org/Ticket/Display.html?id=11509 >

On Mon, Apr 11, 2005 at 09:33:03AM -0700, Jason Short wrote:
> <URL: http://bugs.freeciv.org/Ticket/Display.html?id=11509 >
> 1.  It's not truly greedy.  It doesn't take the first solution but the
> first satisfactory one (that meets the minimums).  Usually this makes no
> difference.

The usual term is the first "feasible" solution.

> 2.  My original patch was quite buggy because it did "return FALSE"
> instead of "return TRUE" causing the CM to simply lock up - oops.  

> Also it didn't work with CMA because CMA didn't use cm_init_parameter
> correctly.  This patch fixes both.

Can you make this a seperate patch & apply it?  I got bitten by this in
trying to get the 12736 stuff to work.


> 3.  I think these numbers show the B&B algorithm to be flexible enough
> to meet all of our needs.  Of course you AI guys should test this on
> your own.

This was in the original design in #10203 but I cut it out since it
complicated the patch, so I'm not too surprised it works well :)

The way I'd implemented it was to have the API be:
        - build the cm_state
        - repeatedly call cm_find_first_feasible until you
          find a parameter that has a feasible solution
        - destroy the cm_state and apply the cm_result.

I pretty much don't care whether the first-feasible / full-search
determination is done via API or parameter, but building the cm_state
only once in auto_arrange_workers is quite advantageous if we get the
search time down to where pre-processing starts to matter.

        -- Benoît