Optimality is a red herring

For most realistic real world situations, optimality is neither achievable nor desirable [1]. Optimality is really a “red herring” in the sense that it has little relevance. Some reasons are:

• Optimal solutions are usually out of reach: A strongly believed conjecture from the area of computational complexity implies that for certain problems optimality cannot be computed easily, even by smart algorithms [2]. Even for modestly sized problems, solutions can't be found in human time. Unfortunately, many realistic industrial optimization challenges belong to this class of problem.
  
  
• Even feasible solutions may be out of reach: Forget about optimality.
  
  
• Optimal solutions are usually brittle: Take, for instance, the problem of minimizing the makespan of a schedule (which is the duration from when the very first task in the schedule starts until the very last ends). If we are allocating our resources smartly we can pack the tasks tightly together (and thereby substantially reduce the makespan). However, such schedules are not robust to changes since there is little or no buffer between the tasks to absorb changes. The moment a task takes longer to finish than planned or a resource shows up too late, then the whole schedule falls apart.
  
  
• Real situations usually have more than one objective: Optimization is conceptually straightforward when you, for instance, want to create an operational schedule that maximizes production. But assume that you want to maximize production and minimize cost. What are you optimizing on? Clearly, these two objectives are pulling in different directions. The more you increase production, the more cost you are likely to incur. Shut down production, and you have minimized cost. The solution is a balance between the two objectives that could be context dependent and can't always be formalized.
  
  
• Optimality is usually not well defined: Usually, companies don't fully know what constitutes an optimal solution. They may recognize good solutions, but it is often hard for them to explain fully why they are good or to give them an absolute ranking. It is a waste of time to chase optimality if optimality is not well defined.
  
  
• Optimality is usually a moving target: In operational environments, it is meaningless to spend an hour or the whole night chasing optimality if the situation changes faster than it takes to propose solutions. What you rather need are good solutions fast.
  
  

Chasing rainbows is good

Optimality is a red herring, but that does not mean that optimization is. Quite the contrary. Chasing rainbows can have great value. Optimality may be out of reach, but we should still strive for finding as good solutions as possible in the time we have available.

For the industrial challenges that we are addressing here at Actenum, there is a diminishing return on chasing optimality. Our philosophy is that it is more important (for many industrial environments) to find good solutions right now than highly optimized solutions tomorrow. “Providing good solutions fast” sounds so simple while being so challenging. Most operational replanning and rescheduling is challenged with cumulative complexities and a huge number of possible combinations. However, if you intend your decision support tool to optimize on key performance indicators in real time or useful time in an operational environment, you have to be clever about which technologies you can apply.

This philosophy brings strong directions to the development of our core technologies. Our optimization algorithms are looking at how we can bring the most “bang for the buck” or value improvement, in the shortest possible time. This is illustrated in the following graph:

The graph shows what happens when we run one of our optimization algorithms for about four minutes (this particular graph is a typical example of a single run of one of the many objective functions in Actenum's rig fleet management system, more concretely the transportation cost minimization function in Actenum RAS 2.0). The graph shows the improvement in the objective function over time when running an optimization algorithm. The x-axis gives time in seconds. The y-axis is the improvement in the objective function. There are several points to notice:

1. It is an anytime algorithm. You can stop the optimization whenever you will, and you will have a solution.
   
   
2. The longer you run it the better solutions you are likely to get.
   
   
3. We get quite strong improvements—25-30% over standard dispatch methods.
   
   
4. The algorithm provides very strong improvements very fast. On these data, we get 5-10% improvement in transportation cost within ten seconds.

Below I have annotated the graph by adding a horizontal line that indicates a hypothetical maximally possible improvement. I have also indicated a point in time where the user has stopped the algorithm (the vertical dashed line).

The question here is really “Does reducing Delta1 have a higher business value than reducing Delta2?”, or in other words, “Where is the best balance between time to find a solution and the value of that solution?”. The answer to this is context dependent, we therefore leave it to the user to decide how long they will run the optimization. Actenum's optimization technologies makes this possible, allowing good solutions fast when that is required.

These methods are not guaranteed to find optimal solutions. However, the methods give you solutions of very high value very fast, and far better than what humans or non-optimization techniques can achieve.

You get something good when you're chasing rainbows.

Notes

[1] In mathematics and computer science, an optimization problem relates to finding a “best solution” from all feasible solutions:

• A feasible solution does not violate any of the declared constraints.
• A best solution is found by ranking the possible solutions, where an objective function determines a solution's rank.
• An objective is what you want to optimize, for instance “minimize transportation cost“. So, a typical objective function might rank solutions according to transportation cost.

[2] Most industrial problems belong to classes of problems that are known as NP-hard. Mathematically, such problems can not be computed in time that is polynomial or better in the size of its input. For many problems, finding optimality may take more time than the estimated remaining time of the universe.