What Is The Solution When There Is No Solution ?
JeanFrancoisPuget 2700028FGP Comments (4) Visits (6926)
Optimization is like a Ferarri, when you drive it correctly you can achieve incredible performance. But you must understand what it can do and what it can't do or you will crash. Same is true for optimization. I'm starting a series of posts on various pitfalls that people using optimization can fall into. This is the what it can't do part. This will complement posts where I brag about the value of optimization, which are centered around what it can do.
Today's topic is about the difference between an exact answer, and a useful answer. Let me illustrate the difference with a well known joke. A woman is having a balloon flight over a foggy country. Because of the fog she cannot see where she is, and she is completely lost. I guess this happened before GPS were widely available... At some point the sun appears, the fog disappears, and the woman sees earth below her, not too far, say 30 meters. She then sees a man walking by, who happens to be a mathematician. The flying woman asks the mathematician where she is. The mathematician answers : "you're in the air, at about 30 meters above the ground, under a balloon." The woman responds that the answer is 100% exact, and it is 100% useless, as often with mathematics!
Optimization can lead to the same kind of fruitless exchange if not used carefully.
Today's topic comes from an interaction I had with an important customer (all customers are important, as anyone selling stuff knows). At a meeting with customer executives we were discussing the merit of optimization. We had some issue on a project because the mathematical model was infeasible from time to time in an application that was run every day. I had hard time explaining to the executive team that the issue was in the model, not in our solver. At at a point one of them asked : "what is the solution when there is no solution?" I could have sighted, thinking that they were hopeless, not understanding what a feasible solution was. But their question underscores the difference between an exact answer, and a useful answer to a business problem. An answer such as "there is no solution to your problem" is exact but it is useless. It is useless because it is not actionable, one cannot use it to run a business. What mathematics offer are exact answers. What businesses need are actionable answers.
Back to my customer, the executive didn't need an explanation of what a feasible solution is. What he needed was a business application that was always giving answers, whatever data and constraints were fed into it. After all, he had a business to run every day.
In order to fulfill this business demand let's look at the source of infeasibility. It is my experience that it often comes from too many constraints thrown at the problem. When business people describe their problem they often tend to describe an ideal world where everything would be run by the book. Reality is that many if not most of the business requirements are wishes, not constraints. It would be good to meet them, but if we can't meet them so be it. In future posts I'll come back to ways to differentiate between wishes and hard constraints, but let's recognize that the two categories exist for now.
Then there are various ways to make sure the model is always feasible. One way is to move wishes to the objective function. For instance, instead of saying that the amount of a given resource use U is no more than a given capacity C, we minimize the quantity U-C. If we can get it down to zero then the wish is fully met, it becomes a constraint Technically, it means that we add a slack variable to all constraints representing wishes, and we then add those slacks to the objective function to be minimized.
Another, related approach, is to minimize the number of wishes that aren't met. In this case we add a binary variable to each wish expressed as a constraint. That binary would be equal to 1 if the constraint isn't met. Then the sum of such binary variables is added to the objective function to be minimized. There can be a hierarchy among these constraints, having some being more important than others. This case amounts at relaxing constraints in an orderly manner, starting with the least important ones. We provide a way to do it with our Solve Anyway feature in our business oriented decision tool ODME. It is sometime called hierarchical constraint solving.
Last, we can let business persons make the decision about which constraints to relax. We can provide them with tools to analyze infeasibility. For instance CPLEX provides an Irreducible Infeasibility Set (IIS) feature that returns a set of infeasible constraints from an infeasible LP model. Such IIS is an indication of parts of the mathematical model that are too tight. The model can then be modified by relaxing some constraints as an attempt to make it easier to solve.
For those willing to explore this topic further I recommend the excellent tutorial by John W. Chinneck. It covers most of the above techniques and more with enough technical details. It also illustrate these in the context of both math programming and constraint programming, my two favorite optimization techniques. Last, but not least to me, it cites me! The first reader who finds on which slide will gain my eternal admiration
Back to business people needs, the lesson is that we must manage their expectations. We must make them understand that all their dreams won't come true. But, at the expense of some trade offs, we can provide them with very useful answers to their business problems. And this is what matters in the end.