Optimization Techniques for the Quadratic Assignment Problems

Abstract

The present thesis focuses on the development of methodologies and algorithms to find an optimal solution of quadratic assignment problem (QAP). To obtain an optimal solution, four methods are developed. newline The first method is based on one by one allocation of lowest cost cells of cost matrix of QAP. The cell containing zero having the greatest suffix value is allocated to find the minimum cost of the assignment. If one cell is allocated, then its complementary cell is also allocated. Once the allocation is done to both cells, all the cells satisfying the constraints are marked cross. Further, the minimum cost cell is searched by the same procedure in the remaining cost matrix and allocation continues as long as complete assignment is done. The solution obtained is either an optimal solution or nearest to the optimal. newline The second method is based on a reformulation of QAP. This reformulation breaks the objective function of QAP into the reduced objective function of QAP and in the objective function of linear assignment problem (LAP). The advantage of this reformulation is that the solution of the whole QAP can be found by solving LAP only. If corresponding to the solution obtained by LAP, the value of the reduced objective function is zero, then the obtained solution is the optimal solution and the corresponding cost is the optimal cost. Otherwise, the solution is not optimal and the corresponding cost is considered as a lower bound for QAP. newline The third method is developed for searching the steepest descent direction for QAP. The method offers an expression for the change in the objective function value in terms of non-basic variables. That helps us to know for which non-basic variable to be the basic variable the value of objective function decreases most rapidly. newline In fourth method, a down gradient technique is developed based on the steepest descent direction search method. Once an initial basic feasible solution is found, the algorithm is designed to choose the entering variable to enter the in the basis and outgoing variable to leave from the basis for the improvement of the solution. The algorithm terminates in the finite number of iterations. The solution obtained using this algorithm is either optimal solution or nearest to optimal. newline newline