Advanced Algorithms and Data Structures

17 Simulated annealing: Optimization beyond local minima

This chapter covers

• Introducing simulated annealing
• Using simulated annealing to improve delivery schedules
• Presenting a primer on the traveling salesman problem
• Using simulated annealing for minimum crossing embeddings
• Using an algorithm based on simulated annealing to draw graphs nicely

If you have read chapters 15 and 16, you should by now be familiar with graph embeddings and optimization problems. In the previous chapter, in particular, we explained how to reformulate graph embedding as an optimization problem, and we introduced gradient descent, an optimization technique that can be used to find (near-)optimal solutions to this category of problems. In particular, we discussed ...