Semi assignment problem

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

$\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_i**j 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