• The quadratic three-dimensiona...

Treffer: The quadratic three-dimensional assignment problem : Exact and approximate solution methods

Title:
The quadratic three-dimensional assignment problem : Exact and approximate solution methods
Authors:
HAHN, Peter M, KIM, Bum-Jin, STÜTZLE, Thomas, KANTHAK, Sebastian, HIGHTOWER, William L, SAMRA, Harvind, ZHI DING, GUIGNARD, Monique
Source:
European journal of operational research. 184(2):416-428
Publisher Information:
Amsterdam: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 1 p
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Logiciel, Software, Systèmes informatiques et systèmes répartis. Interface utilisateur, Computer systems and distributed systems. User interface, Affectation quadratique, Quadratic assignment, Afectación cuadrática, Algorithme randomisé, Randomized algorithm, Algoritmo aleatorizado, Algorithme recherche, Search algorithm, Algoritmo búsqueda, Commutation paquet, Packet switching, Conmutación por paquete, Demande répétition automatique, Automatic repeat request, Demanda repetición automática, Entrée sortie, Input output, Entrada salida, Modulation, Modulación, Modélisation, Modeling, Modelización, Méthode heuristique, Heuristic method, Método heurístico, Méthode séparation et évaluation, Branch and bound method, Método branch and bound, Optimisation, Optimization, Optimización, Optimum, Optimo, Programmation quadratique, Quadratic programming, Programación cuadrática, Programmation stochastique, Stochastic programming, Programación estocástica, Recherche locale, Local search, Busca local, Résolution problème, Problem solving, Resolución problema, Solution exacte, Exact solution, Solución exacta, Technique linéarisation, Linearization techniques, Télécommunication, Telecommunication, Telecomunicación, Problème affectation, Assignment problem, Problema asignación, Branch-and-bound, Heuristics, OR in telecommunications, Three-index assignment
Document Type:
Fachzeitschrift Article
File Description:
text
Language:
English
Author Affiliations:
Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA 19104-6315, United States
CoDE, IRIDIA, CP 194I6, Université Libre de Bruxelles, 1050 Brussels, Belgium
Computer Science, Darmstadt University of Technology, 64283 Darmstadt, Germany
Mathematics and Computer Science, High Point University, High Point, NC 27262, United States
Electrical and Computer Engineering, University of California, Davis, Davis, CA 95616, United States
Operations and Information Management, The Wharton School, University of Pennsylvania, Philadelphia, PA 19104-6340, United States
ISSN:
0377-2217
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=19086268
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.19086268
Database:
PASCAL Archive

Weitere Informationen

This paper reports on algorithm development for solving the quadratic three-dimensional assignment problem (Q3AP). The Q3AP arises, for example, in the implementation of a hybrid ARQ (automatic repeat request) scheme for enriching diversity among multiple packet re-transmissions, by optimizing the mapping of data bits to modulation symbols. Typical practical problem sizes would be 8, 16, 32 and 64. We present an exact solution method based upon a reformulation linearization technique that is one of the best available for solving the quadratic assignment problem (QAP). Our current exact algorithm is useful for Q3AP instances of size 13 or smaller. We also investigate four stochastic local search algorithms that provide optimum or near optimum solutions for large and difficult QAP instances and adapt them for solving the Q3AP. The results of our experiments make it possible to get good solutions to signal mapping problems of size 8 and 16.