Number 42

 The journey continues …

The rule for every optimization problem is to find the best solution strategy. This is not always easy, as our blog series “Custom Heuristics vs Standard Solvers” shows. However, our OR team of specialists never fails to demonstrate its experience, above all when it comes to solving complex problems.

In the first part of our blog series we focused on solution procedures using a Custom Heuristics approach. In this entry, we’ll be taking a look at how optimization problems can be solved analytically with the aid of mathematics by deploying standard solvers. Both solution strategies have their advantages and can be excellently combined to solve complex optimization problems. We will give you a brief overview of this in the third part of our series titled “Custom Heuristics vs Standard Solver: Part 3 – the best of both worlds“.

When are standard solvers deployed?

Solvers are computer programs which solve mathematical problems. In particular they are supported by linear programming (LP), quadratic programming (QP) and mixed integer linear programming (MILP). Mathematically precise procedures are particularly suitable for solving these kinds of problems. Many real problems can be approximated with a lack of precision in modeling. The result is a model which suits the solver and which is thus convenient for rapid optimization using mathematically precise procedures.

Computing time and gap

The algorithms of standard solvers guarantee an optimal solution which has also been proven –  hence, the proven optimum. However, the comupting time for this cannot be predicted, unfortunately. And this is where the gap comes in! After a short computing time, standard solvers provide a solution and, in addition, an assessment of its quality.A gap is an indication of how good the optimum is:  a gap of 5% means that the global optimum of 0% to 5% is better than the solution that is known at the time but we don’t know where the optimal solution is located in this range – we only know the upper limit which has been mathematically proven. When assessing the gap, the following also needs to be taken into consideration:

  • The assessment is dependent on the values that are deployed and therefore on a case-by-case assessment
  • The lack of precision in the data needs to be considered
  •  A large gap is of little to no use
  • If the curve of the gap is asymptotic, this can be a sign of a very good solution and all that remains is to find evidence of it.

 The knapsack problem or: “How do I pack the car for my road trip through Europe?”

Let us now transfer the facts on solvers to the Knapsack Problem, in other words to the question we already posed in our blog Custom Heuristics, namely: How can I best pack my car for my European road trip?” Let’s imagine the following scenario: The mathematically exact method deploying a standard solver might provide me with a solution  with a guaranteed gap of 0.1% after a computing time of just two minutes. However, we don’t know the computing time for a better solution or for the evidence of this solution as an optimum. Do I now want to close the gap and perhaps wait for several more years? In addition, as mentioned earlier, we cannot ignore the uncertainty in the data: Have I estimated the benefit of the umbrella, sunhat and down jacket correctly and measured the sizes precisely? Or do I ultimately come to the conclusion that I can get by with an uncertainty of 0.1% and that I can now start my road trip as planned and not when I retire?

A journey to the galaxy

In the next optimization problem our journey will be even more fantastic than our road trip through Europe: In the novel (or travel guide) “The Hitchhiker’s Guide to the Galaxy”, the super computer Deep Thought says that 42 “is quite definitely the answer”. This answer is the proven global optimum to the question “of Life, the Universe and everything“. So we can asusme that Deep Thought had deployed a solver for his calculation because an optimum can never be proven with heuristics. Not even after 7.5. million years – the computing time that Deep Thought needed to come up with the answer 42 as a proven optimum.

Fun Fact

If the interstellar hitchhiker follows the travel guide’s tips, he doesn’t have to bother with the Knpasack Problem  (described in Custom Heuristics vs Standard Solvers- Part I): It is said that a towel is the most massively useful thing you can have (For this reason Towel Day is held annually on the 25th May in remembrance of the author, Douglas Adams. On this day, fans around the universe carry a towel in his honour.

Normally, though, the answer could have been (after a computing time of maybe two hours instead of 7.5 million years): The best solution to date is 42.2 with a guaranteed gap of 1%. This answer would have shown that the proven optimum (as a minimum) lies between 41.778 and 42.2. We (still) don’t know exactly where and it has not been proven. But to wait 7.5 million years for proof? Even at this early stage it would be clear that the answer 42 is meaningless.

Conclusion to a mathematically exact procedure with a standard solver

There is no doubt that mathematical optimization with standard solvers can be deployed for suitable models. For these so-called Performance Models, optimization is rapid and optimal – or almost optimal – results are delivered with certainty. In addition to this, there is also a gap based on tried and tested technology.

This tried and tested technology does have its price – in the form of license fees. However, these costs are offset against a transparent implementation workload as well as a low project risk (after a short proof of concept) and a short project duration.

Custom Heuristic vs Standard Solver?

Custom Heuristics and standard solvers in comparison: If you would like to learn more about custom heuristics and their deployment, read our blog entry  Custom Heuristics vs Standard-Solvers: Part I – Custom Heuristics. Are you also interested in how we turn the “vs” into an “and”? If you would like to learn more on how both solution procedures can be combined, read Custom Heuristics vs Standard Solvers: Part III – The Best of Both Worlds

Would you like to benefit from the wealth of experience our OR specialists have gained?

They choose the best solution strategy, even for complex optimization problems.

Other topics you may find interesting…