An assignment problem requires that demands are assigned to supplies. For a given
assignment set X
the assignment problem return 1
, if the assignment set is a acceptable solution, and 0
otherwise.
-
Create visualization.
As shown in the imagery a one dimensional assignment problem demands D
that each element of demands is assigned to a element of supplies S
. Every possible assignment of a demand d
to a supply s
is represented by the variable
. An assignment of all assignment variables
is a solution to the assignment problem X
. [related]
A complete solution is an assignment set X
, where each demand has assigned at least one supply. Often it is also required that
each demand has at most one supply. If there has to be exactly one supply for each
demand, than it can be called an 1 on 1 problem. In this case the set of demands and
the set of supplies has to have the same size. If one demand can be assigned to N
supplies this can be called an 1 on N Problem.
The assignment problem itself does not model the semantic meaning of the problem at hand. It just states that a set of demands and a set of supplies are assigned to each other. Each demand and each supply has an inherit identity. There is no inherent semantic meaning of an identity.
When the N-Queen puzzle is modeled as an assignment problem, each demand and supply
is just an identity. The problem also restricts the set of valid assignments via the acceptable
function. The function itself does describe, why a given solution is incorrect. The
model does not state which row corresponds to which elements of the supplies. In general
its not possible to model the puzzle with concepts introduced by the puzzle.
The basic idea of the semantic extension is the usage of attribute functions A
. Each attribute function a
returns a value, for all supplies S
, demands D
and assignemnts X
. The value returned by the attribute, describes or relates to some meaning. In this
case it is modeled via the set of all integers, that itself can for instance represent
the set of all strings.
In most cases it does not make sense to provide values by an attribute function a
for supplies and demands. In most cases it makes sense, that an attribute function
has only defined values for supplies or only for demands. The queens in the N-Queen
problem, do in general not have an inherent row and column, because otherwise the
solution of the problem would be already present. This does no apply for the assignments
in general. In this case, every assignment has an defined value for every attribute.