- What is a heuristic algorithm and how can a heuristic be compared against an algorithm as well as what is a meta-heuristic?
Introduction to Heuristic Algorithms
This post documents an email discussion between myself and Wayne Fu regarding the heuristic algorithm.
Question for Wayne Fu
“What is a heuristic based optimization algorithm, or a heuristic algorithm?
I thought that heuristics were one form of problem solving, and optimization was another. How is a heuristic based algorithm or heuristic algorithm different from a non-heuristic based algorithm? That would help me and readers out a lot.” – Shaun Snapp
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 a better result than deterministic methods while inputs are deterministic.
Heuristics in Major Solvers
Like ILOG’s CPlex, they are very robust 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 a 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 of 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.
So, inventory optimization is meta-heuristic. In METRIC, it is using margin analysis as the criteria of heuristic.
It starts by searching the for the part which provides the best value to increase its inventory, the next one, the next one in the belief that we will stop at some point and that will be the optimal inventory position overall.
Most people who work in this area are familiar with the term heuristics, but much less so with the term “metaheuristics.” Metaheuristics are important for problems that are computationally infeasible to solve with optimization.
In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces of candidate solutions. However, metaheuristics do not guarantee an optimal solution is ever found. Many metaheuristics implement some form of stochastic optimization. – Wikipedia
Optimization is a word with a number of meanings. In operations research, it means to meet an objective function, usually within some constraints. To the laymen, optimization has often been used to mean to “improve.” To many people, it is considered normal that optimization is always possible, or that finding an optimal solution is always possible. However, that is not the case. Some problems, of course, are not worth optimizing and some problems are so complex that they don’t bear optimization easily. This leads to an interesting quote.
In this book we refer to evolutionary algorithms and metaheuristics as improvement methods. In standard business software finding the optimum of a nonlinear or hard to solve problem is often approached by using evolutionary algorithms /iterated search which – after a pre-set maximum calculating time – in a wide variety of cases encountered in business optimization return an acceptable solution in a vicinity of a local optimum (hopefully) close to the global optimum. – Real Optimization in SAP APO
This describes methods that while they do not result in an optimal result, can get reasonably close to the global optimum.
However, in practice and many important foundational research papers, in fact, heuristics are combined with optimization. I think you provided an excellent 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.
I wanted to thank Wayne Fu for his contribution.
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.
“Real Optimization with SAP APO,” Josef Kallrath, Thomas I. Maindl, Springer Press, 2006
Intermittent Demand and Service Parts Databases
Our Solution for Managing Intermittent Demand
The number of service parts companies that actually use service parts software is small. We offer some of the most important features of managing service parts in an easy to use SaaS application that can be used to improve the management of any ERP system for service parts. It’s free until it receives “serious usage” and is free for students and academics to access. Select the image below to find out more.