greedy_alloc - ObjectVision/GeoDMS GitHub Wiki

Allocation functions greedy_alloc

The greedy_alloc family performs land-use allocation by serving the highest bidders first: every land unit is ranked once by its best suitability, and the units are then given their best land-use type that still has claim capacity. It takes the same arguments as discrete_alloc but does not use shadow prices and never reallocates a land unit once it has been assigned.

Its sibling needy_alloc uses the same algorithm with a different ranking: by regret instead of by suitability. Neither regime uses the other, and neither uses discrete_alloc, as a preparation step — each is a complete algorithm on its own.

• greedy_alloc(arguments) - the same 11 arguments as discrete_alloc
• greedy_alloc_16(arguments)
• greedy_alloc_sp(arguments) - 8-argument variant (cf. discrete_alloc_sp)
• greedy_alloc_sp_16(arguments)
• greedy_alloc_np(arguments) - 6-argument variant (cf. discrete_alloc_np)
• greedy_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

See Allocation functions for the argument lists; they are identical to the discrete_alloc counterparts, including the Threshold and the (unused) FeasibleSolution container.

Ranking (once, before anything is allocated). For each land unit, the suitabilities that reach the Threshold are considered. greedy_alloc ranks the land units by the highest of those, so the unit with the highest bid anywhere is served first. Ties are broken by land unit index, which makes a run reproducible and independent of tiling. The ranking is not recomputed while allocating: a bid is what a land unit is worth, not a moving target.

Sweep 1 - reserving for the minimum claims. Skipped when every minimum claim is 0. In ranking order, each land unit is given the best type whose claim is still below its minimum. Land units that cannot help any deficient claim are left to sweep 2. Reserving first matters: after sweep 2 the attractive land units are spent and the minimums could only be met by taking back land units that are wanted elsewhere.

Sweep 2 - the rest, against the maximum claims. Every land unit still free, in ranking order, is given the best type whose claim is below its maximum. A land unit for which every admissible claim is already full stays unallocated; so does a land unit whose suitabilities are all below the Threshold. Both counts are reported in status.

Because each land use type belongs to exactly one partitioning, a (land unit, type) pair is constrained by exactly one claim, even when the partitionings overlap. Overlapping regions therefore never produce competing constraints on a single decision; they only determine which land units each claim can draw from.

The same structure as discrete_alloc, except that no shadow prices are reported:

• landuse: allocated land use type per land unit, null where nothing could be allocated
• status: text describing the result, including the realised total suitability and how many land units were left unallocated below the threshold resp. for lack of claim capacity
• statusFlag: True when all minimum and maximum claims are met
• total_allocated: count of allocated land units per type per region
• bid_price: the winning bid per land unit. Since these regimes have no shadow prices, this is simply the suitability of the allocated type - unlike discrete_alloc, where the shadow price is added to it.

There is no shadow_prices/<name>; referring to one is a "not found" error. Use discrete_alloc when shadow prices are needed.

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. In particular it never builds the O(#atomicRegions × k²) reallocation queues that discrete_alloc needs, which is where most of its constant factor sits.

greedy_alloc is a heuristic and does not maximise total suitability. The land units and the claims each form a partition matroid, and maximising total suitability over their intersection is exactly the problem that discrete_alloc solves exactly; a single-pass greedy over such an intersection can in the worst case reach only half of the optimum. In practice it comes much closer, but the outcome will differ from discrete_alloc and it must not be compared against a fixed expectation map.

Use greedy_alloc when:

• speed matters more than optimality
• the "highest bidder is served first" rule is itself the behaviour you want to model
• claims are not heavily constrained (in the extreme: all minimum claims 0, which skips sweep 1)

Use discrete_alloc when:

• the allocation has to be optimal
• shadow prices are needed for economic interpretation
• claims conflict and require a balanced resolution

• The values unit of SuitabilityMaps must be int32
• The sum of the MinClaims should not exceed the number of land units
• The sum of the MaxClaims should be at least the number of land units
• The domain of the claims must match the corresponding regions

An allocation that violates a claim is reported through statusFlag = False and status, not as an error. The feasibility test that runs before the allocation rejects claims with min > max, and also catches the case where the minimum claims are jointly unsatisfiable even though each of them looks attainable on its own - which overlapping partitionings can cause.

• needy_alloc - the same algorithm ranked by regret
• discrete_alloc
• discrete_alloc_np
• discrete_alloc_sp
• Allocation functions

5.50; the operator was unusable until 20.12.0 (it aborted right after solving, see issue 1171) and ran the discrete_alloc algorithm rather than a greedy one until the same release.