Many Travel Images Collage

“Where the journey is headed” or “a short preview of our blog series Custom Heuristics vs Standard Solvers”

Various strategies are available to solve an optimization problem. Choosing the right solution process for a specific problem requires a great deal of experience. When it comes to solving complex problems in particular, our OR team never fails to demonstrate its expertise.

Our blog series “Custom Heuristics vs Standard Solvers” looks at the range of aspects which influence the choice of the right solution strategy thus outlining how complex it is to decide on a solution procedure. In this first entry we focus on custom heuristics as a practicable alternative to mathematically precise optimization procedures during which optimization problems are calculated analytically with the aid of mathematics. This optimization process is also known as an optimization procedure with standard solvers and will be described in more detail in our next blog entry. A third entry will focus on the “best of both worlds”, thus rounding off the topic of “Custom Heuristics vs Standard Solvers”.

 Does every journey start with problems?

Let’s imagine you are planning to visit the most beautiful cities in Europe by car. You can choose the cities you want to go to and whether it will just be a short trip or a longer break is also entirely up to you. However, one thing is clear: in order to enjoy the journey and see as much of the cities as you can, you want to spend as little time as possible sitting in your car. (Sometimes we could say that “roads were made for journeys, not destinations”, but that’s for another day…) So, the question is: which route should you take that would require the least journey time and therefore be the fastest? This problem, which is known as the Traveling Salesman Problem (TSP), is a typical optimization problem which can be found in all kinds of real-life challenges:

  • In investment planning: “Which location expansion is the most feasible after all the logistic aspects have been taken into consideration?”
  • In route planning: “How do I plan the optimal route for my deliveries?”
  • In production planning: “What is the best job-queuing sequence for my machine scheduling?”

But going back to your journey through Europe… Before the journey can begin, you have a further problem; you need to pack the car. It doesn’t matter whether you are going in a small car, a sedan or a van. At some point, the trunk is full to the brim. So now you have to wor out what you really need for your journey, that is: what is more important – the umbrella when you walk around London? The down jacket for your stay in wintry Oslo? Or maybe the summer hat for your stroll through Sevilla?

This problem is known as the knapsack problem and, just like the TSP, it can be transferred to a real-life situation. Thanks to the solution to this optimization problem, many real-life challenges  can be clarified mathematically. For example, the reference to logistics is evident if you ask:  “How can I load my truck with goods of different value and sizes in order to gain maximum profit  with regard to capacity?”

Solving problems with algorithms and experience

Algorithms are used to solve real problems such as the TSP or Knapsack Problem, but which algorithms are suitable for which optimization problem? Is a custom heuristic more appropriate or would the algorithm of a standard solver be better?

Many factors influence the choice of algorithms. For example:

  • the structure of the problem to be solved
  • the amount of possible solutions
  • the time and effort required for formulating and modeling
  • the available domain knowledge
  • the time aspect of the planning situation
  • and of course the solution itself:
    Is a “good” solution sufficient – with the knowledge that better solutions could be found, if necessary, or is the objective a proven “optimal” solution?

Every optimization problem is to be considered individually with regard to these aspects: All of the above-mentioned factors are considered and weighed up in order to choose the best solution strategy for the optimization problem. Our OR team of specialists has the relevant experience in this respect and is therefore ideal when it comes to finding the right strategy.

The problem becomes a model

Several of the factors mentioned above already influence the modeling of the optimization problem and are therefore a step in the right direction even before the model has been created. The fundamental challenge in modeling is to translate a real issue or problem into the language of mathematics in order to first obtain a mathematical problem that can be solved with mathematical methods (read more about this in our blog Why OPTANO Modeling?) However, the accuracy of the description is up against the complexity of a model and the performance involved.

Therefore, it is clear that these factors and their impacts should be precisely weighed up against and with one another in order to make decisions in view of suitable solution strategies.

 When are custom heuristics deployed?

