Who among optimization practitioners hasn't heard at least one customer saying "I want the best solution" ?

I certainly did.

When that happens one has to manage expectations because solving real problems to optimality may not be possible in a reasonable time.  Customers must understand that finding the best solution and prove it is the best one is not always doable.  They should instead focus on finding the best possible solution in a limited amount of time.   If they agree to it, then they find it valuable to estimate what we have left on the table.  For MIP technology, this is provided by the gap.

There are other things we might do to please customers, but I'd like to throw in a very effective way to change the game.  When I am asked to find the best solution, I usually respond with a simple question:

What is the objective function ?

You would be surprised by how well it resets expectations.  It makes user think again about the value of using optimization, and it helps them define what they want to focus on.  This makes acceptance of optimization much easier.

I discovered this when I was working with my first customer ever.  Granted, it was during previous millennium, but it was at a time where punch cards were already obsolete.  I therefore think that the story is still relevant today. 

I was in a meeting room with 3 executives,  trying to convince them to go with our then burgeoning constraint programming technology.  They got convinced, then quickly agreed among themselves that they wanted the best solution.  I then asked the above question.  I got three different and conflicting answers!  To cut a long story short I decided to use an aggregate objective that took into account the three inputs I got.  After implementation of the corresponding optimization model the customer ended up being happy.

It is now time to revisit this story because there is a better way to handle this situation.  We should explicitly manage all the objectives.  This is called multi objective optimization and it is a relatively active research field.  The notion of optimality has to be modified when there are several objective functions.  The most popular way of doing it is called the Pareto Frontier.  Wikipedia has a nice figure that explains it all, see below. 

Assume we have two objective we try to minimize, f1 and f2.  The boxed points represent feasible solutions. We say that a point P is dominated by another point Q if Q has a better value than P for each objective function.  Then the Pareto Frontier is the set of points that are not dominated. For instance, Point C is not on the Pareto Frontier because it is dominated by both point A and point B.  Points A and B are not dominated by any other, and hence do lie on the frontier.  Pareto Frontier can be generalized to more than two objective functions.

Pareto Frontier looks like an interesting decision support function.  IBM Watson group is working on a tool that leverages it, called MOOV (Multi Objective Optimization Visualization).  More information on MOOV can be found at http://researcher.ibm.com/researcher/view_group.php?id=2812. The overview reads:

Efficient and consistent decision making is a hard challenge. The decision maker needs to account for multiple, often conflicting objectives, resulting in a very large number of options to consider. By using Pareto optimization we reduce the number of alternatives to an optimal set known as the Pareto Frontier. Provided with this set, users aspire to understand the conflicts between the objectives, explore the available tradeoffs and see the value of a selected solution. To meet this end, we offer smart visualization and analytical recommendation mechanism that altogether enable an easy and intuitive exploration of the Frontier. This approach increases the transparency of the selection process when multiple parties need to reach a consensus, and enables better evaluation of alternatives.

I like it and I'm sure the three execs I met in the early days would have liked it too.