## What Is The Solution When There Is No Solution ?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 : 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 "what is the solution when there is no
solution?""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. |