Every optimization problem comes with a range of possible solutions or a solution space (also known as a search space). Custom heuristics is an approach which is deployed to find an approximate solution to an optimization problem or an associated optimization model but it employs a practical method where there is no guarantee that the solution will be optimal. In other words, you don’t know whether the solution is the best one or whether better ones exist. Instead, it serves as an approximate solution which is acceptable for immediate goals. In order to find a “sufficiently good” result, you have to differentiate between construction heuristics and improvement heuristics.

Construction heuristics

Construction heuristics serve to determine a (initial) feasible solution because you can construct a good permissible point (high objection function value).  This occurs by successively determining solution elements.

Possible construction heuristics:

  • Random procedure (randomization)
  • Greedy procedure/Greedy algorithm
  • Future-oriented process
Greedy algorithm

Let us take a closer look at the Greedy algorithm which is a good example of construction heuristics. This algorithm gradually processes the problem by constructing part solutions which deliver the best result at a respective time. It “greedily” finds a local optimal solution at every step (without having to reset). The advantage of the greedy algorithm is its runtime as it quickly leads to a “sufficiently good” solution. The disadvantage is that it fails to consider previous solutions which may have been better. Therefore, the result is rarely an optimal solution.

The result: The greedy procedure is a plausible algorithm which leads to a good result, in particular when so-called domain knowledge (knowledge of the problem and experience values) is included during its creation.

Improvement heuristics

Improvement heuristics are local search procedures and are used when a feasible starting solution has been determined, for examplle by means of construction heuristics. Improvement heuristics lead to improved (locally optimal) solutions by means of successive solution transformations or “clever” experimenting.

Possible improvement heuristics are:

  • Genetic algorithm
  • Simulated annealing
  • Ant algorithm
Genetic Algorithm

Genetic algorithms (GA) are a good example of improvement heuristics. These algorithms are particularly suitable for problems where their structure is rather unknown and where the amount of possible solutions is very large. Genetic algorithms are inspired by the biological theory of evolution and genetics (hence the terminology): Adapting to changed environmental conditions is interpreted as an optimization problem and the evolution is the solution accordingly.
GAs asume the strategy of evolution to solve problems; new generations (of solution proposals) are produced and changed and combined – by mutation and crossover – until a “sufficiently good” solution has been found.

Result: GAs do not always provide the optimal solution to a problem. A sub-optimal solution cannot be overcome if the changes – brought about by mutation and crossover – are not strong enough. A further point of criticism is the high calculating time caused by constantly producing new generations . If the approximate solution proves to be acceptable, however, then the runtime does not greatly outweigh procedures with mathematical precision that apply standard solvers. In addition, the time required for formulating and modeling is extremely low for genetic algorithms.

Image Custom Heuristics

Diagram – Custom Heuristics

Summary of custom heuristics

An optimal solution involving a justifiable amount of time and effort is often difficult to attain for complex optimization problems such as the Traveling Salesman Problem and the Knapsack Problem. In most cases, a sub-optimal solution is sufficient; this means a local optimum which is close enough to the global optimum. Thus, deploying custom heuristics is a practicable alternative as long as a “sufficiently good” solution is acceptable; that is, if you acknowledge that you don’t know whether better solutions could be found. Bearing in mind that this “trial and error” procedure contains a higher error rate,  custom heuristics still offers the following advantages:

As an approximate solution custom heuristics generally have a short runtime, even with a large solution space. This is strengthened by available domain knowledge which can flow into the model to depict the reality. Basically, modeling with custom heuristics allows more freedom (in comparison to the standard solver for which a linear optimization model is a requirement). This enables a more precise depiction of reality, uncertainty is reduced. Furthermore, the reality can often be portrayed in smaller models because a detailed linearization of non-linear contexts is required. This, in turn, leads to an increase in performance.

Last but not least, there is also the aspect of lower licensing fees. These costs, however, must be compared with those involved in the individual (custom) implementation.

Custom Heuristics vs Standard Solver?

A comparison requires at least one alternative. For this reason you will learn more about mathematically precise procedures that apply standard solvers in our next OPTANO blog entry.

Do you want to benefit from the vast experience of our OR specialists? They find the best solution strategy even for complex optimization problems.

Other topics you may find interesting….