Quadratic assignment problems – not so hard in spreadsheets

Quadratic assignment problems – not so hard in spreadsheets

0.00 Avg rating0 Votes
Article ID: iaor2008494
Country: United Kingdom
Volume: 35
Issue: 5
Start Page Number: 541
End Page Number: 552
Publication Date: Oct 2007
Journal: OMEGA
Authors:
Keywords: spreadsheets, education
Abstract:

Quadratic assignment problems (QAP) are rarely mentioned in introductory textbooks in management science and other relevant areas. Even in advanced textbooks, only very small examples are used, because of the complexity of the cost function. This article shows that alternative formulations of the cost function reduce the complexity. The cost function is still quadratic and the variables are still integers (binary variables), so the computational difficulties are the same as with the traditional approach. But new solvers for spreadsheets seem to be quite efficient using the matrix representation of the cost function. This approach turns out to be very simple to implement in spreadsheets. Another formulation directly representing the permutation by integers is even easier to implement, and has shown very promising results using heuristic solvers. In fact spreadsheet solvers could very well be the preferred software solving QAP, compared to other general purpose optimization software.

Reviews

Required fields are marked *. Your email address will not be published.