Heuristic Based Algorithms Explained

by Shaun Snapp on December 30, 2010

What This Article Covers

  • What is a heuristics based algorithm?
  • How can a heuristic be compared against an algorithm?
  • What is a meta-heuristic?

Background

This post documents an email discussion between myself and Wayne Fu regarding heuristic based algorithms.

Question for Wayne Fu

What is a heuristic based optimization algorithm? I thought that heuristics were one form of problem solving, and optimization was another. How is a heuristic based algorithm is different from a non-heuristic based algorithm? That would help me and readers out a lot. - Shaun Snapp

_____________________________

Answer:

Optimization can be classified as deterministic and stochastic, while all inputs are a constant in deterministic optimization. Inventory related optimization is definitely stochastic, since the demand is never been a constant, but a given distribution. The most classic optimization method in deterministic is linear programming.

Another name for stochastic is meta-heuristic. Meta-heuristic is a vast topic and used very broadly, because it is much more flexible, contingent, and even could yield better result than deterministic methods while inputs are deterministic.

Heuristics in Major Solvers

Like ILOG’s CPlex, they are very powerful linear programming solvers, but eventually when it tries to determine a solution, it uses heuristics. i2 Technologies used to use CPlex in master planning to provide draft outcomes, and then MAP as the heuristics solver to fine-tune the solution.

A Metaphor for Comparing Heuristic Versus Optimization

One extremely simplified way to see the deterministic and heuristics is like searching for a house. Using a deterministic approach would be like zooming out to a couple thousand miles always from earth, and then picking a location you think is best by giving all the criteria you can check at that distance. Then heuristics would be like standing in front of a train station, start asking the people around or checking local newspaper to figure out where is the better place to live. Then you move over there, check around again and narrow the scope further down or even jump out to next place.

Meta-Heuristics

So, inventory optimization is meta-heuristic. In METRIC, it is basically using margin analysis as the criteria of heuristic. (for more on METRIC see this post)

http://www.scmfocus.com/servicepartsplanning/2010/12/30/important-service-part-multi-echelon-inventory-optimization-books/

It starts by searching the for the part which provides best value to increase its inventory, then next one, then next one in the believe that we will stop at some point and that will be the optimal inventory position overall.

__________________________________

Follow Up Comment from Shaun: I think one of the complicating factors in understanding the difference between heuristics and optimization is that they are often taught as separate methods. A generalization is that an optimizer has an objective function, while a heuristic does not. However, in practice and in many important foundational research papers, in fact heuristics are combined with optimization. I think you provided a very good explanation of meta-heuristics. It enables a person who reads METRIC (an acronym for Sherbrooke’s foundational Multi-Echelon Technique for Recoverable Item Control), to understand it much better.

___________________________________

Author Thanks:

I wanted to thank Wayne Fu for his contribution.

Interviewee Profile

Wayne Fu is a Senior Product Management in Servigistics. With operation management background, Wayne has worked in service part planning domain for more than a decade. In Servigistics, he led the research and development of various areas like install-base (provisioning) forecasting, inventory optimization and distribution planning. Currently, he is focusing on the effectiveness of forecast techniques in Last Time Buy.

 

Shaun Snapp

Shaun Snapp is a long time supply chain planning software consultant, author & as well as the Managing Editor at SCM Focus. He focuses on both SAP APO as well as best of breed applications for demand, supply and production planning.

Previous post:

Next post: