needy_alloc

Allocation functions needy_alloc

The needy_alloc family performs land-use allocation by serving the neediest land units first: a land unit's rank is its regret, the difference between its best and its next best suitability, so the units that would lose the most by being denied their favourite type are settled first. It is the same algorithm as greedy_alloc with a different ranking key, and takes the same arguments as discrete_alloc.

Neither regime uses the other, and neither uses discrete_alloc, as a preparation step - each is a complete algorithm on its own. needy_alloc uses no shadow prices and never reallocates a land unit once it has been assigned.

syntax

• needy_alloc(arguments) - the same 11 arguments as discrete_alloc
• needy_alloc_16(arguments)
• needy_alloc_sp(arguments) - 8-argument variant (cf. discrete_alloc_sp)
• needy_alloc_sp_16(arguments)
• needy_alloc_np(arguments) - 6-argument variant (cf. discrete_alloc_np)
• needy_alloc_np_16(arguments)

Where:

• _16 suffix allows up to 65535 land use types (uint16) instead of 255 (uint8)
• _sp suffix is the single-partitioning variant
• _np suffix is the no-partitioning variant

definition

Ranking (once, before anything is allocated). For each land unit, take the suitabilities that reach the Threshold; let best be the highest of them and next the second highest. A land unit with only one admissible type has no alternative at all, and then next is the Threshold itself - the value at which allocating stops being worthwhile, so the natural stand-in for "this unit would go unallocated instead". The rank is

regret = best - next

and the land units are served in decreasing regret. Ties are broken by land unit index, so a run is reproducible and independent of tiling. The ranking is not recomputed while allocating.

The rest of the algorithm is identical to greedy_alloc: a first sweep reserves for the minimum claims (skipped when all minimum claims are 0), a second sweep allocates the remaining land units against the maximum claims, and each land unit takes the best type whose claim still has room.

why regret

Ranking by suitability serves the highest bidders first, which is easy to envision but spends scarce capacity on land units that would have been nearly as happy elsewhere. Ranking by regret settles the land units with an outspoken preference while there is still capacity to honour it, and leaves the indifferent land units - the ones that can go almost anywhere without much loss - to absorb whatever capacity remains. At the same cost, that usually yields a higher total suitability than greedy_alloc, though neither is optimal.

Result

Identical in structure to greedy_alloc: landuse, status, statusFlag, total_allocated and bid_price, and no shadow_prices/<name> members. Because these regimes have no shadow prices, bid_price is simply the suitability of the allocated type.

performance

O(n × k + n × log n) time and O(n) extra memory, with n the number of land units and k the number of land use types - the same as greedy_alloc, and without the O(#atomicRegions × k²) reallocation queues that discrete_alloc builds.

optimality

needy_alloc is a heuristic and does not maximise total suitability; see the optimality section of greedy_alloc for why a single-pass greedy over this problem can fall short of the optimum that discrete_alloc reaches exactly. Do not compare its result against a fixed expectation map.

see also

• greedy_alloc - the same algorithm ranked by suitability
• discrete_alloc
• Allocation functions

since version

20.12.0