Chapter 6. Optimization Algorithms

6.1. Search Space Size in the Real World

The number of possible solutions for a planning problem can be mind blowing. For example:
  • 4 queens has 256 possible solutions (4^4) and 2 optimal solutions.
  • 5 queens has 3125 possible solutions (5^5) and 1 optimal solution.
  • 8 queens has 16777216 possible solutions (8^8) and 92 optimal solutions.
  • 64 queens has more than 10^115 possible solutions (64^64).
  • Most real-life planning problems have an incredible number of possible solutions and only 1 or a few optimal solutions.
For comparison: the minimal number of atoms in the known universe (10^80). As a planning problem gets bigger, the search space tends to blow up really fast. Adding only 1 extra planning entity or planning value can heavily multiply the running time of some algorithms.
Calculating the number of possible solutions depends on the design of the domain model:
Note
This search space size calculation includes infeasible solutions (if they can be represented by the model), because:
  • The optimal solution might be infeasible.
  • There are many types of hard constraints which cannot be incorporated in the formula practically. For example in Cloud Balancing, try incorporating the CPU capacity constraint in the formula.
Even in cases were adding some of the hard constraints in the formula is practical, for example Course Scheduling, the resulting search space is still huge.
An algorithm that checks every possible solution (even with pruning such as in Branch And Bound) can easily run for billions of years on a single real-life planning problem. What we really want is to find the best solution in the limited time at our disposal. Planning competitions (such as the International Timetabling Competition) show that Local Search variations (Tabu Search, Simulated Annealing, Late Acceptance, ...) usually perform best for real-world problems given real-world time limitations.