ECLiPSe and Open Source licensing

ECLiPSe LogoExcellent news about ECLiPSe, the constraint programming package. It is now been open-sourced under the “Cisco-style Mozilla Public License”. For a while, I had wondered what had happened to the package. It used to be based at IC-Parc/Imperial College London, but that group disappeared all of a sudden, at least from my perspective. To see ECLiPSe come back in open-source is tremendous news. ECLiPSe is owned by Cisco Systems, who should be applauded for their decision to open-source. Here is a blurb about the software:

ECLiPSe is a software system for the cost-effective development and deployment of constraint programming applications, e.g. in the areas of planning, scheduling, resource allocation, timetabling, transport etc. It is also ideal for teaching most aspects of combinatorial problem solving, e.g. problem modelling, constraint programming, mathematical programming, and search techniques. It contains several constraint solver libraries, a high-level modelling and control language, interfaces to third-party solvers, an integrated development environment and interfaces for embedding into host environments.

Given that Cisco is looking for support and development people for ECLiPSe, the decision to open-source is obviously not a sign that Cisco wants to forget about the code, but is clearly a recognition that open-source code can be developed faster and better than propriety code.

I wrote before about COIN-OR, an open-source initiative originally developed by IBM but now with wide participation from the optimization world. Between the COIN-OR systems in integer and linear programming and the ECLiPSe system in constraint programming, some very top notch operations research code is now available in open-source.

EURO Management Science Strategic Innovation Prize

A lot of the entries in this blog are about significant applications of operations research in practice. EURO has a prize on Management Science Stratetic Innovation (MSSIP). Their 2007 prize will be in the area of OR/MS in Logistics. From the announcement:

The prize is intended to recognize the role of Operational Research/Management Science in Logistics. Needless to say that Logistics or Supply Chain Management is taking centre stage in Operations. In the business world, Supply Chain Management has been a crucial discipline in a global world with an increasing number of players involved in bringing even the simplest of products to the customer. It is fair to say that a separate science of Supply Chain Management has been developed in the last fifteen years (even though Logistics goes back many centuries or even millennia).

Recent events have propelled Supply Chain Management into the boardroom in some businesses but the true strategic impact of Logistics is still poorly appreciated by numerous companies. This is even more the case among policy makers. Obviously, Logistics has always been central to successful military operations and the recent dramatic tsunami in Asia has convinced everyone of the central role of Logistics in disaster response as well. In spite of this rise in attention to logistics, many organizations (public or private) have not yet taken the logical next step of reorganizing their structures accordingly.

OR/MS has been a large contributor to the newly developed science of Logistics/Supply Chain Management. But there is a lot yet to do. The MSSIP 2007 price intends to recognize the OR/MS contribution but also to encourage researchers and professionals to continue and perhaps even increase their efforts in contributing to the content as well as the recognition of Logistics/Supply Chain Management as a core discipline and function in business and society.

One unusual aspect of this award is the breadth of definition of logistics:

So we will kindly regard innovative applications of OR/MS to new or unusual Logistics situations. Think for example about risk, robustness, agility, humanitarian organizations, new products/markets/services, interfaces and integration with other disciplines like accounting and finance, and the like.

The deadline on this is March 1, 2007, so there is plenty of time to put a paper together.

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.

INFORMS Computing Society Conference

The INFORMS Computing Society Conference will hold their annual meeting in Miami from January 3-5, 2007. While ICS has a large contingent at the INFORMS Annual Meeting, this conference has a much different feel. Rather than being part of a 3500 person conference, the ICS Conference aims for around 100-150 participants, all interested in the interaction between OR and computer science. A highlight of this conference will be the presentation by Robert Atlas, director of the Atlantic Oceanographic and Meteorological Labs. AOML looks at things like hurricanes, climate change (or stability, for this politically charged issue!), and coastal effects. This area is a great one for OR: there are lots of policy issues that can use an analytical input.

The deadline for abstract submission for this conference is October 1, 2006.

President Clinton, AIDS and Operations Research

Clinton FoundationIt is heartening to see former President Clinton talk about “Operations Research” and even better to see outside groups see the promise of our field. At an address at the 16th Annual International AIDS Conference, President Clinton announced a new Consortium for Strategic HIV Operations Research. From the transcript (page 13/14):

Second point I want to make is while more money is necessary, it is nowhere near sufficient. It is our moral obligation to ensure that the enormous contributions already made and those that will be made are used most efficiently. Every single wasted dollar puts a life at risk.
A few days ago, my foundation unveiled our consortium for strategic operation research here in Toronto. It’s an initiative designed to help ensure that this huge investment of resources results in the highest quality care, most efficiently delivered for as many HIV infected people as possible. We want to apply the same planning methods that Fortune 500 companies use to manage their operations, so that we can make the most effective use of what will always be scarce resources until the number of people who are HIV positive begins to drop dramatically. Using simple open-source computer models, we’ll be able to help governments save more lives with the same human and financial resources.

Wow! An obvious reference to operations research and open source in the same paragraph!

A few months ago, I talked to some researchers at the Clinton Foundation. Often “Operations Research” in AIDS/HIV research is what we would call “Statistical Experimental Design”: how to best measure the effect of certain treatments. For instance, there is a book available online entitled: “Designing HIV/AIDS Intervention Studies: An Operations Research Handbook” that will not be recognizable as operations research as our field defines it.

