I don't know about you, but my experience is that all customers want the best solution to their business problem.  And they want it rapidly, within some given time limit.  I can't blame them, I do the same when I am the customer.

 

However, if we have finite computing resources then there is a limit to what can be computed.  If the business problem is so complex that it can't be solved exactly in the given time limit, then optimization won't compute the best possible solution (one among the optimal ones).  What it will compute are good feasible solutions, as measured by the objective value.

 

I'm pretty sure you will agree that I am not stating anything new here.  So, what is it I want to blog about today?

I want to revisit the assumption that a better objective value always means a better solution in customer eyes. 

 

To understand why, let us look at a customer experience of mine.  This particular customer had to schedule plant operations while minimizing cost.  We modeled the scheduling problem as a mathematical optimization problem.  It turned out to be a quite difficult problem, and we were not able to solve it to optimality within the time limit set by the customer.  Fortunately we did found a feasible solution.  That solution wasn't optimal as we stopped the optimization process before completion.  However, it was a good solution, better than the customer solution at least.  This is depicted in figure 1.

 

 Figure 1.  Two solutions to a cost minimization problem.  A lower objective value means a lower cost solution.

 

The optimized solution had a better objective value (read, a lower cost), hence it was better than the customer solution.  We were quite confident the customer would be happy when we would present our result.

It turned out that the customer wasn't impressed at all by our solution.  Indeed, she found a way to improve it by switching two jobs.  The mere fact that there was an easy improvement to our solution made it look poor even if it had a much lower cost.  The customer reasoning was: it can't be a good solution because it is easily improved by hand.  Note that the correct mathematical reasoning should have been: it is not an optimal solution because it can be improved.  Our solution could be improved (see figure 2) because we stopped the optimization process before completion. 

 

 

Figure 2.  A third solution of the minimization problem obtained by a small modification of the optimized solution.

 

The fact that a customer isn't happy with a better solution is striking, isn't it?  What's even more surprising is that I've had many similar experiences, in many different industry sectors.  The reasoning was always the same: a solution can't be good if it is easily improved. 

I've discussed it with colleagues, trying to understand why customers weren't convinced by the objective value alone.  In the end I came to a simple conclusion: Customers value solutions that are locally optimal.  For instance, if we depict the feasible region as in figure 3, then the customer solution is a local minimum while the optimized solution is not.  The former was valued while the latter was not, despite a better objective value.  Better wasn't better there!

 

 

 

Figure 3.  The feasible region is above the curve.

 

The cure to this is quite simple fortunately.  Before showing a solution to the customer, try easy improvement schemes.  It will ensure that the optimization process outputs solutions that aren't easily improved.  It can be done as a post processing step using some local search for instance. One can also do it each time a new solution is found (an incumbent) so that solutions are improved whatever the time limit is.  This is more or less what solution polishing in CPLEX does, among others.