One Problem, Four Algorithms: What a Controlled Heuristic Comparison Revealed

Hill Climbing, Simulated Annealing, Tabu Search, and solver-based approaches such as Fix-and-Optimize are often presented individually, each with its own strengths and limitations. But this raises a more practical question: 

What happens when several of these methods are implemented for exactly the same optimization problem and tested under the same conditions?

I explored this question in my doctoral thesis using a particularly difficult production-planning problem: the Multi-Level Capacitated Lot-Sizing Problem with stochastic demand and random yield.

The results showed that selecting an optimization method is not simply a matter of finding the algorithm with the lowest objective value. Solution quality, feasibility, runtime, scalability, and robustness can point to different winners.

The Planning Problem

In a multi-level production system, finished products depend on components and intermediate products. A shortage at one production level can therefore propagate through the entire bill of materials. The problem becomes even more difficult when production yield is uncertain. A planned lot of 100 units may produce fewer than 100 usable units. If this happens to a component, the shortage may prevent the production of its successor products.

The planning model consequently had to consider:

• multiple products and production levels,
• limited production capacity,
• setup and inventory costs,
• stochastic demand,
• random production yield,
• positive lead times,
• and required service levels.

Even the deterministic version of this problem belongs to a computationally difficult problem class. Adding uncertainty and service-level constraints makes exact optimization considerably harder.

The Solution Methods

I implemented and compared four approaches.

Hill Climbing

Hill Climbing evaluates the neighborhood of the current production plan and accepts the best improving move. It is simple and fast, but stops when no directly improving solution can be found. Its main weakness is therefore well known: it can become trapped in a local optimum.

Simulated Annealing

Simulated Annealing also uses local changes, but it can temporarily accept worse solutions. Early in the search, this happens relatively frequently. As the temperature decreases, the algorithm becomes more selective. This allows the method to leave local optima and explore other regions of the solution space.

Tabu Search

Tabu Search maintains a memory of recently executed moves. These moves are temporarily forbidden, preventing the algorithm from repeatedly returning to the same solutions. Like Simulated Annealing, Tabu Search can move to a worse solution in order to escape a local optimum. However, it evaluates the complete available neighborhood in each iteration.

Fix-and-Optimize

Fix-and-Optimize divides the mathematical model into smaller subproblems. A subset of the setup decisions is optimized while the remaining decisions are fixed. This retains more of the structure of the mathematical model, but each subproblem must still be solved by a mathematical solver.

A Controlled Comparison

The heuristics were tested on 600 randomly generated problem instances with up to 10 products, 20 planning periods and different capacity utilization levels.

All local-search methods used the same initial solution, solution representation, neighborhood moves, cost calculation, and service-level penalties. This was important: the experiment compared the search strategies rather than entirely different implementations.

The Results

No method dominated every performance dimension.

• Simulated Annealing found the lowest-cost solutions
• Hill Climbing found feasible solutions most reliably
• Tabu Search satisfied the service-level requirements most accurately
• Fix-and-Optimize reached its scalability limit for the dataset

The Practical Recommendation

The results suggest a simple algorithm portfolio:

1. Start with Simulated Annealing for solution quality.
2. Restart it if no feasible solution is found.
3. Use Hill Climbing as a reliable fallback.
4. Reserve Fix-and-Optimize for small instances.

The best method depends on whether cost, feasibility, service-level accuracy, or runtime matters most.

Conclusion

No method dominated every criteria. Simulated Annealing achieved the lowest costs, while Hill Climbing found feasible solutions most reliably. The broader lesson is clear: metaheuristics should be compared on the actual problem under consistent conditions. In practice, combining complementary algorithms may be better than searching for one universal winner.