While important, this approach ignores 99% of operations research. Issues like optimal resource allocation, stochastic models of disease spread, simulation and so on are equally or more important, but are under-studied in this area.The Clinton Foundation people seem to understand this, and want to bring the full power of OR to this field. The CSHOR has in place a simulation model of clinics that can be modified to fit local costs/resource availability to determine, for instance, the effect of having another nurse. The Q&A directly addresses the role of OR:

Why was CSHOR created?

The emerging field of operations research offers a practical and strategic approach to future planning for developing countries. Operations research can be performed on the ground, in real-time, to guide decision making at a single clinic or a regional or national HIV treatment program. Local data and best practices from programs around the world can be combined to help ensure consistency and quality of care.

Operations research is increasingly critical; as ever-vaster resources are poured into national HIV treatment programs, it is crucial to be sure they are used as efficiently to provide high-quality treatment and care for as many people as possible.

CSHOR was launched in response to direct appeals from CHAI’s partner countries for assistance with resource planning and allocation.

I am not sure “emerging field” is appropriate for a 60 year old field, but the rest is very encouraging.

OR has a huge amount to offer this area, and I am absolutely thrilled that the Clinton Foundation is using the skills of our field

The Blue Ball Production Problem

It’s course preparation time again. For those of you teaching production or scheduling, if you are looking for a graphic to show the need for split-second planning in certain production processes, I highly recommend the Blue Ball Machine. Hypnotic!

From Wired Magazine:

A Rube Goldberg machine made of animated tiles, with hundreds of blue balls moving in time to music from Pee-wee’s Big Adventure.
Max [of http://www.ytmnd.com]says: This is our most viewed title ever. It was created by the Web site Something Awful – they had 100 people make 1-inch tiles, and the only rule was that a ball had to enter at a certain place and exit at another. It came out awesome.

More on Air Taxis

My friend and business partner (in sports scheduling), George Nemhauser, read my post on air taxis and wrote to remind me that Georgia Tech worked with DayJet on the optimization issues that are key to the efficient running of their operation. This led me to an USA Today article by Kevin Maney that I had missed on the subject. The article covers the optimization issues very well:

Tech industry veteran Ed Iacobucci seems an improbable guy to start a new kind of airline. It’s like Donald Trump starting a chain of Laundromats, or Tom Cruise marketing an anti-depression drug.

Pretty jarring, in other words.

But he isn’t really starting an airline, much as eBay didn’t start a flea market. Iacobucci is a one-time IBM tech whiz and founder of software maker Citrix Systems. Over the past four years, he and his team have built a breakthrough computer system for solving highly complex optimization problems.

An optimization problem is like when a mom has to pick up one kid at soccer, one at dance, buy groceries, walk the dog and volunteer at church, and has to figure out the most efficient way to do them all. Now try that for hundreds of moms and hundreds of tasks all at once.

“This is hard stuff,” Iacobucci says. “There’s a lot of new science involved.”

His team is using this system to launch DayJet, the first true on-demand air service. Such a service could not exist without the new computer system. Basically, Iacobucci has started a technology company that will make its money by flying people around.

I love the phrase “a technology company that will make its money by flying people around”. I would like the phrase “an operations research company that will make its money by flying people around” even better, because that is what DayJet really is. Just like Amazon is an operations research company that makes its money by selling books and more, and FedEx is an operations research company …

The article goes on and makes a very clear point about the scale of the optimization, and the need for timely schedules:

If you have a bunch of little jets and a bunch of people in different cities who want a ride, Iacobucci thought, software should be able to figure out the most efficient way to scatter the planes so they can transport the people — while charging enough to make a profit but not nearly as much as a traditional charter plane service.

Good idea, until you start considering all the variables involved. Matching people, cities and aircraft seats is tough enough, but add in crew schedules, maintenance, fuel costs and the uncertainties of weather — plus the need to quote ticket prices before all the variables are in place — and you’ve got a computational mountain no one had yet climbed.

“When I told our team what we wanted to do, they went like this,” Iacobucci says as he makes a cross with his fingers — the way you’d ward off vampires. That’s serious, considering his team includes a couple of former Soviet rocket scientists and the complexity theory department at Georgia Tech, which helped DayJet crack the problem.

As customers put in their requests, the system continually crunches all the departure and arrival requests, plane availability, weather patterns and so on, coming up with a new best answer for schedules and prices every five seconds, always trying — as the DayJet folks say — to get the solution “within 2% of optimality.”

You have to appreciate how remarkable that is. When you’re making everyday, multi-faceted decisions — What should I make for dinner? Should I finish this report or see my kid’s soccer game? — it’s pretty unlikely you ever get within 2% of optimality. I think Donna Reed used to, but I’m sure that’s escaped every other human since.

The DayJet system crunches answers and ranges of probability until a couple of hours before jets would have to take off. “Then the schedule starts to gelatinize,” says Brad Noe, DayJet’s VP of engineering. “And it comes up with a plan.”

This is a great example of academia/business interaction in operations research to come up with businesses that could not exist twenty years ago.