Overview

Location, scheduling and design problems are assignment type problems with quadratic cost functions and occur in many contexts stretching from spatial economics via plant and office layout planning to VLSI design and similar prob­ lems in high-technology production settings. The presence of nonlinear inter­ action terms in the objective function makes these, otherwise simple, problems NP hard. In the first two chapters of this monograph we provide a survey of models of this type and give a common framework for them as Boolean quadratic problems with special ordered sets (BQPSs). Special ordered sets associated with these BQPSs are of equal cardinality and either are disjoint as in clique partitioning problems, graph partitioning problems, class-room scheduling problems, operations-scheduling problems, multi-processor assign­ ment problems and VLSI circuit layout design problems or have intersections with well defined joins as in asymmetric and symmetric Koopmans-Beckmann problems and quadratic assignment problems. Applications of these problems abound in diverse disciplines, such as anthropology, archeology, architecture, chemistry, computer science, economics, electronics, ergonomics, marketing, operations management, political science, statistical physics, zoology, etc. We then give a survey of the traditional solution approaches to BQPSs. It is an unfortunate fact that even after years of investigation into these problems, the state of algorithmic development is nowhere close to solving large-scale real­ life problems exactly. In the main part of this book we follow the polyhedral approach to combinatorial problem solving because of the dramatic algorith­ mic successes of researchers who have pursued this approach.

Full Product Details

Author:   Manfred W. Padberg ,  Minendra P. Rijal
Publisher:   Springer-Verlag New York Inc.
Imprint:   Springer-Verlag New York Inc.
Edition:   Softcover reprint of the original 1st ed. 1996
Volume:   3
Dimensions:   Width: 15.50cm , Height: 1.20cm , Length: 23.50cm
Weight:   0.365kg
ISBN:  

9781461285960

ISBN 10:   1461285968
Pages:   220
Publication Date:   26 September 2011
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   Manufactured on demand  
We will order this item for you from a manufactured on demand supplier.

Table of Contents

1 Location Problems.- 1.1 A Modified KB Model.- 1.2 A Symmetric KB Model.- 1.3 A Five-City Plant Location Example.- 1.4 Plant and Office Layout Planning.- 1.5 Steinberg’s Wiring Problem.- 1.6 The General Quadratic Assignment Problem.- 2 Scheduling and Design Problems.- 2.1 Traveling Salesman Problems.- 2.2 Triangulation Problems.- 2.3 Linear Assignment Problems.- 2.4 VLSI Circuit Layout Design Problems.- 2.5 Multi-Processor Assignment Problems.- 2.6 Scheduling Problems with Interaction Cost.- 2.7 Operations-Scheduling Problems.- 2.8 Graph and Clique Partitioning Problems.- 2.9 Boolean Quadric Problems and Relatives.- 2.10 A Classification of Boolean Quadratic Problems.- 3 Solution Approaches.- 3.1 Mixed zero-one formulations of QAPs.- 3.2 Branch-and-bound algorithms for QAPs.- 3.3 Traditional cutting plane algorithms.- 3.4 Heuristic procedures.- 3.5 Polynomially solvable cases.- 3.6 Computational experience to date.- 4 Locally Ideal LP Formulations I.- 4.1 Graph Partitioning Problems.- 4.2 Operations Scheduling Problems.- 4.3 Multi-Processor Assignment Problems.- 5 Locally Ideal LP Formulations II.- 5.1 VLSI Circuit Layout Design Problems.- 5.2 A General Model.- 5.3 Quadratic Assignment Problems.- 5.4 Symmetric Quadratic Assignment Problems.- 6 Quadratic Scheduling Problems.- 6.1 Alternative Formulations of the OSP.- 6.2 Quadratic Scheduling Polytopes.- 7 Quadratic Assignment Polytopes.- 7.1 The Affine Hull and Dimension of QAPn.- 7.2 Some Valid Inequalities for QAPn.- 7.3 The Affine Hull and Dimension of SQPn.- 8 Solving Small QAPs.- A Fortran Programs for Small SQPs.- References.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions