Please use this identifier to cite or link to this item: http://hdl.handle.net/10603/512600
Title: Optimization Techniques for the Quadratic Assignment Problems
Researcher: Pradeep Kumar
Guide(s): Sharma, Shambhu
Keywords: Mathematics
Physical Sciences
University: Dayalbagh Educational Institute
Completed Date: 2021
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
Pagination: 
URI: http://hdl.handle.net/10603/512600
Appears in Departments:Department of Mathematics

Files in This Item:
File Description SizeFormat 
01_title.pdfAttached File82.13 kBAdobe PDFView/Open
04_abstract.pdf29.89 kBAdobe PDFView/Open
06_content.pdf22.98 kBAdobe PDFView/Open
11_chapter1.pdf237.95 kBAdobe PDFView/Open
12_chapter2.pdf334.93 kBAdobe PDFView/Open
13_chapter3.pdf432.61 kBAdobe PDFView/Open
14_chapter4.pdf350.75 kBAdobe PDFView/Open
15_chapter5.pdf423.5 kBAdobe PDFView/Open
16_conclusion.pdf13.73 kBAdobe PDFView/Open
17_references.pdf199.85 kBAdobe PDFView/Open
18_appendix.pdf392.81 kBAdobe PDFView/Open
19_summary.pdf15.92 kBAdobe PDFView/Open
80_recommendation.pdf18.97 kBAdobe PDFView/Open
Show full item record


Items in Shodhganga are licensed under Creative Commons Licence Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0).

Altmetric Badge: