How to Best Understand a Heuristic Algorithm for Service Parts

Table of Contents: Select a Link to be Taken to That Section

Executive Summary

What is a heuristic algorithm, and how can a heuristic be compared against an algorithm, and 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

The Answer

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 that is deterministic is linear programming.

heuristic-based-algorithm 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, it uses heuristics when it tries to determine a solution. 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, asking the people around, or checking local newspapers to figure out where is the better place to live. Then you move over there, check around again, narrow the scope further down, or even jump out to the next location.

Meta-Heuristics

So, inventory optimization is meta-heuristic. METRIC, it is using margin analysis as the criteria of heuristic.

It starts by searching for the part that provides the best value to increase its inventory, the next one, the next one believing 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?

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 can get reasonably close to the global optimum while they do not result in an optimal result.
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 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.

Author Thanks:

I wanted to thank Wayne Fu for his contribution.

Interviewee Profile

Wayne Fu is a Senior Product Management in Servigistics. Wayne has worked in the service part planning domain with an operation management background 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.

References

“Real Optimization with SAP APO,” Josef Kallrath, Thomas I. Maindl, Springer Press, 2006