### ASSIGNMENT PROBLEMS WITH WEIGHTED AND NON-WEIGHTED NEIGHTBORHOOD CONSTRAINTS IN 36, 44 AND 63 TILINGS

#### Abstract

We formulated a binary integer program to model the assignment

problem stated as follows: the elements of given finite sets should be

assigned to the compartments of a tiling (with finite number of compartments)

such that the costs of having adjacent elements from different

sets are minimized. We defined that two compartments are adjacent if

and only if they share a common edge. In this paper, we considered the

regular tilings of regular polygons in Euclidean plane.

An assignment problem can have weighted and nonweighted neighborhood

constraints. Weights ωg and ωg are assigned to sets g and g,

respectively. The cost of having an element from set g adjacent to an

element of set g is computed as |ωg − ωg|. In an assignment problem

with weighted neighborhood constraint, the higher adjacency costs are

minimized first.

In an assignment problem with nonweighted neighborhood constraint,

the costs of the adjacencies between elements of different sets are simultaneously

minimized, and the weights are considered as dummy only. The

effect of the dummy weights can be removed by permuting the weights

in the objective function of the binary integer program. The binary integer

program associated with the assignment problem with nonweighted

neighborhood constraint is computationally more expensive than the assignment

problem with weighted constraint.

We can represent the tilings as graphs and the assignment problems as

linearized binary integer programs. We presented illustrative examples

showing the optimal solutions; however, optimal solutions may not be

unique.

#### Full Text:

PDF### Refbacks

- There are currently no refbacks.