Stochastic Optimization

1. Front Matter

   Pages I-XVI

   PDF

2. Theory Overview of Stochastic Optimization Algorithms

   1. Front Matter

      Pages 1-1

      PDF

   2. General Remarks

      Pages 3-7

   3. Exact Optimization Algorithms for Simple Problems

      Pages 9-13

   4. Exact Optimization Algorithms for Complex Problems

      Pages 15-29

   5. Monte Carlo

      Pages 31-42

   6. Overview of Optimization Heuristics

      Pages 43-47

   7. Implementation of Constraints

      Pages 49-51

   8. Parallelization Strategies

      Pages 53-57

   9. Construction Heuristics

      Pages 59-61

   10. Markovian Improvement Heuristics

       Pages 63-67

   11. Local Search

       Pages 69-72

   12. Ruin & Recreate

       Pages 73-77

   13. Simulated Annealing

       Pages 79-88

   14. Threshold Accepting and Other Algorithms Related to Simulated Annealing

       Pages 89-102

   15. Changing the Energy Landscape

       Pages 103-113

   16. Estimation of Expectation Values

       Pages 115-118

   17. Cooling Techniques

       Pages 119-134

   18. Estimation of Calculation Time Needed

       Pages 135-136

   19. Weakening the Pure Markovian Approach

       Pages 137-141

Our purpose in writing this book was to provide a compendium of stochastic optimizationtechniques,someguidesto wheneachisappropriateinpractical situations, and a few useful ways of thinking about optimization as a p- cess of search in some very rich con?guration spaces. Each of us has come to optimization, traditionally a subject studied in applied mathematics, from a background in physics, especially the statistical physics of random m- tures or materials. One of us (SK) has used ideas developed in the study of magnetic alloys to explore the optimal placement of computer circuits s- ject to many con?icting constraints, while at IBM Research, in Yorktown Heights, NY. The other (JJS) while completing his studies in physics under Prof. Ingo Morgenstern in Regensburg, Germany, and working at the IBM Scienti?c Center Heidelberg, was exposed to optimization problems as varied as scheduling the pickup of fresh milk and planning automobile assembly line schedules. We had the opportunity to work together after SK moved from IBM to a professorship at The Hebrew University of Jerusalem, Israel, and JJS was, for a year, a postdoc there. JJS has taught a course on stochastic optimization at the University of Mainz, where his students have used p- tions of the present manuscript. We hope to make this material readable by undergraduates, and useful to graduate students and practitioners as well, in computer science, applied mathematics, physics, and economics. Mainz, April 2006 JohannesJosefSchneider Jerusalem, April 2006 ScottKirkpatrick Contents Part I Theory Overview of Stochastic Optimization Algorithms 0 General Remarks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

• Constraint Satisfaction
• Markov
• Monte Carlo
• Random Numbers
• Simulated Annealing
• Stochastic Optimization
• Tabu Search
• Traveling Salesman Problem
• algorithm
• algorithms
• construction
• genetic algorithms
• optimization

From the reviews:

"The book is devoted to stochastic global optimization methods. … The book is primarily addressed to scientists and students from the physical and engineering sciences but may also be useful to a larger community interested in stochastic methods of global optimization." (A. H. Žilinskas, Mathematical Reviews, Issue 2007 i)

"This book provides a rich collection of stochastic optimization algorithms and heuristics that cope with optimization issues. … In summary, this is a good book on stochastic optimization. It is important book of any engineering library or laboratory. In my opinion, this book may be used as a quick reference for sophisticated scholars, or as an introductory book for students who are interested in an overview of the state-of-the-art mechanisms in this field." (Wei Yen, Computing Reviews, December, 2007)

"This book presents a compendium of Stochastic Optimisation concerned with the use of heuristics mainly including Markov Chain Monte Carlo methods. It is divided into 3 parts. … 216 references are listed. They cover the main existing results in the theme. I consider that an outstanding feature of the book is its successful synthesis of giving in an ‘altogether’ curve information needed for being comfortable with the realms of heuristic algorithms. I warmly recommended it for specialists working in optimization." (Carlos Narciso Bouza Herrera, Zentralblatt MATH, Vol. 1116 (18), 2007)

• Institut für Physik Fachbereich 08 Physik, Mathematik und Informatik, Johannes Gutenberg-Universität Mainz, Mainz, Germany

  Johannes Josef Schneider

• The Selim and Rachel Benin School of Engineering and Computer Science, The Hebrew University of Jerusalem, Jerusalem, Israel

  Scott Kirkpatrick

Policies and ethics