Stochastic Optimization Book

Theory
Overview of Stochastic Optimization Algorithms
General Remarks     3
Why Optimize Things?     3
Moral Aspects of Optimization     4
How To Think About It     5
Minima, Maxima, and Extrema     6
What Is So Hard About Optimization?     6
Algorithms, Heuristics, Metaheuristics     7
Exact Optimization Algorithms for Simple Problems     9
A Simple Example-Exact Optimization in One Dimension     9
Newton-Raphson Method     10
Descent Methods in More Than One Dimension     12
Conjugate Gradients     13
Exact Optimization Algorithms for Complex Problems     15
Simplex Algorithm     15
Integer Optimization     20
Branch & Bound     21
Branch & Cut     24
Monte Carlo     31
Pseudorandom Numbers     31
Random Number Generation and Random Number Tests     32
Transformation of Random Numbers     37
Example: Calculation of [pi] with MC     42
Overview of Optimization Heuristics     43
Necessity of Heuristics     43
Construction Heuristics     44
Markovian Improvement Heuristics     45
Set-Based Improvement Heuristics     46
Implementation of Constraints     49
Moves, Constraints, Deadlines     49
Incorporation into the Configurations     49
Consideration of Feasible Solutions Only     50
Penalty Functions     50
Parallelization Strategies     53
Parallelization Models and Computer Architectures     53
Running Several Copies     54
Divide et Impera     54
Information Exchange     56
Construction Heuristics     59
General Outline of Construction Heuristics     59
Insertion Heuristics     60
Savings Heuristics     61
More Intelligent Ways of Construction     61
Markovian Improvement Heuristics     63
Constructing a Markov Chain     63
Trivial Acceptance Functions     64
Introduction of a Control Parameter     65
Heat Bath Approach     66
Local Search     69
Classic Local Search Approach     69
Problems of the Local Search Approach     70
Larger Moves     70
Jumping Between Different Move Sizes     71
Ruin & Recreate     73
The Philosophy of Building One's Own Castle     73
Outline of Approach     73
Discussion of Ruin & Recreate     76
Ruin & Recreate as a Self-Contained Optimization Algorithm     77
Simulated Annealing     79
Physical and Historical Background     79
Derivation of Simulated Annealing     81
Thermal Expectation Values     85
Inverse Simulated Annealing     88
Threshold Accepting and Other Algorithms Related to Simulated Annealing     89
Threshold Accepting     89
The Steady-State Equilibrium Characteristics of TA     91
Methods Based on the Tsallis Statistics     96
The Great Deluge Algorithm     100
Changing the Energy Landscape     103
Search Space Smoothing     103
Ant Lion Heuristics and Activation Relaxation Technique     108
Noising or Permutation of System Parts     111
Weight Annealing     112
Estimation of Expectation Values     115
Simple Sampling     115
Biased Sampling     115
Importance Sampling     116
Parallel Sampling     117
Cooling Techniques     119
Standard Cooling Schedules      119
Nonmonotonic Cooling Schedules     122
Ensemble Based Schedules     126
Simulated Tempering and Parallel Tempering     130
Estimation of Calculation Time Needed     135
Exponentially Growing Space Size     135
Polynomial Approach     135
Grest Hypothesis     135
Weakening the Pure Markovian Approach     137
Saving the Best-So-Far Solution and Spinoffs at Good Solutions     137
Record-to-Record Travel     138
Stochastic Tunneling     139
Changing the Cooling Schedule Due to Intermediate Results     139
Neural Networks     143
Biological Motivation     143
Artificial Neural Networks     145
The Hopfield Model     149
Kohonen Networks     154
Genetic Algorithms and Evolution Strategies     157
Charles Darwin's Natural Selection     157
Mutations and Crossovers     158
Application to Optimization Problems     161
Parallel Applications     166
Optimization Algorithms Inspired by Social Animals     169
Inspiration by the Behavior of Animals     169
Ant Colony Optimization     169
Particle Swarm Optimization     171
Fighting and Ranking     172
Optimization Algorithms Based on Multiagent Systems     175
Motivation     175
Simulated Trading     176
Selfish vs. Global Optimization     178
Introduction of a Social Temperature     179
Tabu Search     181
Tabu     181
Use of Memory     182
Aspiration     183
Intensification and Diversification     183
Histogram Algorithms     185
Guided Local Search     185
Multicanonical Algorithm     186
MUCAREM and REMUCA     192
Multicanonical Annealing     192
Searching for Backbones     193
Comparing Different Good Solutions     193
Determining the Backbone     194
Outline of the SFB Algorithm     195
Discussion of the Algorithm     196
Applications
General Remarks     201
Dealing with a Proposed Optimization Problem     201
Programming Languages and Parallelization Libraries     202
Optimization Libraries     204
Difficulty of Comparing Various Algorithms     205
The Traveling Salesman Problem
The Traveling Salesman Problem     211
The Task of the Traveling Salesman     211
Distance Metrics     211
The Dijkstra Algorithm     212
Various Possible Codings     215
Four Approaches to the TSP     218
Benchmark Instances     219
Bounds for the Optimum Solution     223
The Misfit: A Frustration Measure     225
Order Parameters for the TSP     226
Short History of TSP     229
Extensions of Traveling Salesman Problem     233
Temporal Constraints     233
Vehicle Routing Problems     234
Probabilistic Models and Online Optimization     239
Supply Chain Management     240
Application of Construction Heuristics to TSP     243
Nearest Neighbor Heuristic     243
Insertion Heuristics     246
Using Deeper Insight into the Problem     251
The Savings Heuristic     255
Local Search Concepts Applied to TSP     263
Initialization Routine     263
Small Moves     265
Computational Results for Greedy Algorithm     269
Local Search as Afterburner for Construction Heuristics     272
Next Larger Moves Applied to TSP     275
Lin-3-Opts     275
Higher-Order Lin-n-Opts     277
Computational Results for the Greedy Algorithm     283
Combination of Moves of Various Sizes     285
Ruin & Recreate Applied to TSP     287
Application of Ruin & Recreate     287
Analysis of R & R Moves in RW and GRE Modes     290
Ruin & Recreate as Self-Contained Algorithm     294
Discussion of Application Possibilities of Ruin & Recreate     296
Application of Simulated Annealing to TSP     299
Simulated Annealing for the TSP     299
Computational Results for Observables of Interest     302
Computational Results for Acceptance Rates     306
Quality of the Results Achieved with Various Computing Times     310
Dependencies of SA Results on Moves and Cooling Process     315
Results for Various Small Moves     315
Results for Monotonous Cooling Schedules     318
Results for Bouncing     324
Results for Parallel Tempering     334
Application to TSP of Algorithms Related to Simulated Annealing     341
Computational Results for Threshold Accepting     341
Computational Results for Penna Criterion      347
Computational Results for Great Deluge Algorithm     350
Computational Results for Record-to-Record Travel     359
Application of Search Space Smoothing to TSP     367
A Small Toy Problem     367
Gu and Huang Approach     369
Effect of Numerical Precision on Smoothing     383
Smoothing with Finite Numerical Precision Only     386
Further Techniques Changing the Energy Landscape of a TSP     389
The Convex-Concave Approach to Search Space Smoothing     389
Noising the System     397
Weight Annealing     399
Final Remarks on Application of Changing Techniques     403
Application of Neural Networks to TSP     405
Application of a Hopfield Network     405
Computational Results for the Hopfield Network     407
Application of a Kohonen Network     408
Computational Results for a Kohonen Network     409
Application of Genetic Algorithms to TSP     415
Mutations     415
Crossovers     416
Natural Selection     419
Computational Results     420
Social Animal Algorithms Applied to TSP     423
Application of Ant Colony Optimization      423
Computational Results     426
Application of Bird Flock Model     428
Computational Results     429
Simulated Trading Applied to TSP     431
Application of Simulated Trading to the TSP     431
Computational Results     435
Discussion of Simulated Trading     438
Simulated Trading and Working     438
Tabu Search Applied to TSP     441
Definition of a Tabu List     441
Introduction of Short-Term Memory     444
Adding some Aspiration     445
Adding Intensification and Diversification     445
Application of History Algorithms to TSP     449
The Multicanonical Algorithm     449
Multicanonical Annealing     452
Acceptance Simulated Annealing     455
Guided Local Search     464
Application of Searching for Backbones to TSP     471
Definition of a Backbone     471
Application to the Completely Asymmetric TSP     475
Application to Partially Asymmetric TSP     477
Computational Results     478
Simulating Various Types of Government with Searching for Backbones     489
An Aristocratic Approach     489
A Democratic Approach     491
Solution of the PCB442 Problem     492
Can Humans Do This, Too?     496
The Constraint Satisfaction Problem
The Constraint Satisfaction Problem     501
Sources of Constraint Satisfaction Problems     501
Benchmarks and Competitions     503
Randomly Generated Models and Their Complexity     504
Randomly Generated Models and Their Phase Diagrams     506
Mixtures of easy and hard CSPs     510
Construction Heuristics for CSP     513
Application of the Bestinsertion Heuristic to the 3-SAT Problem     513
Assertion, Decimation, and Resolution     517
Analyzable Assertion Protocols     517
Solution Space Structure of XOR-SAT     519
Random Local Iterative Search Heuristics     523
RWalkSAT     523
WalkSAT     524
Simulated Annealing     526
Belief Propagation and Survey Propagation     529
Belief Propagation, Message Passing, and Cavities     529
Message Passing as Side Information for Decimation     531
Belief Propagation and Sudoku     534
Outlook
Future Outlook of Optimization Business     539
P = NP?     539
Quantum Computing     540
DNA Computing     541
How Will the Problems Evolve?     544
Acknowledgments     547
References     551
Index     563