Category: Legal

More patent madness!

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!

Personal Blogs, Personal Views

William Patry, Google’s Senior Copyright Counsel, is ending his blog “The Patry Copyright Blog“. That sentence, in short, gives one of the two reasons he is ending the blog (the other is the horrid state of copyright law, in his view). Patry is a long time copyright lawyer who started the blog while in private practice. Once he joined Google, however, suddenly people projected his blog onto Google. Of course, it is hard to see how to refer to people without saying something about their credentials. Saying, “William Patry, Google’s Senior Copyright Counsel, said this on his blog” seems to give more credence to a view than “William Patry, random guy on the street, said this”, even without making the step to “Google as a company believes this”. But too many people make the last step, making it impossible for Google’s senior copyright counsel to have a personal blog.

I’m primarily an academic, and there seems little harm in referring to me as “Michael Trick, professor at Carnegie Mellon, said …”, since there is a long tradition of celebrating individual views among professors. If everything a university professor said had to be vetted by the university (and who in the university could do such a vetting?), you wouldn’t hear much from professors on any topic. Once in a while, I get identified with organizations. Recently, I was referred to as “Michael Trick, former President of INFORMS” in a blog entry where I have pretty well convinced myself I was not referred to as a “nut with a computer” (though some doubt exists), which is a bit more troublesome. Even in 2002 as President of INFORMS, almost nothing I said was speaking on behalf of INFORMS. Certainly now, if it is not obvious, I don’t speak for INFORMS.

This is also relevant to the recent IBM/ILOG acquisition. We’d all love to hear from the ILOGers and IBMers on what they think it means. I would love to hear it on a personal level on how it will affect their life, their work, our field, and the universe. But it is essentially impossible for anyone at IBM or ILOG to speak personally at this point. Anything they say could be taken as “official” and would draw harsh legal (and company) repercussions. So, until the acquisition is complete, I think we will have to be satisfied with carefully crafted, legally-cleared, official comments.

Operations Research in the Air

My colleague Steve Spear has a posting on the “Against Monopoly” blog (not against the board game, but commentary on intellectual property issues) regarding a New Yorker article entitled “In the Air” by Malcolm Gladwell. Gladwell makes the point that many advances have been simultaneously made by multiple groups. From the discovery of dinosaur bones to the telephone to cancer treatments, there seems to be something in the air that gives the right time for a discovery. The New Yorker article gives a number of examples:

This phenomenon of simultaneous discovery—what science historians call “multiples”—turns out to be extremely common. One of the first comprehensive lists of multiples was put together by William Ogburn and Dorothy Thomas, in 1922, and they found a hundred and forty-eight major scientific discoveries that fit the multiple pattern. Newton and Leibniz both discovered calculus. Charles Darwin and Alfred Russel Wallace both discovered evolution. Three mathematicians “invented” decimal fractions. Oxygen was discovered by Joseph Priestley, in Wiltshire, in 1774, and by Carl Wilhelm Scheele, in Uppsala, a year earlier. Color photography was invented at the same time by Charles Cros and by Louis Ducos du Hauron, in France. Logarithms were invented by John Napier and Henry Briggs in Britain, and by Joost Bürgi in Switzerland.

“There were four independent discoveries of sunspots, all in 1611; namely, by Galileo in Italy, Scheiner in Germany, Fabricius in Holland and Harriott in England,” Ogburn and Thomas note, and they continue:

The law of the conservation of energy, so significant in science and philosophy, was formulated four times independently in 1847, by Joule, Thomson, Colding and Helmholz. They had been anticipated by Robert Mayer in 1842. There seem to have been at least six different inventors of the thermometer and no less than nine claimants of the invention of the telescope. Typewriting machines were invented simultaneously in England and in America by several individuals in these countries. The steamboat is claimed as the “exclusive” discovery of Fulton, Jouffroy, Rumsey, Stevens and Symmington.

We see this in our own field when multiple groups seem to solve longstanding open problems almost simultaneously, often years after the problem was formulated. Such happenings inevitably lead to accusations and recriminations, with cries of plagiarism and other nefarious goings-on. Of course, ideas are stolen and the stress of publication can lead to short-cuts, and these are rightly decried, but I think there is something to this “in the air” phenomenon. Many simultaneous discoveries may be just that: simultaneous discoveries.

The Against Monopoly blog points out that these simultaneous “inventions” are often the outcome of a tremendous amount of public buildup. The “invention” is then just a small step, with a corresponding willingness to fight a patent battle. As the blog says:

I certainly came away from the article believing even more strongly in the Boldrin-Levine [see here] contention that intellectual property rights just aren’t necessary when you have the shoulders of giants to stand on.

