The Quadratic Assignment Problem Theory and Algorithms
The quadratic assignment problem (QAP) was introduced in 1957 by Koopmans and Beckmann to model a plant location problem. Since then the QAP has been object of numerous investigations by mathematicians, computers scientists, ope- tions researchers and pra
- PDF / 26,205,722 Bytes
- 296 Pages / 482 x 692 pts Page_size
- 67 Downloads / 187 Views
COMBINATORIAL OPTIMIZATION VOLUME 1
Through monographs and contributed works the objective of the series is to publish state of the art expository research covering all topics in the field of combinatorial optimization. In addition, the series will include books which are suitable for graduate level courses in computer science, engineering, business, applied mathematics, and operations research. Combinatorial (or discrete) optimization problems arise in various applications, including communications network design, VLSI design, machine vision, airline crew scheduling, corporate planning, computer-aided design and manufacturing, database query design, cellular telephone frequency assignment, constraint directed reasoning, and computational biology. The topics of the books will cover complexity analysis and algorithm design (parallel and serial), computational experiments and applications in science and engineering. Series Editors:
Ding-Zhu Du, University of Minnesota Panos M. Pardalos, University of Florida Advisory Editorial Board:
Afonso Ferreira, CNRS-LIP ENS Lyon Jun Gu, University of Calgary D. Frank Hsu, Fordham University David S. Johnson, AT&T Research James B. Orlin, M.l.T. Christos H. Papadimitriou, University of California at Berkeley Fred S. Roberts, Rutgers University
The Quadratic Assignment Problem Theory and Algorithms by Eranda ~ela Institute of Mathematics, Technical University Graz, Graz, Austria
Springer-Science+Business Media, B.V.
A C.I.P. Catalogue record for this book is available from the Library of Congress.
ISBN 978-1-4419-4786-4 ISBN 978-1-4757-2787-6 (eBook) DOI 10.1007/978-1-4757-2787-6
Printed on acid-free paper
All Rights Reserved © 1998 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 1998. Softcover reprint of the hardcover 1st edition 1998 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner.
CONTENTS
PREFACE
IX
LIST OF FIGURES
Xlll
LIST OF TABLES 1
PROBLEM STATEMENT AND COMPLEXITY ASPECTS 1.1 1.2 1.3 1.4
1.5
2
xv
Problem Statement Applications Two alternative formulations of the QAP Linearizations 1.4.1 Kaufman and Broeckx linearization 1.4.2 Frieze and Yadegar linearization 1.4.3 Padberg and Rijallinearization Computational complexity aspects 1.5.1 The complexity of optimally and approximately solving QAPs 1.5.2 The complexity of local search
EXACT ALGORITHMS AND LOWER BOUNDS 2.1
Lower bounds 2.1.1 The bound of Gilmore-Lawler and other Gilmore-Lawlerlike bounds 2.1.2 Eigenvalue related lower bounds 2.1.3 Bounding techniques based on reformulations 2.1.4 Bounds based on linear programming relaxations v
1 2 3 5 7 8 9 10 17 17 22 27 28 28 38 43 46
THE QUADRATIC ASSIGNMENT PROBLEM
VI
2.2 2.3
3
HEURISTICS AND ASYMPTOTIC BEHAVIOR 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8
4
2.1.5 Bounds base
