The journey continues – the target being the best of both worlds

In our blog series “Custom Heuristics vs Standard Solvers” we have presented the various strategies available in order to solve an optimization problem. These are custom heuristics on the one hand and mathematically precise procedures deploying standard solvers on the other. Deciding to what extent a specific strategy is appropriate to solve a given optimization problem requires a great deal of empirical skill. When it comes to solving complex problems in particular, our OR team never fails to demonstrate its expertise. And sometimes the result is a combination of both solution procedures as shown here in “The Best of Both Worlds”, the third part of our blog series.

 Trekking through mountains and valleys

Let us first sum up the facts of both solution strategies. An optimization problem is solved by optimizing its target function. If we take a look at the target function – in consideration of parameters – it constitutes a range of mountains and valleys. The optimization is the search for the highest peak (the maximum), or for the deepest valley (the minimum). The path towards the solution thus depends on the topology of the mountain range and also on whether a local optimum is considered to be a sufficiently good solution or whether the global optimum is being searched. Should, from one point, the next local maximum (highest peak) or minimum (lowest valley) be found in the vicinity, custom heuristics provide a sufficiently good solution. Should, however, the absolute maximum (highest peak) or the absolute minimum (lowest peak) be determined, then we are talking about a global optimization. The search for the global and proven optimum is implemented by mathematically precise procedures and by deploying standard solvers. However, the computing time for the guaranteed global optimum cannot be foreseen. When which solution method is the better one greatly depends first of all on the topology of the target function but just as much on the attainable solution quality and the resulting computing time.

The Best of Both Worlds – the combination leads to the result

A multitude of real optimization problems cannot merely be solved  by one of the two strategies we have mentioned; i.e. custom heuristics or mathematically precise procedures with solvers. Bearing in mind the attainable solution quality  and the resulting computing time complex planning problems require a procedure that is specific to the problem. So how can a challenging problem be solved? A combination of both solution procedures can yield the desired result.

Combination 1 – construction heuristics and standard solvers

“Turn a big problem into a small one and small ones into none at all”. This Chinese proverb forms the first approach towards solving complex optimization problems: In the first stage, the problem is broken down into partial problems where construction heuristics are deployed first of all, such as the random or greedy procedure (see Custom Heuristics vs Standard Solvers: Part I – Custom Heuristics). The following factors are taken into consideration – often as domain knowledge – when it comes to breaking down a problem:

  •  Time (continuous or hierarchical planning; general and detailed planning)
  • Geography (countries or regions)
  • The structure of product ranges or production (products or product groups)
  •  A network in view of assembly stages and added value (pre-assembly to final assembly)

When breaking down a problem, individual factors are not always considered independently of one another. For example, timing is combined with the geographical aspects. Thus, general planning is initially performed by construction heuristics according to territories (countries). The detailed planning comes next. In this way, a real problem can be approached by uncertainty in modeling. The result is a model that is suited to a standard solver. Consequently, a rapid optimization of the partial problem is possible by deploying mathematically precise procedures (see Custom Heuristics vs Standard Solvers Part II – mathematical optimization procedures with a standard solver). The results yielded are at best optimal or almost optimal and therefore reliably assessable to a great extent.

 Breaking down the Alps

We were also able to break down our trek through the mountains according to this principle and therefore structure our search for the highest peak in view of geopgraphical aspects. If we planned our mountain trek through the Alps, we would have to consider 8 countries in its breakdown. For each country the search for the highest peak could be implemented as detailed planning deploying standard solvers. However, one thing has always been clear ever since the Alps were surveyed in the 19th century: Mont Blanc, which is 4,810 meters high, is the highest mountain in the Alps – that is the proven global optimum, so to speak. In this case, however, it wasn’t mathematics that yielded this result but cartographical surveyance.

Combination 2 –  Improvement Heuristics and Standard Solvers

A far more seldom combination is that of improvement heuristics and mathematically precise procedures so that the exact procedure is used internally to assess the solution. One example here is the deployment of Genetic Algorithms (GAs) as heuristics together with standard solvers in order to solve challenging optimization problems such as the following question in network planning: “Which facility location should be opened?”

This type of problem immediately contains two decision criteria –  the question regarding the location but also the question of how much the respective locations produce – which need to be considered when assessing a loaction and its effects (e.g. the total costs of production and logistics).
Genetic algorithms are overtaxed by this complex question. Dividing the problem into primary and sub-problems can help to solve it: An example of a good question which can be modeled for this primary problem is: “Which of the locations under consideration best meet the stipulated requirements (decision criteria)?” The primary problem decides which of the locations can be opened and can be solved with the aid of GAs.

The fitness function is evaluated for each individual which is synonymous with a solution to a primary problem. This no longer needs to consider the location decision as it has already been made by GA. The solver solves the sub-problem in view of the cost evaluation and thus provides an answer to the question “How does the location decision affect production and logistic costs?” The heuristics of the primary problem assess the solutions of the sub-problems and ultimately choose the best solution.

Diagramm Best of Both Worlds

Diagram – The Best of Both Worlds

So we can say that complex planning problems can be divided between custom heuristics and solvers: Each does what it does best and you get the best of both worlds.

Custom Heuristics and Standard Solvers

This blog entry shows that turning the “versus” into an “and” can be the way to achieving the best solution results. Our blog entry entitled “Custom Heuristics vs Standard Solvers” explains both solution strategies in more detail. Read the following two blogs again as a prequel to this entry:
Custom Heuristics vs Standard Solvers: Part I – Custom Heuristics
Custom Heuristics vs Standard Solvers: Part II Mathematical Optimization Procedures with Standard Solvers

Thanks to their many years of experience in this field, our OR experts can evaluate which solution strategy is the most suitable, even in the case of complex optimization problems and also when to turn a “versus” into an “and”.

Other topics you may find interesting…