Relaxation §

Date created: 2022-07-21

It’s a strategy often used in computer science, where you make a problem easier by, for example, removing constraints. Then you try to solve the easier problem before moving onto the more difficult one.

If you can’t solve the problem in front of you, solve an easier version of it–and then see if that solution offers you a starting point, or a beacon, in the full-blown problem. Maybe it does.

Chapter notes §

• A minimum spanning tree is a useful benchmark for route problems
  • Traveling salesman problem
  • Constraint Relaxation
  • Continuous Relaxation
  • Lagrangian Relaxation

---

References §

• Chapter 8 in Algorithms to live by