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!
And that’s why…
a. “software” patents (that is in the broadest sense, patents involving no apparatus) are such a pain in the bum;
b. most countries deny the patentability of pure algorithms;
c. the world definitely is in need of a harmonized regulation system (which pays high attention to prior art & clearly defines what an average engineer would be capable of; so, for instance; no search or permutation strategy should be considered innovative in a way that the granting of a patent is justified).
As far as I know, algorithms are not patentable in the US. And indeed, in this case it is not LDS that’s patented, but rather a method for job scheduling. That means that if you use LDS for something else, you are safe.
Also, if you call it something else, you may be safe. (like calling your algorithm “barrier method” instead of “interior-point method” can help you sidestep a lawsuit wiith AT&T).
Thirdly, it needs to be verified that the LDS implementation in question is covered in the patent. In general, practical implementations differ from a theoretical algorithm quite a bit.
I think this is an overreaction and the patent would not hold up in court. Too bad they didn’t push back.
I share your concerns about software patents in general, and “non-obviousness” of LDS in particular. Novelty, however, is not a problem with this patent. The first version was filed by the authors of the original LDS paper in 1996, so that was within the grace period (you can file a patent within one year after publishing about an invention).
Mike,
Thanks for taking this up (thanks to Willem-Jan for pointing that out to you). It is just something we can’t afford to waste our time with: the license holder has been quite forthcoming in that he offered a transferable non-commercial license to me for LDS which I then could grant to our users. Entirely reasonable within the US patent system (whatever that’s worth)…
But honestly: why would we do that? As one of the developers of Gecode, I just have that much time to devote to a single feature in Gecode. Dealing with patent issues is something that I neither have the time nor the expertise for.
So, software patents foster innovation, right?
Christian
This goes back a long way as you indicate, and presumably will expire in 2012.
I assume the patent is held (or at least was held) by Ginsberg and Harvey and/or their institution. The paper was published at a conference but I am pretty sure the patent was applied for before the paper was published: otherwise obviously the patent should never have been granted. Presumably it took 5 years to get through the system.
So to be fair, I doubt it was a retroactive patent.
On the other hand, assuming I’m right about the background, it is a great pity that the paper doesn’t say “we are trying to patent this” to help out people avoiding getting trapped. We could all have just left it well alone and avoided wasting time instead of getting into fights about it.
P.s. I should mention that – without going into the rights and wrongs at all – to have the originality of a patentable idea to me. That is, in principle it seems likely that the threshold of getting a patent is lower than the threshold of getting an IJCAI paper.
That is, assuming it was narrow enough, there was no prior art etc.
This patent already got close to the courts. Over 5 years ago ILOG Inc (now part of IBM) had to defend themselves from the patent holders for including LDS in their constraint solver, ILOG Solver. The case got as far as assembling teams of expert witnesses before, I presume, the patent holders backed down.
I know this since I was asked to be one of the expert witnesses for ILOG. One reason I was approached by ILOG was that I co-wrote a paper more than two years before the patent application which may or may not be considered prior art. I know that our work was considered close enough that the patent submission had to be rewritten when I told the people filling the patent about our prior work.
In our paper, we propose a novel search strategy, called “left-first search” in which we search a tree in order of the number of right arcs (aka discrepancies). There is, however, one significant difference between LDS and left-first search as our trees were quite small: we were able to implement this in a more time efficient but less memory efficient way.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.7948
It was a pity that the case never got tested then to prevent future events like the one you describe.
There have been many variants and alternatives to LDS since the 1995 patent/paper if your readers want something similar (and often as or more effective) to include in their solver. See, for instance, ILDS, DDS and DDFS.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.5738
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.4059
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.8089
A patent for a (new? clever? non-obvious?) use of LDS is not a patent on LDS itself. So I suspect this is yet another case of someone filing a patent for a butter knife and then wielding it like a claymore (forgive the fuzzy metaphor). Like you, I’d love to see this one get settled in a court. I’d also like to see a law that allows frivolous and overreaching patent enforcement attempts to be dismissed without trial, with the plaintiff paying all costs, similar to anti-SLAPP laws. But I’m not holding my breath waiting for one, since we still don’t have a federal anti-SLAPP statute.
I appear to be the “offending” party here, so let me try to clarify.
First, the facts. We published LDS in 1995, and the original patent was filed in 1996. It was refiled in 1998 and granted in 2000. The patent has seven years to run, I believe.
LDS was original, as Toby well knows. He did indeed invent a method called “left first search”, but that method uses exponential amounts of memory. LDS uses polynomial amounts of memory, which is why it is useful.
We have been very clear that (a) we have no claim on any method that uses exponential amounts of memory, and (b) we will always grant a license to anyone who wants it for non-commercial use. That includes for-profit entities wishing to do research. All we ask is that if you make money on our work, you pay us a reasonable licensing fee.
I am not a lawyer, but my understanding is that you cannot sidestep a patent by changing the name of what you’re doing (indeed, the ILOG site used to mention LDS by name and they changed that but it didn’t affect the argument). If you want to know whether you’re violating a patent, you have to look at the claims in the patent. In this case, the claim is for incrementally modifying a “discrepancy limit” (fairly loosely described) during search. The patent talks about job scheduling, so that an application that does not involve job scheduling (and cannot reasonably be interpreted as involving job scheduling) would not infringe, I don’t think.
As far as Toby’s claim that, “The case got as far as assembling teams of expert witnesses before, I presume, the patent holders backed down,” I can tell you that commercial users of LDS in the U.S. have paid licensing fees in every instance of which I am aware.
I think that the only thing I would do differently at this point is that I wish we had said at the outset that we were applying for a patent on LDS when the original paper was published. I currently do that in all my work (where it’s applicable), including the fact that we will always grant licenses for non-commercial purposes.
My feeling is that the patent system *does* encourage research. Now that I run a company (*in addition* to doing research, I keep telling myself), I know that the possibility of patent protection is the only reason that we can publish research in many cases. We always grant noncommercial licenses; my message to Christian was clear that not only would we grant such licenses, but we would give *him* a fully transferable non-commercial license, which would take care of everything at a stroke.
That said, I agree completely that the patent system can be misused. Things that are obvious should not be patented. (LDS isn’t obvious; witness, for example, the fact that Toby didn’t come up with it when he was doing the left-first-search stuff.) Patents should not be used as cudgels. 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.
Thanks to all the commentators, but especially to you, Matt: I very much appreciate hearing your side.
I am not sure why the enforcement is at the Gecode level: the patent application is limited to job scheduling, while Gecode can be used for much, much more than job scheduling. It would seem more appropriate to attempt to enforce at the level of commercial job scheduling software that embeds LDS (like Matt proposes). But I (like Matt) am not a lawyer trying to enforce patent rights.
But I reiterate that allowing a non-commercial license (like Matt offered) is not compatible with open source licenses, which cannot distinguish among users. And the effect of the action has been to remove LDS from Gecode even for non-job-scheduling applications. The latter, in particular, cannot be seen as encouraging innovation.
I’d like to clarify that I indeed pointed out that Matt had offered me a transferable non-commercial license.
I also would like to stress that I have full respect for Matt’s take: I might disagree with the usefulness of the patent system as such and this patent in particular but I absolutely respect Matt’s claims (by face value, without any acknowledgment of the fact that the patent in question might cover just the application of LDS to jobshop scheduling).
All in all, why bother. I second Toby in this. We as Gecode developers will provide something in the future that is not LDS, is not infringed by patents and is more useful than LDS.
As far as Michael’s comment, let me add a couple of things.
First, you have responsibilities when you have a patent; if you don’t honor them, you can lose the patent. One of those responsibilities is to enforce the patent; you can’t learn of someone infringing and not bother them. (This is arguably bad.) So I had to tell Christian *something* when I learned that LDS was inside Gecode. I didn’t say he was infringing; I just told him it was patented and tried to help him fix it.
Second, I agree completely that open source software and patents don’t mix well. My view, however, is that that is a *condemnation* of open source. Certainly if *all* software were open source, many people would stop writing software. It would be a good thing if the people at Microsoft would stop, but not everyone works at Microsoft. 🙂
The bottom line, I think, is that it is important that IP be protectible. It should be obvious that if you *allow* people to protect IP, more people will develop IP because there is more payoff to doing so. Then you have what should be an entirely separate question — how do you (as the owner) decide whether or not to protect a *particular* piece of IP?
In some cases, you don’t. The company I run releases some stuff without limitation. That’s great. In some other cases, you do. That’s how I justify some of the research that we do. And in other cases — actually, in a *lot* of other cases — you want to get some sort of partial protection. You want, maybe, to let anyone use your stuff unless they make money off of it (in which case you want a cut). You also need to weigh the restrictive nature of patenting something with the opportunity cost of releasing it for nothing.
In all honesty, I think that this sort of “partial” protection should happen all the time. It would *encourage* innovation without stifling research. So that’s what I aim for in the work in which I’m involved.
As I said, I think its a pity a court never actually decided if LDS was novel enough to be patented. It was a novel method but whether it was different enought from prior art is still open to question in my opinion.
I carefully worded my comment: “(Left-first search) may or may not be considered prior art (to LDS)”. There are arguments for and against this position it seems to me.
Matt argues that we invented a method called “left first search”, but that method uses exponential amounts of memory. This is a slight compression of the facts here.
What we wrote in 1992 was:
“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”
[Aside: in my opinion, it would be hard at this point
to distinguish this from a high level description of LDS]
Then we add:
“We have implemented a meta-interpreter that performs
this search as follows. …. ”
And we then gave an algorithm whose space complexity
was linear in the size of the (possibly exponential) tree.
[Aside: the application we had in 1992 had small enough
trees we could get away with this]
So we gave one implementation which was, I agree totally
with Matt, different to LDS but the high level description of
left-first search (and indeed the figure we drew to illustrate
it in our paper) are very close to LDS.
One question that I suspect would have been argued in
court is whether the step from our implementation of
left-first search to Matt’s implementation of LDS was worthy
of a patent. The arguments for this include that we didn’t do it
back in 1992. The arguments against include that
similar cases of trading time for space exist in other
areas of search (e.g. Korf’s 1985 IDA* version of A*).
The overall impression I have is that the matter is not black
or white and arguments can be given in both directions.
This has been a fascinating discussion so far, but ultimately, I think that this is not the best time or place to litigate the LDS patent.
The more general questions of interest are:
Are patents the right kind of protection for algorithms and software? Or would copyright and trade secret protections (which are unquestionably appropriate) better serve the cause of encouraging innovation in software?
If patents are really appropriate, are there practical changes to the patent regime (such as shortening the protection period or clarifying standards for originality or patentability) that would make the process better serve the cause of encouraging innovation in software?
I think Matt’s characterization of the open source approach to patents as condemnable is too strong. There are some open source partisans that think all software should be open, but my opinion is that vendors might have reasons to distribute proprietary tools. Optimization software is one example where there can be value to the vendor in keeping software closed, independent of whether patent protection is appropriate. If you have a technique that gives your code a performance edge in this business, you have to evaluate whether that edge is valuable enough to keep it from the competition. But there are plenty of other models for doing business in software that are compatible with open source. And there are benefits to getting the community involvement that often comes with open source. That’s a tradeoff that the author needs to evaluate.
Just as a point of information: The common patent protection in open source licenses requires anyone using the code that owns a patent on ideas in the code to grant a patent license to other users of *that* code or derived works. There are licenses that don’t require that patent licenses be granted to other realizations of the patent or that users refrain from pursuing patent claims not related to the software. And the remedy is generally just revocation of the license on the software. Developers and users need to check the terms of the license that applies to their software. Original developers, of course, need to choose a license that treats patents as they prefer.
I agree that this is not the place to litigate the LDS patent. 🙂 But there are a few things that relate to patents generally, and it’s probably worth pointing them out.
First, the patent office in this case was aware of the left-first search work before the patent was allowed. In general, a court ruling on the validity of a patent will virtually never overturn a patent on the basis of supposed prior art when the prior art was disclosed to the patent office during the examination process. It is assumed that the patent office has done its job.
Second, I disagree with Toby’s suggestion that the left-first search work made LDS non-novel. In the left-first search work, you store all the nodes in the space, and examine them in increasing discrepancy order. You need exponential space, and the method is of limited value on large problems as a result.
In LDS, you switch from exponential to polynomial memory by potentially *reexamining* the nodes with lower discrepancy value when you examine those with a particular discrepancy value n. This works because of two very separate reasons: (1) There are many more nodes with discrepancy value n than there are with value n-1, and (2) It is possible to use depth-first search, with polynomial memory and time, examine all nodes with discrepancy no more than n.
Of course, both (1) and (2) are obvious *in retrospect*. But given that Toby, who is a very smart guy, didn’t notice that there was a poly space version of LFS when he invented it, I think it’s pretty clear that the poly-space version of LFS is novel. It sacrifices a *little* bit of time to save an exponential amount of memory.
Now, if there were some general result that you could *always* sacrifice a small amount of time to save an exponential amount of memory, LDS would be much less of an innovation over LFS. But I strongly suspect that there is no such general result. And just because you can *sometimes* do it (i.e., IDA* vs A*) does not make LDS any less patentable. There are a lot of things that you can sometimes do. Figuring out which of them apply in which situation is research.
So in this particular case, the US Patent and Trademark Office, whose judgment is generally viewed by US courts as authoritative, ruled — correctly in my view, although I’m obviously biased — that LDS was sufficiently different from LFS to warrant patentability. Probably Toby is just ticked that he didn’t think of it. 🙂 That’s only fair, because Toby has thought of a lot of stuff that I wish I had thought of, as well!
Matthew Saltzmann wrote:
Optimization software is one example where there can be value to the vendor in keeping software closed, independent of whether patent protection is appropriate. If you have a technique that gives your code a performance edge in this business, you have to evaluate whether that edge is valuable enough to keep it from the competition.
I agree completely. The problem is that making something a trade secret — especially something that actually WORKS — stifles research in a terrible way. That’s why I think that the patent system can add so much value.
To indicate the depth to which I believe this, the company I run has a policy that anyone doing research can *always* publish the results. If we want to protect them, it is up to us to file a patent. All we ask (and it’s rare) is that the inventor give us a chance to prepare the patent paperwork before publishing anything.
I believe in research. As I said in my first post here, I still think of myself as more of a scientist than an executive. If I can’t turn a profit, research at my company stops because the company goes under. The patent system is the only way — the only way — that I can simultaneously ensure the viability of my company and the distribution of our work.
Software patents stifle innovation because software is build upon a multitude of other software. Money that now must be spend on defending against patents, as well as attaining defense patents, could have been much better spend making better software or providing more support.
The open source movement might be safe from patent litigation by real companies because of the OSN:
http://www.openinventionnetwork.com
http://opensource.com/law
But it is, just like propitiatory software, under constant threat of patent litigation of patent trolls…
When is LDS not LDS? Harvey & Ginsberg (H&G) describe an algorithm that takes its discrepancies early. Korf later proposed ILDS but in doing so re-introduced LDS … but as a search that takes discrepancies late, counter to the hypothesis behind H&G’s LDS. Richard Korf introduced a bug and this has been faithfully reproduced by the community for 15 years now. Most papers I have read on LDS, the authors obviously haven’t read H&G and just code up LDS as incorrectly described by Korf, taking discrepancies late! My experiments (rejected by ECAI, rejected by CP, and now waiting rejection from JEA) shows that late or early makes no difference. So, does H&G’s patent cover Korf’s buggy version? And is my algorithm LDS2010 (rejected by ECAI, rejected by CP, awaiting rejection by JEA) patented by Matt?
… LDS2010 reject is here
http://www.dcs.gla.ac.uk/~pat/papers/ldsRevisited/jea/ldsRevisited.pdf
I was product manager at ILOG for Solver during this investigation. I think there are many reasons that patents should not be awarded for methods like LDS. I am really tired of seeing algorithms tied to pictures of CRTs and disk drives as justification of “embodiment”.
One part of the entire picture that is missing in this discussion is the obvious trolling of web sites for the term “LDS” or “limited discrepancy search” by the University or Oregon. Why Oregon? Because they used the 1 year window after “invention” to file the patent despite the fact the work was done elsewhere.
The system in the US is not set up in a way to promote the same advantages of software patents as it is for mechanical patents. In particular the 1 year window is a dangerous thing. If I see a talk at a conference I have to wait a year to figure out if the disclosure was filed. The US should more closely follow the EU in this instance where filing must be done prior to 1st disclosure. There are other areas for improvement but this is an important one.
Chris Hane
Why don’t you just use a lossy technique to store which nodes you have already visited, and get around this patent? I am thinking Bloom filters here, though they give you false positives, and you need false negatives (doing search 2x is complete, not doing search is problematic).
BTW, for my two cents: I can understand the author defending his patent. I don’t like patents, but some research positions are even worse (France anyone?). If patenting makes you independent from them, maybe it’s worth the price.
I was the VP of Optimization R&D at ILOG when we were approached by Matt Ginsberg on the LDS patent. Matt came to us after seeing on our website that we claimed to offer LDS in our ILOG Solver product. After investigation Matt and us agreed that ILOG wasn’t actually using the LDS algorithm. As part of the settlement of the dispute ILOG ceased to use the LDS name in all of its documentation and web site content. ILOG did not acknowledge any patent infringement nor did we had to remove or rewrite portions of ILOG Solver code.
In reply to Matt Ginsberg’s expressed views above:
Did I hear right that one can’t make a living without patenting mathematics or that people won’t practice mathematics if they can’t get a patent?
Are we aware of Einstein’s high caliber contributions to society sans patents? That he needed to leverage his peers and social context? That he was a patent examiner who fortunately was able to bypass that nonsense to be able to achieve his contributions to society?
..that monopolies, the removal of allowed competition, bring in largess?
[Arrogance or simply unclear thinking?] Superior mathematics than what passes for patents has been developed for hundreds of years on an ongoing basis.. including many algorithms from the early days of computing when patents weren’t taken out.
Mathematics are facts (and information). Algorithms are mathematics. These aren’t copyrightable nor patentable. And particular expressions that might be copyrightable are recognized to have many limitations on monopolization due to over-riding free speech protections. You can’t get copyright protection on ideas, for example, yet patents are just that, protections on ideas.. at least this is what *process patents* are.. which is what a software patent would have to be if you want hope to sue someone for using a general purpose digital machine that expresses that patent as a core unchanged physical machine performing a calculation (a process).
Giving noncommercial rights to others is much better than asking for a monopoly, but if we applied patents automatically to everyone’s creations (and not just gave them to those able to afford them and willing to take them out), it would become impossible to account for all the reuse of all ideas.
The patent system hasn’t crashed because only the wealthy play the game since for software it’s rather easy to meet the non-obviousness bar. You just need a computer and start writing away ideas. [Some will lean on developments in open source and others will look at mathematics, but all of this isn’t required merely to get a patent.. see “non-obvious” comments here http://nathanmarz.com/blog/inglourious-software-patents.html ]
People have suggested taxing income (profits) and using this as a base upon which others can lay claims (for patents). This is one way to approach the problem of providing another source of income for those with decent ideas. In the case that others also come up with the idea independently, that is fine. No monopolies are set and the “first” to apply gets access to some change. Taxing is simple and essentially unobtrusive to progress.
For this to be affordable, the money you get would likely not be that high, but it wouldn’t have to be because we would allow anyone to apply for a token sum. Not dealing with the high legal and maintenance costs that come with today’s patents would save everyone loads of overhead. Together, these lower costs would make the system worthwhile to participants.
There would be many other savings such as the removal of lawsuits that can break small businesses and in any case cost society tons of money that would be spent in more useful ways (than arguing in a courtroom) and not suffer the large opportunity costs from monopolies blocking many.
I think there are many ways for software patent inventors to get paid (mathematicians and many other experts have been finding ways for ages). These ways would not preclude others from independently making the same observations/discoveries or from leveraging information they come across. .. Again, people borrow from all over society and then want to place a barrier in front of others? That should not be tolerated.. and it doesn’t promote the progress (and a major reason why they would be unconstitutional).
To end, a quote from a comment I just read (see link above):
>> Companies have an affirmative motivation sufficient to induce innovation absent monopolies. What they don’t have is the extreme profits and market power derived from patenting. Acquiring market power this way is highly destructive to the market as a whole, to innovation, to competition and consequently to the value a customer receives.
>> You might as well argue that if I can’t shoot my competitors in the face at will, then the business model I created with the built in assumption that I could will suffer. Therefore I need the power to shoot my competitors in the face.