Assignment Problem

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.

acceptable ( X ) { 0 , 1 } acceptable( X ) -> lbrace 0, 1 rbrace

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 x na x_na . An assignment of all assignment variables x ds X x_ds in X is a solution to the assignment problem X.  [related] 

x ds X : x ds = { 1 , if d is assigned to s 0 , otherwise x_ds in X : x_ds = left lbrace stack {1 ", if"d "is assigned to" s # 0 ", otherwise"} right none

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.

a A : o ( D S X ) = { a ( o ) , if defined , undefined , otherwise. forall a in A: forall o in ( D union S union X ) = left lbrace stack { a(o) in setN , " if defined", # "undefined" , "otherwise."} right none

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.

A limited = { a , a A d D : a ( d ) s S : a ( s ) = undefined s S : a ( s ) d D : a ( d ) = undefined x X : a ( x ) } A_limited = left lbrace stack {a}, stack {a in A # forall d in D: a(d) in setN and forall s in S: a(s) = undefined # {} or forall s in S: a(s) in setN and forall d in D: a(d) = undefined # forall x in X: a(x) in setN } right rbrace