Nonlinear Assignment Problems: Algorithms and Applications

Front Cover
Panos M. Pardalos, Leonidas Pitsoulis
Springer Science & Business Media, Nov 30, 2000 - Computers - 304 pages
Nonlinear Assignment Problems (NAPs) are natural extensions of the classic Linear Assignment Problem, and despite the efforts of many researchers over the past three decades, they still remain some of the hardest combinatorial optimization problems to solve exactly. The purpose of this book is to provide in a single volume, major algorithmic aspects and applications of NAPs as contributed by leading international experts.
The chapters included in this book are concerned with major applications and the latest algorithmic solution approaches for NAPs. Approximation algorithms, polyhedral methods, semidefinite programming approaches and heuristic procedures for NAPs are included, while applications of this problem class in the areas of multiple-target tracking in the context of military surveillance systems, of experimental high energy physics, and of parallel processing are presented.
Audience: Researchers and graduate students in the areas of combinatorial optimization, mathematical programming, operations research, physics, and computer science.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

MULTI INDEX ASSIGNMENT PROBLEMS COMPLEXITY APPROXIMATION APPLICATIONS
1
11 TECHNICAL PRELIMINARIES
2
22 THE PLANAR 3IAP
5
MIAPS
6
EXTENSIONS
8
MULTIDIMENSIONAL ASSIGNMENT PROBLEMS ARISING IN MULTITARGET AND MULTISENSOR TRACKING
11
PROBLEM BACKGROUND
13
ASSIGNMENT FORMULATION OF SOME GENERAL DATA ASSOCIATION PROBLEMS
15
11 PRELIMINARIES
140
EIGENVALUE TYPE BOUNDS
143
21 HOMOGENEOUS QAP
144
22 PERTURBATIONS
149
23 PROJECTED EIGENVALUE BOUND
150
24 STRENGTHENED PROJECTED EIGENVALUE BOUND
152
25 TRUST REGION TYPE BOUND
153
SDP RELAXATIONS
154

MULTIPLE FRAME TRACK INITIATION AND TRACK MAINTENANCE
20
41 TRACK INITIATION
21
ALGORITHMS
23
52 THE LAGRANGIAN RELAXATION ALGORITHM FOR THE ASSIGNMENT PROBLEM
25
53 THE LINEAR PROGRAMMING DUAL
29
54 LAGRANGIAN DECOMPOSITION AND OTHER TRANSFORMATIONS
30
55 IMPROVEMENT METHODS
31
62 FRAMES OF DATA
32
TARGETBASED WEAPON TARGET ASSIGNMENT PROBLEMS
37
STATIC ASSIGNMENT MODELS
38
21 UNIFORM WEAPONS
40
THE DYNAMIC ASSIGNMENT MODEL
42
32 STOCHASTIC DEMAND PROBLEMS
44
THE NONLINEAR ASSIGNMENT PROBLEM IN EXPERIMENTAL HIGH ENERGY PHYSICS
53
14 DATA ASSOCIATION
55
16 RECONSTRUCTION ANALYSIS
56
22 OPTIMAL NONLINEAR PARAMETER ESTIMATION
57
24 EXTENDED KALMAN FILTERING
58
25 CONVENTIONAL DATA RECONSTRUCTION METHODS
59
3 THE HIGH ENERGY PHYSICS TRACKING PROBLEM
61
33 DETECTOR LAYOUT
62
34 JUSTIFYING A GLOBAL DATA ASSOCIATION ALGORITHM
65
35 SIMPLIFICATIONS
67
4 COMBINATORIAL TRACK RECONSTRUCTION
68
42 TRACK RECONSTRUCTION IN THE ITC
69
43 TRACK RECONSTRUCTION IN THE INNER VERTEX REGION
72
IMPLEMENTATION
76
52 TRACK RECONSTRUCTION IN THE INNER REGION
78
CONCLUDING REMARKS
80
POLYHEDRAL METHODS FOR SOLVING THREE INDEX ASSIGNMENT PROBLEMS
87
21 FACET CLASS Q
91
23 FACET CLASS B
92
24 FACET CLASS C
93
LINEARTIME SEPARATION ALGORITHMS FOR FACETS
94
32 A LINEARTIME SEPARATION ALGORITHM FORP1
95
34 A LINEARTIME SEPARATION ALGORITHM FOR P2
98
35 A LINEARTIME SEPARATION ALGORITHM FORB 2
99
A POLYHEDRAL METHOD
100
OPEN QUESTIONS
101
POLYHEDRAL METHODS FOR THE QAP
105
POLYTOPES ASSOCIATED WITH THE QAP
115
THE STARTRANSFORMATION
120
FACIAL DESCRIPTIONS OF QAPPOLYTOPES
122
CUTTING PLANE ALGORITHMS FOR QAPS
128
CONCLUSION
131
SEMIDEFINITE PROGRAMMING APPROACHES TO THE QUADRATIC ASSIGNMENT PROBLEM
139
31 LAGRANGIAN RELAXATION
155
32 GEOMETRY OF THE RELAXATION
160
33 THE GANGSTER OPERATOR
163
34 INEQUALITY CONSTRAINTS
165
CONCLUSION
166
HEURISTICS FOR NONLINEAR ASSIGNMENT PROBLEMS Stefan Voss
171
FINDING INITIAL FEASIBLE SOLUTIONS
174
IMPROVEMENT PROCEDURES
175
32 GRASP
176
34 TABU SEARCH
177
35 GENETIC ALGORITHMS
178
36 ANT SYSTEMS
180
42 THE MULTIINDEX ASSIGNMENT PROBLEM
190
43 THE BIQUADRATIC ASSIGNMENT PROBLEM
192
44 MISCELLANEOUS
193
52 MISCELLANEOUS
198
SYMBOLIC SCHEDULING OF PARAMETERIZED TASK GRAPHS ON PARALLEL MACHINES
213
INTRODUCTION
214
DEFINITIONS AND NOTATIONS
215
OVERVIEW OF THE SLC METHOD
218
SYMBOLIC LINEAR CLUSTERING
220
CLUSTER IDENTIFICATION
223
MULTITHREADED EXECUTION OF CLUSTERS
226
SIMULATION AND EXPERIMENTAL RESULTS
227
RELATED WORK
230
CONCLUSIONS
232
DECOMPOSITION ALGORITHMS FOR COMMUNICATION MINIMIZATION IN PARALLEL COMPUTING
241
11 THE MINIMUM PERIMETER PROBLEM
242
THE DECOMPOSITION COORDINATION FRAMEWORK
250
22 OPTIMAL SUBPROBLEM SOLUTIONS TO MP
252
STRIPE DECOMPOSITION
256
32 Extension to 3D Domains
268
SNAKE DECOMPOSITION
269
THE SNAKE DECOMPOSITION ALGORITHM
270
43 EXTENSIONS TO 3D DOMAINS AND NONUNIFORM GRIDS
274
PARALLEL GENETIC ALGORITHMS
275
51 THE GA MODEL
276
52 HANDLING CONSTRAINTS
279
53 PARALLEL GA MODELS
280
A DISTRIBUTED GA
281
COMPUTATIONAL RESULTS
284
62 RECTANGULAR GRIDS
285
63 THE KNAPSACK APPROACH
287
64 NONRECTANGULAR GRIDS
288
CONCLUSIONS AND FUTURE DIRECTIONS
291
Copyright

Other editions - View all

Common terms and phrases