Semi Assignment Problem

From ObjectVision

Jump to: navigation, search

The Semi Assignment Problem (SAP) aka lambda-assignment aka simple b-matching is the algorithmic problem of finding the \(X_{ij} >= 0\) for each land unit \(i\) and land use type \(j\) that solves the following optimization problem for given suitabilities \(S_{ij}\):


\(\max \sum\limits_{ij}{X_{ij} * S_{ij}}\) subject to

for each \(j\): \(\sum\limits_{i}{X_{ij}} <= b_j\) and for each land unit \(i\): \(\sum\limits_{j}{X_{ij}} = 1\)

Thus \(X_{ij}\) represents whether land unit \(i\) is allocated to land use type \(j\) and only one single allocation per land unit is allowed.

This differs in two aspects from the Discrete Allocation:

  1. \(b_j\) only enables strict equality claims, thus no slack is allowed between min and max claims in this problem formulation
  2. claims are not related to regions (sub sets of the set of land units) although formally this restriction can be circumvented by defining a separate land use types for each region and assigning prohibitive negative values to the suitability of those types in other regions.

SAP is a generalization of LAP

SAP is a specialization of the Transportation Problem

Personal tools