In operations research, we saw this with our most famous patent issue: AT&T’s patent for “Karmarkar’s Algorithm” for linear programming. I remember the INFORMS (ORSA/TIMS at the time) conference when this came out. Researchers were canceling their talks on the simplex algorithm, since it no longer seemed relevant. Doctoral students were ruing their choices, and giving up hope for a successful academic career since they had bet on the wrong horse. Of course, the algorithm had no such effect. Research on effective implementations of the simplex algorithm was spurred by the competition, and research on interior point algorithms moved quickly to respond. The field has been greatly enhanced by having competing techniques. The patent didn’t help this advance, and was not financially successful for AT&T (I do not believe), but Karmarkar’s algorithm was a beginning not an end.

But it wasn’t even a beginning. “Karmarkar’s” algorithm was actually a well-known nonlinear programming algorithm in disguise, with its roots dating to the 60s (Karmarkar announced “his” algorithm in 1984). This equivalence to known work doesn’t take away from what Karmarkar did. Believing that an approach more suitable for nonlinear programming would be efficient and effective for linear programming was a big step. And it made a huge difference on the field. But, in keeping with Stigler’s Law (no invention is truly named after its inventor), Karmarkar’s algorithm could really take on many other names.

More on patents: constraint programming

Diego Olivier Fernandez Pons has continued to search the patent database for interesting patents. Here is one given in 2000 to i2:

US patent 6,031,984

Method and apparatus for optimizing constraint models

February 29, 2000

A computer implemented system (40) for optimizing a constraint model (52) includes a memory (46) for storing the constraint model (52). The constraint model (52) is an over-constrained system model that has constraints with variables. Each variable in the constraint model (52) is
assigned a current value from a domain of the variable. A processor (42) generates a current assignment of each variable in the constraint model (52), selects a constraint from a set of unsatisfied constraints, selects at least one variable of the selected constraint, selects a new value for each selected variable, changes the value of each selected variable to its new value to generate a new assignment of variables, and stores the new assignment of variables as a best assignment in a set of one or more best assignments if it satisfies all the constraints and is at least as good as a best stored assignment. The processor (42) repeats the operations of selecting a constraint, a variable, and a new value, changing the value of each selected variable to its new value to generate a new assignment, and storing the new assignment until the new assignment satisfies all the constraints and is approximately optimal or until a specified number of iterations has been performed. In response, the processor (42) communicates at least one best stored assignment or communicates that no assignment satisfying all the constraints was found.

Looks like i2 has a patent on constraint programming. This could certainly cause some chaos to companies!

Patents and Operations Research

There is an article today in the New York Times on the fight the CEO of Audible (one of my favorite companies: listening to a book read by a skilled reader is a completely different experience than reading a book) is having against companies who claim Audible is infringing on a patent. These “patent trolls” offer to license for an amount somewhat less than the cost of litigating.

Of course, this is a well known and well publicized activity. While it is hard to argue for the worst aspects of trolling, patents are a key aspect to technological advance (open-source and open-development notwithstanding). Without patents, inventors lack incentive to take the risks inherent in research.

But the US patent office’s decision to patent processes has led to an incredible amount of abuse of this process. While patents are only supposed to be given for “nonobvious” advances, patent examiners seem to have an unbelievable inability to see the obvious given some of the processes deemed nonobvious. And Operations Research gets involved here. The United States Treasury and Patent Office has a wonderful system for searching patents. Searching (in “quick search”) on operations research gives 493 hits including one of those silly process patents for:

“Systems and methods wherein a buyer purchases a product at a first price and physically acquires the product at a location associated with a merchant that offers the product for sale at a second price”

(Patent 7,107,228. Dated September 12, 2006). Reading through this can lead to nothing but anger over a broken patent system. People can get a patent for this?? It appears that the only “operations research” aspect is a reference to one of our field’s journals, but I am ashamed to have those words appear in a patent such as this.

The patent database is a great place to spend a few hours (if you can get past some of the office’s nutty decisions). Searching on “integer programming” gives 244 patents, some of which look to be very clever uses of integer programming.

It might be argued that our field started this nonsense with AT&T’s ill-conceived patent on “Karmarkar’s algorithm” (patent 4,744,026 if you want to look it up on the system). At the time, AT&T had to surround this algorithm with a computer but they worked hard to “own” this algorithm, ignoring significant prior art. I don’t think AT&T made very much (if anything) out of this, but it appears to have encouraged a lot of others to try to stretch the patent process … past its limits.

Updated September 18

Diego Olivier Fernandez Pons wrote regarding patent 5,667,438. Entitled “Method of constructing crossword puzzles by computer”, it reads in part:

A software crossword puzzle design tool is provided. It provides a menu-driven user interface with various editing functions allowing the user to specify details of the crossword puzzle desired, such as the size, pattern, and inclusion of certain theme words. The unsolved puzzle is constructed automatically by a computer assigning letters to cells one cell at a time. After each assignment, the affected wordslots are compared to a lexicon of words to determine what letters of the alphabet may potentially be assigned to each of the remaining unassigned cells. If any unassigned cell becomes unassignable, some assignments must be reversed and others tried. Special data structures for the lexicon and fast methods of accessing the lexicon are disclosed. Clues can be assigned to the puzzle automatically or manually, and then the unsolved puzzle can be printed.

Wonderful: a patent on backtrack search.