Partial ranking in sets of partial solutions of problems of linear and quadratic assignment

Partial ranking in sets of partial solutions of problems of linear and quadratic assignment

0.00 Avg rating0 Votes
Article ID: iaor20084718
Country: Brazil
Volume: 23
Issue: 2
Start Page Number: 265
End Page Number: 284
Publication Date: May 2003
Journal: Pesquisa Operacional
Authors: ,
Keywords: programming: quadratic
Abstract:

We present an approach to Quadratic Assignment Problem, QAP, via a linear relaxation, through the use of the Linear Assignment Problem, LAP. We define one ordering an LAP-solution-set that makes us compare QAP costs. From here, this poset, partial ordering set, considers coordinates of instances as free variables. We have managed to build a capable algorithm to determine freely comparable permutation pairs. A theorem shows that the order mentioned above is compatible to the one that involves inversion numbers of permutations. We can apply linear and quadratic solutions to permutations and empiric tests are presented to show that the inversion numbers can be used to measure the quality of QAP-solutions.

Reviews

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