Assignment Problems with Weighted and Nonweighted Neighborhood Constraints in 36, 44 and 63 Tilings

Amy April D. Bosaing Institute of Mathematical Sciences and Physics University of the Philippines Los Baos n Jomar F. Rabajante Institute of Mathematical Sciences and Physics University of the Philippines Los Baos n jfrabajante@up.edu.ph Mark Lexter D. De Lara Institute of Mathematical Sciences and Physics University of the Philippines Los Baos n
Abstract We formulated a binary integer program to model the assignment problem stated as follows: the elements of given nite sets should be assigned to the compartments of a tiling (with nite number of compartments) such that the costs of having adjacent elements from dierent sets are minimized. We dened 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 rst.

In an assignment problem with nonweighted neighborhood constraint, the costs of the adjacencies between elements of dierent sets are simultaneously minimized, and the weights are considered as dummy only. The eect 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. 2010 AMS Mathematics Subject Classication: 90C27, 90C35, 90C90.

Keywords: assignment problem, regular tilings, integer programming.

Introduction

In an assignment problem, elements of set A are assigned to the elements of set B subject to some criteria or constraints. The members of A can be persons, objects, machines or manufacturing plants; and B can contain tasks, locations or other objects. However, some constraints may exist because not all elements of A can be assigned to an element in B, or selected elements of A are best suited to be assigned to a specic element in B. This type of decision-making problem can be solved using mathematical programming, in particular, binary integer programming [7, 6]. Assignment problems can be seen in real-world scenarios such as assignment of workers to specic jobs, assignment of goods to storage areas in grocery stores, assignment of crops to certain areas in a plantation, assignment of patients with contagious diseases to hospital wards, or assignment of computers to connected network clusters. In this study, we modeled the assignment problem of arranging elements that come from dierent nite sets into the compartments of a given tiling in Euclidean plane. We supposed that the tiling has a nite number of compartments. Each element is assigned to a compartment subject to the constraint that the sum of the costs of the adjacencies of the elements from dierent sets is minimized. The tilings that were considered are regular 2

tilings of regular polygons, specically 36 (triangular), 44 (square) and 63 (hexagonal) tilings [4, 3]. We dened that two elements are adjacent if they were assigned to adjacent compartments, and that two compartments are adjacent if and only if they share a common edge. For simplicity, we assumed that the total number of elements to be assigned is less than or equal to the number of compartments, and at most one element can be assigned to a compartment.

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, we prioritize to minimize rst the costs with higher value. In an assignment problem with nonweighted neighborhood constraint, the costs of the adjacencies between elements of dierent sets are simultaneously minimized without any priority, that is, we simply want that the elements from dierent sets are not adjacent. Arranging the elements of sets in a tiling may be done manually using brute force (enumeration) if the number of elements and the number of compartments being considered are small. However, if the numbers of elements of the sets and compartments become large, then determining the optimal arrangement may be impractical for manual computation. The total number of possible arrangements (optimal and non-optimal) is equal to ! where is the number of compartments, Ng is the number N1 !N2 !...Nk !(Ntotal )! of elements in set g for g = 1, 2, . . . , k and Ntotal = N1 +N2 +. . .+Nk . Hence, we formulated binary integer programs that may help achieve the optimal solutions systematically.

1.1

Related Works

This study is related to location problems. Esteves et al. [2] were able to create a mathematical model that is expected to help solve the problem of overpopulation of bees by determining the optimal distribution of bee colonies in a specic location. They used mixed integer programming in formulating their model while they used graphs to visually represent the environment where the beehives will be distributed. The assignment problem with nonweighted neighborhood constraint is related to graph coloring in which minimum number of colors are needed to paint a map with the restriction of having no same colors that are adjacent. In 2010, the paper of Diaby and Moustapha [1] used integer programming technique to solve graph coloring problems. De Lara and Rabajante [5] presented a model for an assignment problem with weighted neighborhood constraint in 44 tilings. We extended their study to include nonweighted neighborhood constraint and to other tilings. In their paper, they came up with the following model (see Model Formulation section for the denition of parameters and variables): Minimize
r c1 k k r1 c k k

g xgij
i=1 j=1 g=1 g=1

g xgi(j+1) +
i=1 j=1 g=1

g xgij
g=1

g xg(i+1)j

subject to Constraint 1: For i = 1, 2, . . . , r and j = 1, 2, . . . , c,

xgij
g=1

= 0, if ijth compartment is a dummy compartment 1, otherwise

Constraint 2: For g = 1, 2, . . . , k,
r c

xgij = Ng
i=1 j=1

Constraint 3: For i = 1, 2, . . . , r, j = 1, 2, . . . , c and g = 1, 2, . . . , k, xgij {0, 1} 4

1.2

Linear Programming

A linear program is one of the optimization models which has linear objective and constraint expressions. This technique is of the form Optimize f (x1 , x2 , . . . , xn ) g1 (x1 , x2 , . . . , xn ) g2 (x1 , x2 , . . . , xn ) . . . gn (x1 , x2 , . . . , xn ) = b1 b2 . . . b

subject to

Integer linear programs are linear programs in which the variables are integer-valued. Binary integer linear programs require that the variables be restricted to 0 or 1 only. Mixed integer linear programs may have integer and real-valued variables.

1.3

Conversion of NonLinear Objective Function to a Linear Program

If the objective function of a mathematical program is nonlinear such as absolute value function, then, if applicable, we should linearized it so as not to violate the general assumptions of linear programming. For example, the objective function Minimize |f (x1 , x2 , . . . , xn )| can be transformed into Minimize f (x1 , x2 , . . . , xn ) 0 subject to f (x1 , x2 , . . . , xn ) 0 R .

2
2.1

Model Formulation
Parameters and Variables
Let the binary-valued decision variables be 0, if an element from set g is not assigned to the compartment at the ith row and jth column = 1, otherwise

xgij

for i = 1, 2, . . . , r where r is the number of rows, and j = 1, 2, . . . , c where c is the number of columns. The decision variable xgij is like an on/o variable it will be on (that is equal to 1) if an element of set g is assigned to the ij-th compartment, and it will be o (that is equal to 0) if no element from set g is assigned to the ij-th compartment. Let Ng be the number of elements in set g for g = 1, 2, . . . , k where k is the number of sets. Let g be the weight given to set g. Suppose a1 , a2 , . . . , ak , b1 , b2 , . . . , bk be the dummy weights associated to the decision variables y1 , y2 , . . . , yk , z1 , z2 , . . . , zk , respectively, then dene the relation (O ) as (O ) (|(a1 y1 + a2 y2 + + ak yk ) (b1 z1 + b2 z2 + + bk zk )|) = 1(O ) + 2(O ) + + k(O ) where 1(O ) = (a1 y1 + a2 y2 + + ak1 yk1 + ak yk ) (b1 z1 + b2 z2 + + bk1 zk1 + bk zk ) 2(O ) = (a2 y1 + a3 y2 + + ak yk1 + a1 yk ) (b2 z1 + b3 z2 + + bk zk1 + b1 zk ) 3(O ) = (a3 y1 + a4 y2 + + a1 yk1 + a2 yk ) (b3 z1 + b4 z2 + + b1 zk1 + b2 zk ) . . . (k1)(O ) = (ak1 y1 + ak y2 + + ak3 yk1 + ak2 yk ) 6

k(O

(bk1 z1 + bk z2 + + bk3 zk1 + bk2 zk ) = (ak y1 + a1 y2 + + ak2 yk1 + ak1 yk ) (bk z1 + b1 z2 + + bk2 zk1 + bk1 zk ).

The relation (O ) denotes the circular shift permutation of the dummy weights in objective function term O . This relation was used in modeling an assignment problem with nonweighted neighborhood constraint.

2.2

Assignment Problem with Weighted Neighborhood Constraint

For an assignment problem with weighted neighborhood constraint, we prioritize to minimize rst the adjacency costs with higher value. For example, if we have three sets, say set 1 with weight equal to 1, set 2 with weight equal to 2 and set 3 with weight equal to 3, then we prioritize to minimize rst the adjacency between set 1 and set 3 (with cost equal to 2) before minimizing the adjacencies between set 1 and set 2 (with cost equal to 1) and between set 2 and set 3 (with cost equal to 1). We can introduce dummy compartments so that each row has equal number of compartments and each column also has equal number of compartments, see Figures 4 and 5 for illustration. We used this approach to simplify our summation notations in the binary integer programs.

2.2.1

In 36 Tiling (Model 1)

For the 36 tiling, two types of tilings were considered one that starts with adjacent columnar compartments (Model 1) and the other starts with

non-adjacent columnar compartments (Model 2). See Figures 6 and 7 for illustration. The tilings can be transformed into graphs in which the nodes represent the compartments and the edges represent the adjacencies among compartments, see Figure 8 for illustration. Now, the following is the formulated nonlinear binary integer model for the assignment problem with weighted neighborhood constraint in 36 tiling starting with adjacent columnar compartments: Minimize
r c1 k k

g xgij
i=1 j=1 g=1 g=1

g xgi(j+1)

(O1)

r/2 1 c/2

+
i=1 j=1 g=1

g xg(2i)(2j)
g=1

g xg(2i+1)(2j)

(O2)

r/2

c/2

+
i=1 j=1 g=1

g xg(2i1)(2j1)
g=1

g xg(2i)(2j1)

(O3)

subject to Constraint 1: For i = 1, 2, . . . , r and j = 1, 2, . . . , c,

xgij
g=1

= 0, if ijth compartment is a dummy compartment 1, otherwise

Constraint 2: For g = 1, 2, . . . , k,
r c

xgij = Ng
i=1 j=1

Constraint 3: For i = 1, 2, . . . , r, j = 1, 2, . . . , c and g = 1, 2, . . . , k, xgij {0, 1} The term O1 in the objective function represents the costs of the row adjacencies. The term O2 represents the costs of the adjacencies in even columns, while the term O3 represents the costs of the adjacencies in odd columns. See Figure 9 for illustration.

The rst constraint guarantees that at most one element will be assigned to a compartment and that dummy compartments will not have any assigned element. The second constraint guarantees that each element will be assigned to a compartment, while the third constraint assures that the decision variable xgij is binary-valued. 9

Notice that the objective function is composed of expressions in absolute value. We can use Integer Linear Programming techniques to solve the nonlinear model by linearizing the objective function. The following is the linearized binary integer program: Minimize
r c1 r/2 1 c/2 r/2 c/2

ij +
i=1 j=1 i=1 j=1

(2i)(2j) +
i=1 j=1

(2i1)(2j1)

subject to Constraint 1: For i = 1, 2, . . . , r and j = 1, 2, . . . , c 1,

g xgij
g=1 g=1

g xgi(j+1) ij 0

Constraint 2: For i = 1, 2, . . . , r and j = 1, 2, . . . , c 1,

g=1

g xgij +
g=1

g xgi(j+1) ij 0

Constraint 3: For i = 1, 2, . . . , r/2 1 and j = 1, 2, . . . , c/2 ,

g xg(2i)(2j)
g=1 g=1

g xg(2i+1)(2j) (2i)(2j) 0

Constraint 4: For i = 1, 2, . . . , r/2 1 and j = 1, 2, . . . , c/2 ,

g=1

g xg(2i)(2j) +
g=1

g xg(2i+1)(2j) (2i)(2j) 0

Constraint 5: For i = 1, 2, . . . , r/2 and j = 1, 2, . . . , c/2 ,

g xg(2i1)(2j1)
g=1 g=1

g xg(2i)(2j1) (2i1)(2j1) 0

10

Constraint 6: For i = 1, 2, . . . , r/2 and j = 1, 2, . . . , c/2 ,

g=1

g xg(2i1)(2j1) +
g=1

g xg(2i)(2j1) (2i1)(2j1) 0

Constraint 7: For i = 1, 2, . . . , r and j = 1, 2, . . . , c,

xgij
g=1

= 0, if ijth compartment is a dummy compartment 1, otherwise

Constraint 8: For g = 1, 2, . . . , k,
r c

xgij = Ng
i=1 j=1

Constraint 9: For i = 1, 2, . . . , r, j = 1, 2, . . . , c and g = 1, 2, . . . , k, xgij {0, 1} The term O1 in the objective function of the nonlinear binary integer program was transformed to constraints 1 and 2 in the linearized program. The term O2 was transformed to constraints 3 and 4, and the term O3 to constraints 5 and 6. Constraints 1, 2, . . ., 9 has r(c1), r(c1), ( r/2 1) c/2 , ( r/2 1) c/2 , r/2 c/2 , r/2 c/2 , rc, k and rck subconstraints, respectively. 2.2.2 In 36 Tiling (Model 2)

The following are the sample graph illustration (Figure 10) and the formulated nonlinear binary integer model for the assignment problem with weighted neighborhood constraint in 36 tiling starting with non-adjacent columnar compartments: Minimize
r c1 k k

g xgij
i=1 j=1 g=1 g=1

g xgi(j+1)

(O1)

11

r/2 1 c/2

+
i=1 j=1 g=1

g xg(2i)(2j1)
g=1

g xg(2i+1)(2j1)

(O2)

r/2

c/2

+
i=1 j=1 g=1

g xg(2i1)(2j)
g=1

g xg(2i)(2j)

(O3)

subject to Constraint 1: For i = 1, 2, . . . , r and j = 1, 2, . . . , c,

xgij
g=1

= 0, if ijth compartment is a dummy compartment 1, otherwise

Constraint 2: For g = 1, 2, . . . , k,
r c

xgij = Ng
i=1 j=1

Constraint 3: For i = 1, 2, . . . , r, j = 1, 2, . . . , c and g = 1, 2, . . . , k, xgij {0, 1} The term O1 in the objective function represents the costs of the row adjacencies. The term O2 represents the costs of the adjacencies in odd columns, while the term O3 represents the costs of the adjacencies in even columns. We do the same process as in 36 Tiling (Model 1) to linearize the objective function. 12

2.2.3

In 63 Tiling

We dene three types of adjacencies in a 63 tiling row adjacency, column adjacency and diagonal adjacency, see Figure 11 for illustration. The following are the sample graph illustration (Figure 12) and the formulated nonlinear binary integer model for the assignment problem with weighted neighborhood constraint in 63 tiling:

Minimize
r c1 k k

g xgij
i=1 j=1 g=1 g=1

g xgi(j+1)

(O1)

r1

+
i=1 j=1 g=1

g xgij
g=1

g xg(i+1)j

(O2)

r1

+
i=1 j=2 g=1

g xgij
g=1

g xg(i+1)(j1)

(O3)

subject to Constraint 1: For i = 1, 2, . . . , r and j = 1, 2, . . . , c,

xgij
g=1

= 0, if ijth compartment is a dummy compartment 1, otherwise 13

Constraint 2: For g = 1, 2, . . . , k,
r c

xgij = Ng
i=1 j=1

Constraint 3: For i = 1, 2, . . . , r, j = 1, 2, . . . , c and g = 1, 2, . . . , k, xgij {0, 1} The term O1 in the objective function represents the costs of the row adjacencies. The term O2 represents the costs of the column adjacencies, while the term O3 represents the costs of the diagonal adjacencies. We do the same process as in 36 Tiling (Model 1) to linearize the objective function.

2.3

Assignment Problem with Nonweighted Neighborhood Constraint

For an assignment problem with nonweighted neighborhood constraint, we simultaneously minimize the costs of the adjacencies between elements from dierent sets without considering any priority. That is, we only want to have the least number of adjacencies between elements from dierent sets without considering any weights. However, we cannot just remove the weights or let the weights assigned to all sets be equal, that is |g g | = 0 for any set g and g, because this implies that we do not have any cost to minimize. To remedy this, we let the assigned weights g for any set g to be considered as dummy, but we will later eliminate the eect of the dummy weights by using the relation (O ) . For simplicity, we let g = g. For example, refer to Figure 13, say we have sets s1, s2 and s3. In the rst permutation, the adjacencies between elements of s1 and s3 should be minimized rst because they have the largest adjacency cost (cost = 2). In the second permutation, the adjacencies between elements of s1 and s2 should be minimized rst because they have the largest adjacency cost (cost = 2). In the third permutation, the adjacencies between elements of s2 and s3 should be minimized rst because they have the largest adjacency cost (cost = 2). By doing this circular shift permutation, we eliminate the eect of the dummy weights. However, this strategy would make the linearized binary integer model associated to an assignment problem with nonweighted neighborhood constraint to have more subconstraints and to be computationally expensive than the model associated to an assignment problem with weighted neighborhood constraint. 14

2.3.1

In 36 Tiling (Model 1)

The following is the formulated nonlinear binary integer model for the assignment problem with nonweighted neighborhood constraint in 36 tiling starting with adjacent columnar compartments: Minimize
r c1 k k

(O1)
i=1 j=1 r/2 1 c/2 g=1 k

g xgij
g=1

g xgi(j+1)

(O1)

+
i=1 r/2 c/2 j=1

(O2)
g=1 k

g xg(2i)(2j)
g=1 k

g xg(2i+1)(2j)

(O2)

+
i=1 j=1

(O3)
g=1

g xg(2i1)(2j1)
g=1

g xg(2i)(2j1)

(O3)

subject to Constraint 1: For i = 1, 2, . . . , r and j = 1, 2, . . . , c,

xgij
g=1

= 0, if ijth compartment is a dummy compartment 1, otherwise

Constraint 2: For g = 1, 2, . . . , k,
r c

xgij = Ng
i=1 j=1

15

Constraint 3: For i = 1, 2, . . . , r, j = 1, 2, . . . , c and g = 1, 2, . . . , k, xgij {0, 1} The term O1 in the objective function represents the costs of the row adjacencies. The term O2 represents the costs of the adjacencies in even columns, while the term O3 represents the costs of the adjacencies in odd columns. The objective function is composed of expressions in absolute value. Now, the following is the linearized binary integer program: Minimize
r c1 k r/2 1 c/2 k r/2 c/2 k

hij +
i=1 j=1 h=1 i=1 j=1 h=1

h(2i)(2j) +
i=1 j=1 h=1

h(2i1)(2j1)

subject to Constraint 1: For h = 1, 2, . . . , k, i = 1, 2, . . . , r and j = 1, 2, . . . , c 1, h(O1) hij 0 Constraint 2: For h = 1, 2, . . . , k, i = 1, 2, . . . , r and j = 1, 2, . . . , c 1, h(O1) hij 0 Constraint 3: For h = 1, 2, . . . , k, i = 1, 2, . . . , r/2 1 and j = 1, 2, . . . , c/2 , h(O2) h(2i)(2j) 0 Constraint 4: For h = 1, 2, . . . , k, i = 1, 2, . . . , r/2 1 and j = 1, 2, . . . , c/2 , h(O2) h(2i)(2j) 0 Constraint 5: For h = 1, 2, . . . , k, i = 1, 2, . . . , r/2 and j = 1, 2, . . . , c/2 , h(O3) h(2i1)(2j1) 0 Constraint 6: For h = 1, 2, . . . , k, i = 1, 2, . . . , r/2 and j = 1, 2, . . . , c/2 , h(O3) h(2i1)(2j1) 0 16

Constraint 7: For i = 1, 2, . . . , r and j = 1, 2, . . . , c,

xgij
g=1

= 0, if ijth compartment is a dummy compartment 1, otherwise

Constraint 8: For g = 1, 2, . . . , k,
r c

xgij = Ng
i=1 j=1

Constraint 9: For i = 1, 2, . . . , r, j = 1, 2, . . . , c and g = 1, 2, . . . , k, xgij {0, 1} The term O1 in the objective function of the nonlinear binary integer program was transformed to constraints 1 and 2 in the linearized program. The term O2 was transformed to constraints 3 and 4, and the term O3 to constraints 5 and 6. Constraints 1, 2, . . ., 9 has kr(c 1), kr(c 1), k( r/2 1) c/2 , k( r/2 1) c/2 , k r/2 c/2 , k r/2 c/2 , rc, k and rck subconstraints, respectively. 2.3.2 In 36 Tiling (Model 2)

The following is the formulated nonlinear binary integer model for the assignment problem with nonweighted neighborhood constraint in 36 tiling starting with non-adjacent columnar compartments: Minimize
r c1 k k

(O1)
i=1 j=1 g=1

g xgij
g=1

g xgi(j+1)

(O1)

r/2 1 c/2

+
i=1 j=1

(O2)
g=1

g xg(2i)(2j1)
g=1

g xg(2i+1)(2j1)

(O2)

r/2

c/2

+
i=1 j=1

(O3)
g=1

g xg(2i1)(2j)
g=1

g xg(2i)(2j)

(O3)

17

subject to Constraint 1: For i = 1, 2, . . . , r and j = 1, 2, . . . , c,

xgij
g=1

= 0, if ijth compartment is a dummy compartment 1, otherwise

Constraint 2: For g = 1, 2, . . . , k,
r c

xgij = Ng
i=1 j=1

Constraint 3: For i = 1, 2, . . . , r, j = 1, 2, . . . , c and g = 1, 2, . . . , k, xgij {0, 1} The term O1 in the objective function represents the costs of the row adjacencies. The term O2 represents the costs of the adjacencies in odd columns, while the term O3 represents the costs of the adjacencies in even columns. We do the same process as in 36 Tiling (Model 1) to linearize the objective function. 2.3.3 In 44 Tiling

The following is the formulated nonlinear binary integer model for the assignment problem with nonweighted neighborhood constraint in 44 tiling: Minimize
r c1 k k

(O1)
i=1 j=1 g=1

g xgij
g=1

g xgi(j+1)

(O1)

r1

+
i=1 j=1

(O2)
g=1

g xgij
g=1

g xg(i+1)j

(O2)

subject to 18

Constraint 1: For i = 1, 2, . . . , r and j = 1, 2, . . . , c,

xgij
g=1

= 0, if ijth compartment is a dummy compartment 1, otherwise

Constraint 2: For g = 1, 2, . . . , k,
r c

xgij = Ng
i=1 j=1

Constraint 3: For i = 1, 2, . . . , r, j = 1, 2, . . . , c and g = 1, 2, . . . , k, xgij {0, 1} The term O1 in the objective function represents the costs of the row adjacencies, while the term O2 represents the costs of the column adjacencies, see Figure 14 for illustration. We do the same process as in 36 Tiling (Model 1) to linearize the objective function.

2.3.4

In 63 Tiling

The following is the formulated nonlinear binary integer model for the assignment problem with nonweighted neighborhood constraint in 63 tiling: Minimize

19

c1

(O1)
i=1 j=1 g=1

g xgij
g=1

g xgi(j+1)

(O1)

r1

+
i=1 j=1

(O2)
g=1

g xgij
g=1

g xg(i+1)j

(O2)

r1

+
i=1 j=2

(O3)
g=1

g xgij
g=1

g xg(i+1)(j1)

(O3)

subject to Constraint 1: For i = 1, 2, . . . , r and j = 1, 2, . . . , c,

xgij
g=1

= 0, if ijth compartment is a dummy compartment 1, otherwise

Constraint 2: For g = 1, 2, . . . , k,
r c

xgij = Ng
i=1 j=1

Constraint 3: For i = 1, 2, . . . , r, j = 1, 2, . . . , c and g = 1, 2, . . . , k, xgij {0, 1} The term O1 in the objective function represents the costs of the row adjacencies. The term O2 represents the costs of the column adjacencies, while the term O3 represents the costs of the diagonal adjacencies. We do the same process as in 36 Tiling (Model 1) to linearize the objective function.

Illustrative Examples

Let us suppose there are three groups and denote G1, G2 and G3 to be elements from Group 1, Group 2 and Group 3, respectively. The distribution of elements for each group is shown in Table 1. 20

Table 1: Distribution of elements per group. Group Number of elements Group 1 3 Group 2 4 Group 3 5 Now we want to assign the members of the given groups to the compartments of a tiling such that the costs of having adjacent elements from dierent sets are minimized. Assume g = g. The tilings to be considered for assignment problem with weighted neighborhood constraint are shown in Figures 15 and 16. The tilings to be considered for assignment problem with nonweighted neighborhood constraint are shown in Figures 17 and 18.

The optimal solutions (not necessarily unique) to our illustrative examples are shown in Figures 19-22. The optimal solutions were determined using General Algebraic Modeling System (GAMS) version 23.7.

21

Summary

In this study, binary integer models were formulated for the assignment problem stated as: given a nite number of k sets and nite number of M compartments of a regular polygonal tiling, each Ng element in set g (g = 1, 2, . . . , k) should be arranged in the polygonal tiling such that N1 + N2 + + Nk M and the costs of having adjacent elements from dierent sets are minimized. Two neigborhood constraints were considered weighted and nonweighted. We used the idea of circular shift permutation to model the assignment problems with nonweighted neighborhood constraint. The formulated binary integer programs were linearized, i.e. transformed to linear programming models, since the objective functions have absolute value expressions. This study can be extended to include other kinds of adjacencies and other types of tilings. 22

References
[1] Moustapha Diaby. Linear programming formulation of the vertex colouring problem. Int. J. Mathematics in Operational Research, 2(3):259289, 2010. [2] Ramon Joseph P. Esteves, Michael C. Villadelrey, and Jomar F. Rabajante. Determining the optimal distribution of bee colony locations to avoid overpopulation using mixed integer programming. Journal of Nature Studies, 9(1):7982, 2010. [3] B. Grunbaum and G. C. Shephard. Tilings and Patterns. Dover Publications, 2011. [4] Forrest H. Kaatz, Adhemar Bultheel, and Takeshi Egami. Order in mathematically ideal porous arrays: the regular tilings. J. Appl. Phys., 2010. Submitted. [5] Mark Lexter D. De Lara and Jomar F. Rabajante. Population assignments in grids with neighborhood constraint. International Industrial Engineering Conference: Research, Applications and Best Practices, August 2010. [6] Marius Posta, Jacques A. Ferland, and Philippe Michelon. An exact method with variable xing for solving the generalized assignment problem. Technical report, CIRRELT, March 2011. [7] Hamdy A. Taha. Operations Research: An Introduction. Prentice Hall, 8th edition, 2006.

23