Gecode is one of the key development platforms in constraint programming. On the gecode-user’s list, Christian Schulte announced the reason for a new release of the software:
We have been informed by one of the patent holders that LDS (limited discrepancy search) is patented in the United States of America. While this does not pose an issue per se for us as developers (the MIT license under which Gecode is released makes that clear), it does to you as users.
After weighing the merits of offering LDS in Gecode with the effort for obtaining a non-commercial license, we have decided to remove LDS from Gecode. Gecode 3.4.2 removes LDS.
Limited discrepancy search has been around since 1995 and occurs often in research (Google scholar is showing 465 references). It is a pretty simple idea: if you are doing a tree search and you have a good idea that, say, all the variables should be 1 (but might not be in the optimal solution), you first search the “all 1” side of the branches, then try the “all 1 except one” then then “all 1 except two” and so on. Call it twenty lines of code to control the tree search in this manner. Seems like a reasonable approach, but patentable? You have got to be kidding!
It is not clear from Schulte’s email either what patent is being referred to or who is doing the referring. Checking the US patent registry, patent 6,070,144 from 2000 is for “System and process for job scheduling using limited discrepancy search”. There are a couple later patents that use the phrase, but this is the earliest.
I am no patent lawyer, but I would love to see this go to the courts (or at least more discussion on what is actually patented). How a 2000 patent can claim rights over a 1995 result published in the open literature is beyond me. I can understand a patent that might use LDS in a narrow domain, but I can’t understand this sort of retroactive patenting of the entire technique. Of course, there may be an earlier patent that covers the method without using the phrase, though patents before 1995 only last 17 years, so there would be a very narrow window possible at this point.
Schulte’s email later states “The patent holder has informed me that he is willing to give a non-commercial license to anybody who seeks one” but that does not go very far compared to the patent holder’s wish to take LDS out of any free or open source system.
Patents (and companies trying to enforce them) make creating open source software much, much more difficult. How many developers would know that if you embed a method from a 1995 paper in software, you may run afoul of a patent claim?
Patents exist to encourage innovation. The current system, with nonsense like this, serves only to stifle it.
Thanks to my colleague Willem van Hoeve for pointing this out to me (and for wondering what is wrong with the U.S. patent system).
Note Added: As part of the extensive comments, Matt Ginsberg (holder of this patent) talks about his thinking in this matter. I hadn’t put two and two together: I have blogged on Matt before!
The mathematician Benoit Mandelbrot has passed away at the age of 85. Mandelbrot made a career in defining and studying fractals, geometric shapes that do not lose complexity as you zoom in on them. Things like coastlines are fractals: as you zoom in on a coastline, smaller and smaller inlets and other curves appear.