Discrete Allocation
Discrete allocation is the allocation of resources (e.g. land units) to a set of categories (e.g. land use types) based on the suitability of each resource for each category and restrictions on the number of resources that should be allocated to a category. Discussed here is the allocation that maximises total suitability by offsetting relative suitability differences; this is in contrast with step-by-step allocation where a strict order of land use categories or allocation priorities is defined, or a sorted allocation according to transition potentials that operates as a greedy highest values first allocation that doesn't take alternatives and their opportunity costs into account.
the following text comes from Koomen & Borsboom-van Beurden (2011)
The algorithm finds the optimal allocation of land use for the given specified demand and definition of suitability. This new approach is referred to as the discrete model as it uses a discrete description of land use per cell: each cell is assigned only one type of land use from the total range of possible land-use types. Nowadays, the Land Use Scanner model has a flexible structure that allows for the selection of five different resolutions, ranging from 100 to 10,000 m, as well as the choice of using the discrete or continuous model, thus providing a total of 10 basic model variations. The discrete allocation model allocates equal units of land (cells) to those types of land use that have the highest suitability, taking into account regional land-use demand. This discrete allocation problem is solved through linear programming, which is considered optimal when the sum of all suitability values corresponding to the allocated land use is maximal. The allocation is subject to the following constraints:
- the amount of land allocated to a cell cannot be negative;
- in total, only 1 ha can be allocated to a cell;
- the total amount of land allocated to a specific land-use type in a region should be between the minimum and maximum claim for that region.
Mathematically, the allocation problem can be formulated as follows:
$\max \sum\limits_{ij}{X_{ij} S_{ij}}$
subject to:
-
$X_{ij} \ge 0$ for each$i$ and$j$ ; -
$\sum\limits_{j}{X_{ij}} = 1$ for each$c$ ; -
$L_jr \le \sum\limits_{i}{X_{ij}} \le H_jr$ for each$j$ and$r$ for which claims are specified;
in which:
-
$X_{ij}$ is the amount of land allocated to cell$i$ to be used for land-use type$j$ ; -
$S_{ij}$ is the suitability of cell$i$ for land-use type$j$ ; -
$L_jr$ is the minimum claim for land-use type$j$ in region$r$ ; and -
$H_jr$ is the maximum claim for land-use type$j$ in region$r$ .
The regions for which the claims are specified may partially overlap, but for each land-use type
The problem at hand is comparable to the well-known Hitchcock transportation problem that is common in transport-cost minimisation and, more specifically, the semi-assignment problem (Schrijver, 2003; Volgenant, 1996). The objective of the former problem is to find the optimal distribution in terms of minimised distribution costs of units of different homogenous goods from a set of origins to a set of destinations under constraints of a limited supply of goods, a fixed demand, and fixed transportation costs per unit for each origin-destination pair. The semi-assignment problem has the additional characteristic that all origin capacities are integers and that the demand for each destination is one unit of a specific homogenous good. Both are special cases of linear programming problems. The discrete allocation algorithm has two additional characteristics that are not incorporated in the mathematical formulation of the classical semi-assignment problem: (1) several (partially) overlapping regions are specified for the claims (although the regions of claims for the same land-use type may not overlap), and (2) it is possible to apply distinct minimum and maximum claims.
This mathematical problem, with its very large number of variables, calls for a specific, efficient algorithm. A scaling procedure is applied to improve the efficiency, and a threshold value is used. Scaling means that growing samples of cells are used in an iterative optimisation process that has proven to be fast (Tokuyama & Nakano, 1995). An optimisation is performed for each sample. After each optimisation, the sample is enlarged, and the shadow prices in the optimisation process are updated in such a way that the (downscaled) regional constraints continue to be met. To limit the number of alternatives under consideration, a threshold value is used: only potentially optimal allocation choices are placed in the priority queues for each competing claim. An important advantage of the algorithm is that it enables an exact solution to be found with a desktop PC (Pentium IV-2.8 GHz, 1 GB internal memory) within several minutes, provided that feasible solutions exist and all suitability maps have been prepared in an initial run of the model. Running the model for the first time takes just over an hour, as all base data layers have to be constructed. These data sets are then stored in the application files (in a temporary folder) to speed up further calculation.
The constraints that are applied in the new discrete allocation model are equal to the demand and supply balancing factors applied in the original, continuous version of the model. In fact, all the extensions to the original continuous model related to the fixed location of certain land-use types, the use of regional claims, the incorporation of minimum/maximum claims, and the monetary scaling of the suitability maps also apply to the discrete model. Similar to the original model, the applied optimisation algorithm of the discrete model aims to find shadow prices for the regional demand constraints that increase or decrease the suitability values, such that the allocation based on the adjusted suitability values corresponds to the regional claims. The main difference between the discrete and continuous models is that each cell only has one land-use type allocated, meaning that the share of allocated land is zero or one for each land-use type. From a theoretical perspective, the models are, however, equivalent if the scaling parameter that defines the importance of the suitability values becomes infinitely large. In that case, the continuous model would also strictly follow the definition of suitability in the allocation and produce homogenous cells. This procedure is, however, theoretical and cannot be applied in the calculations due to computational limitations. A more extensive discussion of the two available algorithms and an assessment of their performance is described in a separate report on calibration (Loonen & Koomen, 2009).
end text from Koomen & Borsboom-van Beurden (2011)
In GeoDMS, the discrete alloc function is implemented according to the scaling ideas described in (Tokuyama & Nakano, 1995), where degenerated cases have been handled by virtual perturbation as described in (Edelsbrunner & Mücke, 1990) with perturbation
If there are only two land use types, only the difference between the two suitability maps matters, and one can use the nth element or rth element function for the allocation (or use the weighted variants to implement quantitative allocation).
Discrete allocation can also be used to aggregate a discrete map (aka Downsampling) to larger zones or raster-cells while keeping the total area's constant or within bounds by using the amount of each land use type in or near an aggregate unit as suitability for that type and the total areas as claims (rounded down as minimum claim and rounded up as maximum claim).
When applied iteratively and incorporating dynamic neighbourhood enrichment, one can simulate land-use change caused by natural processes. In contrast, minimum demands and/or maximum land-use restrictions (as specified by the claims) are maintained. When applied iteratively, with feedback from future (neighbourhood-dependent) yields on the current suitability, one can model a time-consistent market equilibrium.
In Luisa, the suitabilities for discrete allocation are called transition potentials and there are three modeltraits for calculating them:
