{'fraction_non_alphanumeric': 0.022869495960860166, 'fraction_numerical': 0.012800091022869496, 'mean_word_length': 4.75794300687848, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Solving Quadratic Assignment Problem with Fixed Assignment (QAPFA) using Branch and Bound Approach

Quadratic Assignment Problem (QAP) has been a very popular problem to be solved among researchers due to its practical applications. Several variants of QAP have been proposed by researchers in the past in order to reflect the real situations of QAP. One of the real problems of QAP is related with facilities which are required to be assigned to certain locations due to its function. In solving this problem, a fixed assignment has to be made thus allowing for the complexity of the problem to be reduced. Hence, this study introduces Quadratic Assignment Problem with Fixed Assignment (QAPFA) with the objective to minimize the assignment cost between the facility and location. This assignment takes into account the flow and distance between facility and location. QAPFA represents the real-world situation of the problem especially in dealing with specific requirement of some facilities to specific locations. Dataset of QAPFA is introduced and is solved using branch and bound approach. As for validation, the results of QAPFA are compared with QAP in terms of objective function and running time. The computational results show that the solution quality of QAPFA is lower when compared with the QAP, while the running time for QAPFA is lower than the QAP. Since the complexity of the problem is reduced by fixing the assignment, thus there is possibility that QAPFA has lower quality than QAP due to the fixed assignment. Nevertheless, in terms of running time QAPFA is better than QAP. It can be concluded that this problem reflect the real problem and practical to be used.

In dealing with real situation, there are some situations where some facilities need to be allocated at some specific locations due to their needs. For instance, some facilities in a hospital such as operating theater and emergency room should not be too far from each other and the flow of product (patients) between the two of the facilities should be minimized. Hence, fixed assignment of QAP is introduced in this study which is called as Quadratic Assignment Problem with Fixed Assignment (QAPFA) QAP has been solved by researchers using various approaches to produce an optimal or near optimal solution. Approaches in solving QAP can be classified into three types which are exact, metaheuristic and hybrid methods. Exact method is used in searching an optimal solution but the method is limited to solve only small data sets [22]. An example of the exact methods for solving QAP are Branch and Bound approach (BB) [23,24], Dynamic Programming [25] and Cutting Plane Method [26]. Nevertheless, metaheuristic and hybrid methods are used to solve large and complex problem of QAP in order to produce a best solution or near optimal solution. Example of such methods are Tabu search algorithm [27], Simulated Annealing algorithms [28], Genetic Algorithms [29] and Ant Colony Optimization [30].
This study proposed a variant of QAP which is called as Quadratic Assignment Problem with Fixed Assignment (QAPFA). In QAPFA, some assignments of facility and location are fixed due to its special requirement. This would represent the real-world situation. The benchmark dataset of QAPFA is proposed and solved using branch and bound approach. The computational results of the QAPFA are compared with the QAP.
The rest of the paper is organized as follows. Section 2 discusses on the literature review of the approaches in solving QAP and its variant, studies related to fixed assignment in QAP and in other types of fixed assignment. Section III presents the mathematical model of QAPFA, data representation and Branch and Bound approach in solving QAPFA. Several experimental results of QAPFA are presented and compared with QAP in Section IV. Finally, we concluded and give some future directions of this study in Section V.

Quadratic Assignment Problem (QAP)
QAP is considered as an NP-hard problem [31,33] which represents the facility layout problem mathematically. This problem considers the assignment of facilities to sites or location whenever there is an exchange between facilities with the objective of minimizing the cost. According to Kratica, Tosic, Filipovic, and Dugosija [32], QAP can be explained as the problem of assigning facilities n to locations n with given flows between the facilities and given distances between the locations, placing the facilities on locations in such a way that the sum of the product between flows and distances is minimized. QAP is a very interesting and challenging problem that can model many real-life problems. Solving this problem is very important for effective and efficient production. Thus, an efficient layout can reduce the cost and thus increase productivity. Another definition of QAP is given by Lim, Wibowo, Desa and Haron [33] where QAP is an assignment model involving a set of facilities that need to be allocated to a set of locations, with each location only will be having one facility. While, the objective is to minimize the total cost of the assignment involve multiply with the flow and the distances between facilities where, n can be the number of facilities and also the number of locations. Then, given two × matrices as which is refer to flow and is the flow from facility to facility . Another matrix is matrix for distance or D, where is the distance from location to location .

1234567890''""
4th International Conference on Operational Research (InteriOR) IOP Publishing IOP Conf. Series: Materials Science and Engineering 300 (2018) 012002 doi:10.1088/1757-899X/300/1/012002 In 1963, Lawler [34] recreated and proposed a general mathematical model originally introduced by Koopman and Beckman [10]. The mathematical model of the problem is as follow: Equation (1) is an objective function where Cikjl is equal to fik multiply by djl. That is, f(i,j) represents the amount of flow between facilities i and j, d(j,l) represents the distance between locations i and j. Equation (2) shows that each facility need to be assigned to each location. Equation (3) shows that only one facility can be assigned to one location and all constrains need to be fulfilled. While, Equation (4) shows that xij = 1 if facility i is assigned to location j and if otherwise, xij = 0.

Approaches in solving QAP
Numerous algorithms have been proposed for both exact and approximate solutions such as heuristics and metaheuristics for solving QAP. Exact algorithms are limited to solving small data sets of the QAP with huge parallel computers, whereas metaheuristics is used for a larger size of dataset and can offer near-optimal solutions within reasonable optimization times [22]. Branch and Bound (BB) algorithms are the most ideal approach in exact methods in solving the QAP [23,24] [33].
The first study in solving QAP using BB was proposed by Gilmore in 1962 [35]. BB was used to find an optimal solution for a problem in assigning a single facility to a single location. Duffuaa and Fedjki [36] modified the BB proposed by Gilmore [35] to solve generalized quadratic semi-assignment problem (GQSAP) which allow several facilities to be allocated in a single location. Another exact method used in solving QAP is Dynamic Programming. It has been used by [25] in solving one of the QAP applications which related with facility layout problem. The incomplete dynamic programming concept was proposed in solving the problem. Cutting Plane Method is one of the earliest method used in solving QAP.
Bazaraa and Sherali [26] used cutting plane procedure in solving quadratic assignment problem formulation. This study used QAP formulation for minimizing a concave quadratic function over the assignment polytope. A cutting plane procedure requires a huge computational effort for solving quadratic assignment problem because of the calculation of the lower bound that derived on the number of cuts needed for termination. However, the result gained from the cutting planes produced optimal or good quality solutions early on in the search process [26].
The capability to use QAP in producing many solution of many different problems has made it the subject of wide research area for comprehensive and metaheuristic strategies. Small size QAP datasets are suitable for exact solutions but the larger dataset cannot be solved by using exact solution in reasonable times due to the computational limits [37]. Therefore, metaheuristic approaches have grew a reputation for their ability to produce high-quality solutions within the computational limitations. A survey done by [38] shows that hybrid procedures from different metaheuristic arrangements are the most utilized solution procedure in solving QAP such as Morita and Shio [39] used a hybrid brand and bound method with Genetic algorithm in solving the multi-stage flexible flowshop-scheduling problem.   [21] introduced subset quadratic assignment problem by giving an idea of application situations. The idea is to place facilities to a subset of locations. For example, the hospital proposed plans, which are to assigning departments at suitable units. The strategy is to minimize the overall cost of time or distance concerning the movement of nurses, doctors and patients between the hospital departments. Besides, the locations should also suitable with the assigned department, for example, the wards need to be allocated at the location that have plenty of sunshine and the emergency rooms should be closed to the front gate.
Other similar applications also can be found in the wireless sensor deployment process. For example, body sensor network has usually used to detect the body functionalities of patients. Some fixed position should be determined in order to place different sensor to detect certain body functionality status and place some information flow around deployed sensor nodes. The location for the sensor nodes must be suitable depending on the function, for example in order to detect body temperature the sensors must be placed inside the mouth or under the armpit, meanwhile to detect the hard functionalities the sensors must be place near the pulse or heart [40,41].
In order to obtain an optimal solution, the most suitable method to use is exact method which is branch and bound for solving a small data. This is because branch and bound make an overall searching without leaving one value in order to search an optimal result value. Since, this study considers solving small dataset of QAPFA, thus exact method is the most suitable for solving the problem. BB is chosen as an approach for solving the proposed problem.

Quadratic Assignment Problem with Fixed Assignment
This study proposed a model of QAP with fixed assignment which is called QAPFA. The model considers multiple sets of facilities and locations where some facilities must be fixed allocated at some locations. The mathematical model of the QAPFA is developed by considering the requirement of the facilities to the locations. The mathematical formulation of quadratic assignment problem with fixed assignment is presented as shown below: Equation (5) is an objective function to minimize the cost of assignment of facility to location by taking into consideration the cost of flow and distance between them. Where n represent the number of total number of facility and location, while, f(i,k) represents the amount of flow between facilities i and k, d(j,q) represents the distance between locations j and q. Equations (6), (7), (8) and (9) are constraints for the problem and each one of the constrains need to be fulfil. Equation (6) shows that

1234567890''""
4th International Conference on Operational Research (InteriOR) IOP Publishing IOP Conf. Series: Materials Science and Engineering 300 (2018) 012002 doi:10.1088/1757-899X/300/1/012002 each facility need to be assign to each location. Equation (7) shows that only one facility can be assign to one location. Equation (8) indicates fixed assignment where the value of i and j is determine by decision maker preference or DMpref. DMpref refers to the preference of the decision maker on the fixed assignment of facility to location where the DMpref is the subset of the Allpref. Allpref represent all preferences of the allocation of the facility to the location and F represent the facility and L represent the location. Equation (9) shows that xij = 1 if facility i is assigned to location j and if otherwise, xij = 0. The illustration of the assignment is show below:  Figure. 1 is an example for 3 facilities to be assigned to 3 locations with the objective of minimizing cost of allocation by taking into consideration the flow-distance cost. Equation (13) represents the Equation (8) which is DMpref. Equation (13) shows the fixed assignment of facility 3 where it must be assigned to location B. This is may be due its special requirement that need to be fulfilled where only location B can fulfil the requirement of facility 3. Therefore, fixed assignment is written as a constraint as shown in Equation (13).

Branch and Bound approach
Branch and Bound (BB) is used in solving QAPFA. The first step is to determine the upper bound and the lower bound of the problem solving. The lower and upper bound are used to close up the region of searching the solution value. When the bound value is found, the value is used to help to determine which of the subproblem should be eliminated. Given node S of the tree and the subproblem of the original problem is a child of the S. Usually, each subproblem is derived from the S through intruding a single new constraint and the child of the S are those subproblem. The feasible solution represents the leaves of the tree. An exponential number of the leaves can determine the instance exist in the search tree. The search is continued until the optimal solution is obtained. This branch and bound approach is tested on dataset ranged from size 3 until 15. The dataset size 12 to 15 is from QAPLIB (website) with some modifications on fixed assignment, while other dataset were generated using dummy data.   2 shows an example of the flow and distance matrices. The matrix used is in symmetric where the fik mean f represent flow, i is row facility and k is column facility. While, djk means that d represent distance, j is a row distance and q is a column distance. The number in the matrix represent the cost between the facility i to k.

Computational results
The QAPFA using BB methods was programmed in Lingo 16.0 on Acer Intel®Core i7 2.00 GHZ computer with 8 GB RAM. In order to validate the QAPFA, the instances with different sizes of QAP are also tested using BB. The computational results and running time for both problems are compared as presented in Table II. The bold font shows the best objective function value, while the italic font represents the minimum running time.  Table 1 shows the comparisons of the objective function value and the running time between QAP and QAPFA on sizes from n = 3 until 15. The objective function value shows that the optimal solutions of QAP are better than the QAPFA. The fixed assignment of QAPFA has made the objective function value to increase. Since some facilities required to have fixed assignment to certain locations, thus the assignment which can give minimum cost never been considered. Hence, it limits the solution search and increased the objective function value of QAPFA compared to QAP. Nevertheless, the running time of QAPFA is shorter than the QAP. Due to fixed assignment of certain facilities to certain locations, thus allowing for the complexity to be reduced significantly compared with QAP. The last column of Table 1. shows the number of assignment that have been fixed for the QAPFA.  Figure 3 show the comparison of running between QAP and QAPFA using line plot. The Figure 3 shows that QAP has longer running time due to its complexity. However, the dataset 12 and 15 shows a decreasing in the running time. Fig. 4 shows the comparison of the objective function values for dataset 3 to 15 between QAP and QAPFA. The bar chart is divided into two based on the size of the dataset. The bar chat show that QAPFA have a higher value than the QAP. This mean that QAP result produce lower cost that meet the objective of the research which is a minimum cost. The fixes assignment that has been done makes the minimum cost never been considered. The second bar chart represent QAP and QAPFA with high objective function results. The result are higher is because of the value in the dataset itself.

Conclusion and Future Work
In this study, a QAPFA is introduced which represent a real situation of QAP. Fixed assignment of certain facility to certain location according to their requirement is considered. The mathematical formulation of QAPFA is presented and various sizes of the QAPFA instances is introduced. The problem was solved using Branch and Bound approach. Finally, the results of QAPFA and QAP were compared in terms of its objective function value and running time. Findings showed that the QAPFA produced higher objective function values compared to the QAP because when the fixed assignment is made and make the it less difficult. However, the running time for QAPFA is less than QAP because of the fixed assignment of certain facilities to certain locations that also reduce the complexity compared to QAP. For the future research, we intend to use a larger size of benchmark data and solve it by using a metaheuristic method so see the result on the objective function.