Discrete Allocation

Allocation functions Discrete Allocation

definition

Discrete allocation is the assignment of each land unit (usually a grid cell) to exactly one land use type out of a limited set of competing types, such that the total suitability of the resulting land use pattern is maximized while regional minimum and maximum claims per land use type are respected.

This optimization problem is a variant of the Hitchcock transportation problem, see Tokuyama, T. and Nakano, J. (1995) Efficient algorithms for the Hitchcock transportation problem. SIAM Journal on Computing 24(3): 563-578. Its application to land use modelling is described in Koomen, E., Hilferink, M. and Borsboom-van Beurden, J. (2011) Introducing Land Use Scanner, paragraph 1.3.3.

In the GeoDMS, discrete allocation is performed by the discrete_alloc function and its variants, see Allocation functions. A worked-out configuration can be found in the Discrete Allocation Example.

the allocation problem

The problem is defined by:

• a domain unit of land units, the units of land (usually grid cells) to be allocated;
• a suitability map for each land use type: an attribute that expresses, for each land unit, the (economic or policy driven) value that the land use type attaches to that land unit;
• one or more partitionings of the land units into claim regions, for instance provinces or municipalities. Each land use type relates to one partitioning; the overlap of the different partitionings defines the set of atomic regions;
• claims: for each land use type, the minimum and maximum number of land units that should be allocated to that type within each region of its partitioning.

The result is a land use attribute that assigns one land use type to each land unit, accompanied by the realized number of allocated land units and a shadow price per claim, a status flag that indicates whether the allocation is feasible, and the resulting bid price per land unit.

optimality and feasibility

A solution is a feasible assignment, an assignment that violates no claim, with maximum total suitability: no other feasible assignment exists with a higher total suitability.

Such a solution is characterized by a shadow price for each claim, such that allocating each land unit to the type with the highest augmented suitability (its suitability plus the shadow price of the related claim) meets all claim constraints. Shadow prices are raised for claims whose minimum is not yet met and lowered for claims whose maximum is exceeded; they can be interpreted as the market clearing correction on land prices that regional restrictions would cause.

Whether a feasible assignment exists at all can be tested beforehand by the FeasibilityTest, which checks the claims against the number of land units per atomic region. A minimum suitability threshold can exclude land use types from land units with a lower suitability; a strict threshold can turn a problem that passed the FeasibilityTest into one with only an Infeasible Solution. If no feasible assignment exists, the discrete_alloc function reports which claims were violated.

algorithm

The GeoDMS implementation finds the shadow prices by sampling and scaling: it starts from a downscaled version of the problem and, during each scale up, adjusts the prices where claims are violated, using priority queues of the cheapest reallocation options between pairs of claims. This makes the expected time complexity O(n * k) for n land units and k claims. Equal suitabilities are resolved deterministically by virtual perturbation. See the discussion in discrete_alloc for a more detailed description, and Algorithmic techniques for other techniques used in the GeoDMS.

see also

• function reference: discrete_alloc and the overview of Allocation functions
• configuration example: Discrete Allocation Example
• AtomicRegions
• FeasibilityTest
• Tile By Tile Heuristic for allocation problems larger than what fits in memory