Network-based formulations of the quadratic assignment problem |
| |
Affiliation: | 1. Grupo da Causa Humana, Ouro Preto, Brazil;2. Instituto de Pesquisa e Desenvolvimento de Tecnologias, Ouro Preto, MG, Brazil;3. Graduate Program in Electrical Engineering, Universidade Federal de Minas Gerais, Belo Horizonte, MG, Brazil;4. Department of Computer Science, Universidade do Estado do Rio de Janeiro, RJ, Brazil;5. Department of Automatic Control and Systems Engineering, University of Sheffield, Sheffield, UK;6. Department of Electrical Engineering, Universidade Federal de Minas Gerais, Belo Horizonte, MG, Brazil;7. Department of Information and Communication Technologies, Universitat Pompeu Fabra, Barcelona, Spain;8. Department of Economics and Business, Universitat Pompeu Fabra, Barcelona, Spain;9. Department of Computer Science, Universidade Federal de Ouro Preto, Ouro Preto, MG, Brazil;10. Cité Scientifique, University Lille 1, Lille, France;11. INRIA Lille - Nord Europe Parc Scientifique de la Haute Borne 40, Avenue Halley, Bat A, France;12. Computer Science Laboratory of Paris, Université Pierre et Marie Curie, Paris, France;3. Department of Pathology, University of Utah School of Medicine, Salt Lake City, Utah 84112;4. Department of Pathology, ARUP Institute for Clinical and Experimental Pathology, ARUP Laboratories, Salt Lake City, Utah 84108 |
| |
Abstract: | We present two formulations of the Quadratic Assignment Problem (QAP) that result in network flow problems with integer variables and side constraints. A linearization of the QAP is obtained in both cases by considering each facility to consist of two parts—a source for all outgoing flows from that facility, and a sink for all incoming flows to the facility. Preliminary computational experience with both approaches is presented. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|