- 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 constant in deterministic optimization. Inventory related optimization is stochastic since the demand is never 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 the 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 location.
So, inventory optimization is meta-heuristic. In METRIC, it is using margin analysis as the criteria of heuristic.
It starts by searching 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 several meanings. In operations research, it means to meet an objective function, usually within some constraints. To the laymen, optimization has often been used to indicate 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 issues 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 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 an operation management background, Wayne has worked in the 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.
What We Do and Research Access
Using the Diagram
Hover over each bullet or plus sign to see more explanation. To move to a different bullet point, just “hover off” and then hover over the new bullet.
“Real Optimization with SAP APO,” Josef Kallrath, Thomas I. Maindl, Springer Press, 2006