Improvement or Innovation ?

There is currently a discussion on the blog of Michael Trick about the LDS (Limited Discrepency Search) which has neither any relation with LSD nor with Lucy, Diamond or Sky, but which comes from a request of Matt Ginsberg asking Christian Schulte for changing the licence of Gecode because the use of Limited Discrepency Search for solving some job scheduling problems is patented.

The same story happened when I was at ILOG. So, M. Ginsberg seems to like repeated business :-) I don't know exactly what was the agreement between ILOG and M. Ginsberg. Everybody knows that  ILOG removed the
LDS acronym and name from all the documentation and from the product, but there are some unknown funny stories (because cp is fun) behind that old problem.

- we discovered that we didn't correctly understand the LDS and what we implemented was  not the LDS. Thus, we name it Slice Based Search and it was published under the name Discrepancy-Bounded Depth First Search (J. Christopher Beck and Laurent Perron)
- all that stuff does not really work well. I think that there is no more any CP model of benchmarks using it.
- LDS is clearly outperformed by restarts with randomization.

However, there are some other lessons that are interesting:

First, it is not because it is open source that you have the right to copy everything and put it into your product.

Second, M. Ginsberg is right when he says :"But if a commercial company wants to sell an implementation of LDS for use in job scheduling, it is — in my opinion — not unreasonable for the people who invented LDS to be compensated.". With such an idea I could become rich, especially if I create a company with N. Beldiceanu :-) But how can we implement this idea ? By patents ? I am not sure it is the good solution. We could accept this only when the idea is really an invention, that's mean it is strongly original. In other words, it is an inovation and not only an improvement. Because if it is an improvement we should also compensate the people who introduce the idea before, and so on... But how do we distinguish these two notions? In the comments of Mike's blog we can see that this is the point! T. Walsh proposed the Left First Search : “Thus, in searching the tree we want to minimize right arcs … We call a search algorithm which does this left-first search. At the n+1-th ply of the search we explore all those nodes whose path back to the root includes n right arcs”. Then Toby proposed an exponential algorithms. If you recognize LDS in Toby's words then LDS is an improvement otherwise it could be seen as an inovation...

At the end, I hope that M. Ginsberg made more money by the breakthrough brought by LDS over other search methods than by the patent and the threats associated with it...