Computer Science and Operations Research: New Developments in their Interfaces (eBook)

Osman Balci (Autor)

eBook Download: PDF

2014 | 1. Auflage
548 Seiten
Elsevier Science (Verlag)
978-1-4832-9786-6 (ISBN)

Infos

The interface of Operation Research and Computer Science - although elusive to a precise definition - has been a fertile area of both methodological and applied research. The papers in this book, written by experts in their respective fields, convey the current state-of-the-art in this interface across a broad spectrum of research domains which include optimization techniques, linear programming, interior point algorithms, networks, computer graphics in operations research, parallel algorithms and implementations, planning and scheduling, genetic algorithms, heuristic search techniques and data retrieval.

Inhalt

Front Cover 1
Computer Science and Operations Research: New Developments in Their Interfaces 4
Copyright Page 5
Table of Contents 6
Preface 10
Referees 12
PART I: OPTIMIZATION TECHNIQUES 14
Chapter 1. A Principled Approach to Solving Complex Discrete Optimization Problems 16
Abstract 16
Keywords 16
INTRODUCTION AND BACKGROUND 17
DESCRIPTION OF OPL 18
A BENCHMARK OF OPL ALGORITHMS 25
EXTENDING AND MERGING PROBLEMS 27
OTHER OPL APPLICATIONS 31
CONCLUSIONS 32
BIBLIOGRAPHY 33
CHAPTER 2. BOOLEAN-COMBINATORIAL BOUNDING OF MAXIMUM 2-SATISFIABILITY 36
ABSTRACT 36
KEYWORDS 36
1. Maximum 2-satisfiability problems and their reducibility 36
2. Connections with roof-duality 38
3. Elementary boolean operations 39
4. Squeezing out constants by fusions and exchanges 42
5. Equivalence between reducibility and squeezability 46
6. Improving the lower bound by consensus and condensations 50
REFERENCES 54
CHAPTER 3. NAVAL PERSONNEL ASSIGNMENT: AN APPLICATION OF LINEAR-QUADRATIC PENALTY METHODS 56
ABSTRACT 56
KEYWORDS 56
INTRODUCTION 56
THE NAVAL PERSONNEL ASSIGNMENT PROBLEM 57
APPLICATION OF THE LINEAR-QUADRATIC PENALTY METHOD TO NAVAL PERSONNEL ASSIGNMENT 61
NUMERICAL RESULTS 65
CONCLUSIONS 70
REFERENCES 70
Chapter 4. Preprocessing Schemes and a Solution Method for the Convex Hull Problem in Multidimensional Space 72
ABSTRACT 72
KEY WORDS 72
INTRODUCTION 72
1. BACKGROUND 73
2. DEFINITIONS, NOTATION AND IMPORTANT TERMS 74
3. FIRST STAGE: PREPROCESSING 74
4. SECOND STAGE: RESOLUTION 77
5. THE FRANK-WOLFE ALGORITHM FOR FINDING PROJECTIONS 78
6. IMPLEMENTATION AND COMPUTATIONAL RESULTS 80
7. CONCLUSIONS 82
REFERENCES 83
PART II: LINEAR PROGRAMMING INTERIOR POINT ALGORITHMS 84
CHAPTER 5. ADAPTING THE INTERIOR POINT METHOD FOR THE SOLUTION OF LINEAR PROGRAMS ON HIGH PERFORMANCE COMPUTERS 86
ABSTRACT 86
KEY WORDS 86
HARDWARE PLATFORMS FOR THE SPARSE SIMPLEX AND THE INTERIOR POINT METHOD 86
CHOICE OF INTERIOR POINT METHOD 91
PARALLEL SSPD SOLVER KERNEL ON A DISTRIBUTED MEMORY COMPUTER 92
THE SSPD SOLVER KERNEL ON THE DAP COMPUTER 94
DISCUSSION AND CONCLUSIONS 97
ACKNOWLEDGEMENTS 98
REFERENCES 98
CHAPTER 6. IMPLEMENTATION OF AN INTERIOR POINT LP ALGORITHM ON A SHARED-MEMORY VECTOR MULTIPROCESSOR 100
ABSTRACT 100
KEYWORDS 100
INTRODUCTION 100
A PRIMAL-DUAL LP ALGORITHM 101
THE CHOLESKY DECOMPOSITION 103
IMPLEMENTATION 104
COMPUTATIONAL EXPERIENCE 109
CONCLUSIONS 112
ACKNOWLEDGEMENTS 113
REFERENCES 113
PART III: NETWORKS 116
CHAPTER 7. ALTERNATE SERVER DISCIPLINES FOR MOBILE-SERVERS ON A CONGESTED NETWORK 118
ABSTRACT 118
KEYWORDS 118
1. INTRODUCTION 118
2. FORMULATION 120
3. SERVER DISCIPLINES 121
4. RELATED THEORY 124
5. CONCLUSIONS 127
6. REFERENCES 127
CHAPTER 8. COLLISION DEPENDENT PERFORMANCE MODEL FOR A STAR TOPOLOGY LOCAL AREA NETWORK 130
ABSTRACT 130
KEYWORDS 130
INTRODUCTION 130
THE HUBNET PROTOCOL 131
FORMULATION OF THE COLLISION DEPENDENT MODEL 131
CONCLUSIONS 139
REFERENCES 139
CHAPTER 9. GREEDY RECOGNITION AND COLORING ALGORITHMS FOR INDIFFERENCE GRAPHS 140
ABSTRACT 140
KEYWORDS 140
1. INTRODUCTION 140
2. BASICS 141
3. GREEDY ALGORITHMS 146
4. CONCLUSION AND OPEN PROBLEMS 149
ACKNOWLEDGEMENT 149
REFERENCES 149
CHAPTER 10. MINIMUM GRAPH VERTEX COVERING WITH THE RANDOM NEURAL NETWORK 152
ABSTRACT 152
KEYWORDS 152
INTRODUCTION 152
RANDOM NETWORK SOLUTION 155
CONCLUSIONS 159
REFERENCES 159
CHAPTER 11. MULTIPLE CLASS G-NETWORKS 162
ABSTRACT 162
KEYWORDS 162
INTRODUCTION 163
CUSTOMER FLOW EQUATIONS AND PRODUCT-FORM 166
CONCLUSIONS AND OPEN PROBLEMS 169
REFERENCES 170
CHAPTER 12. ON IMPLEMENTING AN ENVIRONMENT FOR INVESTIGATING NETWORK RELIABILITY 172
ABSTRACT 172
KEYWORDS 172
1. NETWORKS AND RELIABILITY 172
2. SYSTEM REQUIREMENTS 173
3. SOME EXAMPLES 176
4. EXACT COMPUTATIONS 180
5. SUMMARY OF IMPROVEMENTS 185
ACKNOWLEDGEMENTS 186
REFERENCES 186
PART IV: COMPUTER GRAPHICS IN OPERATIONS RESEARCH 188
CHAPTER 13. ANIMATED SENSITIVITY ANALYSIS 190
ABSTRACT 190
KEYWORDS 190
1. INTRODUCTION 190
2. RELATED RESEARCH 191
3. EXAMPLES OF ANIMATED SENSITIVITY ANALYSIS 193
4. A FRAMEWORK FOR ANIMATED SENSITIVITY ANALYSIS 200
5. CONCLUSION AND RESEARCH DIRECTIONS 205
REFERENCES 206
CHAPTER 14. EDINET - A NETWORK EDITOR FOR TRANSSHIPMENT PROBLEMS WITH FACILITY LOCATION 210
ABSTRACT 210
KEY WORDS 210
INTRODUCTION 210
THE PROBLEM AND DATA MODEL 213
LOCAL WINDOWS 215
GLOBAL WINDOWS 218
CONCLUDING REMARKS 223
REFERENCES 224
CHAPTER 15. FUNCTIONAL DESCRIPTION OF A GRAPH-BASED INTERFACE FOR NETWORK MODELING (GIN) 226
ABSTRACT 226
KEYWORDS 226
INTRODUCTION 226
CURRENT MODELING ENVIRONMENTS 227
OVERALL SYSTEM DESIGN AND ARCHITECTURE 229
MODEL BUILDING WITH GIN 231
WINDOWS Icons 233
EXAMPLE PROBLEM 234
IMPLEMENTATION AND CURRENT STATUS 237
CONCLUSIONS 240
ACKNOWLEDGEMENTS 241
BIBLIOGRAPHY 241
CHAPTER 16. NETPAD: AN INTERACTIVE GRAPHICS SYSTEM FOR NETWORK MODELING AND OPTIMIZATION 244
ABSTRACT 244
KEYWORDS 244
OVERVIEW 244
NETPAD ENVIRONMENT 246
USING NETPAD 247
CUSTOMIZING NETPAD 250
NETPAD ARCHITECTURE 251
POTENTIAL USES OF NETPAD 252
SOME EXISTING SYSTEMS 253
NETPAD AVAILABILITY 255
ACKNOWLEDGMENT 255
PART V: PARALLEL ALGORITHMS AND IMPLEMENTATIONS 258
CHAPTER 17. A CONCURRENT COMPUTING ALGORITHM FOR REAL-TIME DECISION MAKING 260
ABSTRACT 260
KEYWORDS 260
INTRODUCTION 260
THE PRODUCTION SCHEDULING PROBLEM 262
THE GENERIC SCHEDULER 267
CONCLUSIONS AND FUTURE DIRECTIONS 277
ACKNOWLEDGEMENTS 278
REFEENCES 278
CHAPTER 18. COMPUTATIONAL EXPERIENCE WITH PARALLEL ALGORITHMS FOR SOLVING THE QUADRATIC ASSIGNMENT PROBLEM 280
ABSTRACT 280
KEYWORDS 280
INTRODUCTION 280
PARALLEL ALGORITHMS 282
COMPUTATIONAL RESULTS 285
REFERENCES 289
CHAPTER 19. ON REPORTING THE SPEEDUP OF PARALLEL ALGORITHMS: A SURVEY OF ISSUES AND EXPERTS 292
ABSTRACT 292
KEYWORDS 292
INTRODUCTION 292
REPORTING OF COMPUTATIONAL TESTING 293
ISSUES IN REPORTING THE RESULTS OF PARALLEL TESTING 295
A SURVEY OF EXPERTS 297
CONCLUSIONS 305
ACKNOWLEDGMENTS 305
REFERENCES 306
CHAPTER 20. OPTIMAL PARALLEL ALGORITHMS FOR COMPUTING A VERTEX OF THE LINEAR TRANSPORTATION POLYTOPE 308
ABSTRACT 308
KEYWORDS 308
INTRODUCTION 308
AN OPTIMAL SEQUENTIAL ALGORITHM 311
AN OPTIMAL PARALLELIZATION OF THE NORTHWEST-CORNER RULE FOR THE CREW PRAM 312
AN OPTIMAL PARALLEL SOLUTION TO THE VECTOR COMPOSITION PROBLEM ON THE EREW PRAM 316
AN OPTIMAL PARALLELIZATION OF THE NORTHWEST-CORNER RULE FOR THE EREW PRAM 318
ACKNOWLEDGEMENT 318
REFERENCES 319
CHAPTER 21. PARALLEL DECOMPOSITION OF MULTICOMMODITY FLOW PROBLEMS USING COERCION METHODS 320
ABSTRACT 320
KEYWORDS 320
INTRODUCTION 320
DECOMPOSITION OF MULTICOMMODITY NETWORK FLOWS USING COERCION METHODS 321
PARALLEL COMPUTING USING COERCION FUNCTIONS 323
ANALYTIC MODELS OF PARALLEL PERFORMANCE 326
COMPUTATIONAL RESULTS 328
CONCLUSIONS 330
REFERENCES 330
PART VI: PLANNING AND SCHEDULING 332
CHAPTER 22. A GRAPH-THEORETIC MODEL FOR THE SCHEDULING PROBLEM AND ITS APPLICATION TO SIMULTANEOUS RESOURCE SCHEDULING 334
ABSTRACT 334
KEYWORDS 334
INTRODUCTION 334
THE SCHEDULING MODEL 336
MULTIPROCESSOR SCHEDULING 343
PARALLEL I/O SCHEDULING 344
SCHEDULING WITH MUTUAL EXCLUSION CONSTRAINTS 348
SCHEDULING IN PARALLEL I/O BUS ARCHITECTURES 353
CONCLUSIONS 358
ACKNOWLEDGEMENTS 359
REFERENCES 359
CHAPTER 23. INTELLIGENT MODELLING, SIMULATION AND SCHEDULING OF DISCRETE PRODUCTION PROCESSES 362
ABSTRACT 362
KEYWORDS 362
INTRODUCTION 362
JOB SHOP PROBLEMS: DEFINITION AND OVERVIEW 363
I-MASSA ARCHITECTURE 364
THE MODEL BUILDER 364
SIMULATOR 367
EVALUATOR MANIPULATOR 369
FUTURE RESEARCH 374
CONCLUDING REMARKS 374
ACKNOWLEDGEMENTS 375
REFERENCES 375
Chapter 24. OOFP–Object Oriented Flow Planning 376
ABSTRACT 376
KEYWORDS 376
1 PROBLEM 377
2 MODEL 378
3 EQUATIONS 382
4 IMPLEMENTATION 388
5 EXAMPLE 391
6 CONCLUSIONS 394
REFERENCES 395
CHAPTER 25. ROMAN: AN INTEGRATED APPROACH TO MANPOWER PLANNING AND SCHEDULING 396
ABSTRACT 396
KEYWORDS 396
1. INTRODUCTION 396
2. THE ROMAN APPROACH 397
3. THE SPECIFICATION MODULE 401
4. TOE ALLOCATION MODULE 403
5. THE SCHEDULING MODULE 405
6. THE ROSTER DESIGN MODULE 407
7. CONCLUDING REMARKS 408
REFERENCES 408
PART VII: GENETIC ALGORITHMS 410
CHAPTER 26. apGA: AN ADAPTIVE PARALLEL GENETIC ALGORITHM 412
ABSTRACT 412
KEYWORDS 412
INTRODUCTION 412
DECEPTIVENESS 413
GENETIC ALGORITHMS 414
TEST FUNCTIONS AND RESULTS 418
SUMMARY AND FUTURE RESEARCH 420
REFERENCES 420
CHAPTER 27. GENETIC ALGORITHMS FOR THE TRAVELING SALESMAN PROBLEM WITH TIME WINDOWS 424
ABSTRACT 424
KEYWORDS 424
INTRODUCTION 424
TRAVELING SALESMAN PROBLEM WITH TIME WINDOWS 425
EXPERIMENTAL PROCEDURES 426
EARLIEST CLOSING TIME CROSSOVER OPERATOR 427
EVALUATION FUNCTION 431
TEST PROBLEMS 431
EXPERIMENTAL RESULTS 431
CONCLUSIONS 435
REFERENCES 435
CHAPTER 28. INCREASED FLEXIBILITY IN GENETIC ALGORITHMS: THE USE OF VARIABLE BOLTZMANN SELECTIVE PRESSURE TO CONTROL PROPAGATION 438
ABSTRACT 438
KEYWORDS 438
1. INTRODUCTION 438
2. THEORY 439
3. PRACTICE 441
4. DISCUSSION 447
5. CONCLUSION 453
REFERENCES 453
CHAPTER 29. PARALLEL GENETIC ALGORITHMS IN COMBINATORIAL OPTIMIZATION 454
ABSTRACT 454
KEYWORDS 454
INTRODUCTION 454
EVOLUTIONARY AND GENETIC ALGORITHMS 455
THE SEARCH STRATEGY OF THE PGA 457
THE TRAVELING SALESMAN PROBLEM 458
PERFORMACE EVALUATION FOR THE TSP 459
THE GRAPH PARTITIONING PROBLEM 461
PERFORMACE EVALUATION FOR THE GPP 463
CONCLUSION 464
REFERENCES 465
PART VIII: HEURISTIC SEARCH TECHNIQUES 468
CHAPTER 30. CONSTRAINT-DIRECTED SEARCH FOR THE ADVANCED REQUEST DIAL-A-RIDE PROBLEM WITH SERVICE QUALITY CONSTRAINTS 470
ABSTRACT 470
KEYWORDS 470
INTRODUCTION 470
THE DIAL-A-RIDE SYSTEM 471
THE ALGORITHM 474
COMPUTATIONAL RESULTS 482
CONCLUDING REMARKS 486
REFERENCES 487
CHAPTER 31. HEURISTIC SOLUTION PROCEDURES FOR THE GRAPH PARTITIONING PROBLEM 488
ABSTRACT 488
KEYWORDS 488
INTRODUCTION 488
PROBLEM FORMULATION 489
THE EXTENDED LOCAL SEARCH PROCEDURE 490
A GENETIC ALGORITHM FOR THE GRAPH PARTITIONING PROBLEM 491
SUMMARY AND CONCLUSION 502
REFERENCES 503
CHAPTER 32. NEW EJECTION CHAIN AND ALTERNATING PATH METHODS FOR TRAVELING SALESMAN PROBLEMS 504
ABSTRACT 504
KEYWORDS 504
1. INTRODUCTION 504
2. A STEM-AND-CYCLE REFERENCE STRUCTURE 505
3. CHAINS FOR EJECTING TOUR SUBPATHS 505
4. A CONNECTION TO ALTERNATING PATHS 511
5. FUNDAMENTAL STEM-AND-CYCLE RULES 511
6. ASYMMETRIC TRAVELING SALESMAN PROBLEMS 516
7. PARALLEL PROCESSING AND DIYIDED-STEM-AND-CYCLE STRUCTURES 518
CONCLUSION 520
ACKNOWLEDGEMENT 520
REFERENCES 521
PART IX: DATA RETRIEVAL 524
CHAPTER 33. ENHANCING DATA RETRIEVAL USING ARTIFICIALLY SYNTHESIZED QUERIES 526
ABSTRACT 526
KEYWORDS 526
I. INTRODUCTION 527
II. FUNDAMENTALS AND NOTATION 530
III. DISTRIBUTION CHANGING FILTERS 532
IV. CASCADING DCT FILTERS 538
V. EXPERIMENTAL RESULTS 542
VI. CONCLUSIONS 543
ACKNOWLEDGEMENTS 544
REFERENCES 544
AUTHOR INDEX 546
SUBJECT INDEX 547

Produkt-Details

• Erscheint lt. Verlag: 23.5.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Naturwissenschaften
• Themenwelt: Technik
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Planung / Organisation
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Unternehmensführung / Management
• ISBN-10: 1-4832-9786-1 / 1483297861
• ISBN-13: 978-1-4832-9786-6 / 9781483297866