What Is The Gap?
JeanFrancoisPuget 2700028FGP Comments (2) Visits (13659)
My last blog entry triggered a discussion on twitter, where one said customers should not wait hours to get their problem solved. This made me think and I decided not to answer directly. Why? Because such discussion is meaningless until we agree on what "solving" means.
Let's go back to the basics. Excuse me if I sound pedantic, but I had to go through the same explanation when I learned about mathematical programming (MP). Indeed, my background was in constraint programming (nobody is perfect) and learning MP was kind of difficult because of language issues. As a matter of fact, after going through this learning curve I wrote a paper with Irv Lustig about it: Program Does Not Equal Program: Constraint Programming and Its Relationship to Mathematical Programming in case you want to learn more about it.
So, ready for a crash course? You can skip it if you are a MP person. You can read it if you come from another area.
[start pedantic = true]
MP is a prominent optimization technology, but not the only one. Researchers in other areas (graph theory, artificial intelligence, physics, biology) have developed other techniques known as constraint programming, local search, meta heuristics, evolutionary algorithms, you name it. In general these techniques can meet condition 1 above, but not condition 2. They can find x in P such that f(x) is low, but they usually do not provide a gap. It is usually impossible to know how far we might be from the solution of the problem. This is true even for those techniques that can prove optimality, eg constraint programming.
Is this a problem? Is it a problem for business users? Do they care about the gap? The first time I was exposed to this definition of a gap, I though that these MP guys (CPLEX team to name them) were off track here. As far as I knew, what mattered was to find x in P wih f(x) as low as possible, but nobody cared about the proof of optimality. I now know I was wrong.
In fact it was a chicken and egg story. If you don't have a technology that provides gaps, you don't get customers interested in getting a gap. This is what happened to me. It is as simple as that.
Now that I have been exposed to CPLEX customers for quite a while, I can testify that there are customers who require a gap, or who require optimality proof. This can be for regulatory or even legal reason. It can also be for the sake of the gap itself, i.e. for being able to evaluate how far we are from the solution of the problem. Anyway, there is a demand for good gap out there. For instance, I am currently working for a customer that requires a gap of less than 10% within two hours.
Granted, not all customers are interested in a gap. Some just want a good feasible solution, and they don't care about optimality. It is my experience though that most customers are interested in optimality. They resist attempts at trading optimality for computation time even if it could be a sensible approach to their problem.
So, next time one speaks about solving an optimization problem, check if it is about finding a feasible solution, or if it is about proving optimality of a solution.