Pittsburgh INFORMS information

We are about 6 weeks away from the Pittsburgh INFORMS conference.  On the plus side, we have been blessed with outstanding local and global support (ILOG has supported upgraded conference bags, SmartOps has sponsored a new Tuesday reception, IBM Center for Business Optimization has sponsored a new Prize Ceremony and much, much more).  On the minus side, I hope readers here have hotel rooms, since the city is definitely filling up!

Pittsburgh has a lot to offer.  The local committee is putting together a local guide.  If you have been here (or live here now!) and have comments to offer, please let me know and I will update the guide.

We now have receptions for all of Sunday, Monday, and Tuesday (November 5, 6, and 7).  If you are one of the first dozen or so people to find me at the reception and say “Hey Mike, I read your blog”, I will be happy to buy you a drink!

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.