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

Amy April D. Bosaing, Jomar F. Rabajante, Mark Lexter D. De Lara

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.