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.