Category: Open Source

COIN-OR needs a new web site

A long, long time ago (1995 to be exact), INFORMS asked for volunteers to put together its website.  While I was hesitant (I was an untenured assistant professor), I decided to apply, and I became the editor of INFORMS Online.  There are few decisions that had such wide-ranging, and unforeseen, effects.  I met people (like Brian Borchers, Matt Saltzman, and many others) who have been good friends and colleagues to this day.  I worked with an amazing staff, many of whom (like my good friend Mary Magrogan) are still with INFORMS.  And I learned a lot about how to distribute information to a large, distributed organization (getting significant information from the members would have to wait for later generations of web masters).  Eventually I became President of INFORMS (for the year 2002) and Vice President for IFORS.  And, it turned out, I eventually even got tenure.  There are few decisions I have made that have changed my life so much.

One of my favorite organizations, COIN-OR,  is looking for someone to help with their website issues.   COIN-OR is a major force for open source resources in operations research. While I won’t guarantee it will change your life, I highly recommend getting involved in organizations like COIN-OR:  you meet people, you learn a lot, and somehow, life seems to work out better when you are involved in things.  Here is the announcement:

General overview:

The COIN-OR foundation is a non-profit foundation that hosts 50+ open source software projects. Currently, the Web site is hand-crafted HTML (www.coin-or.org). Pages are hosted in subversion and checked out from there. Pages describing individual project are rendered from XML (see, e.g.,https://projects.coin-or.org/SYMPHONY/browser/conf/projDesc.xml and http://www.coin-or.org/projects/SYMPHONY.xml). Project source code is hosted in subversion with TRAC providing an integrated wiki and bug tracking (see, e.g., https://projects.coin-or.org/SYMPHONY). A mailman list serve is used for support, user feedback, etc. (see http://list.coin-or.org/mailman/listinfo/). Individual projects get Web space in the form of pages checked our from subversion (see, e.g., https://projects.coin-or.org/SYMPHONY/browser/html and http://www.coin-or.org/SYMPHONY/index.htm)

The general idea is to give the site a complete makeover to give it a more modern look and feel, social media integration, Web *.* capabilities. We implemented a test site in WordPress to play with ideas.

http://wptest.coin-or.org/

Specific design goals:

1. Move site to a CMS that will allow easier maintenance, ability to grant edit permission to individual pages, ability to edit in the browser, etc. Currently, WordPress seems to do all we need and we are familiar with WordPress. We’re open to other suggestions, however.
2. With the move to CMS, upgrade look and feel of the site and add capabilities, as follows:
— Implement forums for support and user feedback. Should include the ability to have general high-level forums, as well as individual forums for each project. Users should be able to create accounts on the site and post to the forums. Forums should be moderated (or at least should have the ability to moderate.
— Upgrade TRAC to the latest version, integrate support for git, and integrate the look and feel into the overall Web site.
— Implement single sign-on for the Web site (forums), the TRAC site, subversion. and git (so far, the best solution for this seems to be OpenID). Support ability to require e-mail address for valid registration and to capture basic demographic information (again, OpenID seems the easiest option).
— Implement download form that asks downloaders to fill out a form with basic demographic information (possibly requiring some sort of account creation).
— Support the ability to auto-generate project information pages from XML templates checked out from the subversion repos of individual projects, as with current site.
— Support blog(s) for posting news items. Each project should have its own blog, but these individual blogs could be hosted on the sites of individual projects (see 3 below).
— Support an events calendar.
3. Support the creation of individual sites for each project using the same CMS (WordPress allows this).
4. Ideally, create a separate site for the foundation itself.

—
Dr. Ted Ralphs
Associate Professor, Lehigh University
(610) 628-1280
ted ‘at’ lehigh ‘dot’ edu
coral.ie.lehigh.edu/~ted

If you are interested, contact Ted:  the COIN-OR group is a great group to work with!

COIN-OR Cup, 2011 edition

COIN-OR is a project to spur open-source activities in operations research.  I am a big supporter of this activity, to the extent that I was part of its Strategic Leadership Board for a term until I did them an even bigger favor by stepping aside for people who could be even better at this than I (not that such people were exactly rare:  my time on SLB corresponded to a somewhat over-committed time for me).

Every year COIN-OR gives out an award called the COIN-OR INFORMS Cup.  This year’s winner has just been announced, and I think the committee has made an inspired choice:

The submission “OpenSolver: Open Source Optimisation for Excel using COIN-OR”, by Andrew Mason and Iain Dunning, has been selected as the winner of the 2011 edition of the COIN-OR INFORMS Cup. OpenSolver is an “Open Source linear and integer optimizer for Microsoft Excel. OpenSolver is an Excel VBA add-in that extends Excel’s built-in Solver with a more powerful Linear Programming solver.” (from http://opensolver.org)

This year’s award recognizes that lots and lots of people want to use top-notch optimization code, but would like to stay in the world of Excel.  The authors of this work (who I am very proud to say come from the University of Auckland (at least in Andrew’s case), where I was a visitor in 2007) have done a great job in integrated the optimization codes from COIN-OR into an easy-to-use interface in Excel.  It is a fantastic piece of work (that I blogged about previously) and one that I believe does a tremendous amount of good for the world of operations research.  If you can model in Excel’s Solver, then you can plug in OpenSolver and start using the COIN-OR solvers with no limits on problem size.  I am also delighted to see that that they have moved to CPL licensing, rather than GPL, which was my only whine in my original post.

Congratulations Andrew and Iain.  If you would like to celebrate this award, there is a reception to attend, thanks to IBM:

All entrants and their supporters are welcome to join in the celebration and regale (rile) the prize winners.

Date: Sunday, November 13
Time: 8pm-10pm

Location: The Fox and Hound
330 North Tryon St.
Charlotte, NC 28202
(Directions: http://tinyurl.com/75zhm7k)

The celebration is sponsored by IBM.

Good work by the committee:

The COIN-OR INFORMS Cup committee:

Pietro Belotti
Matthew Galati
R. Kipp Martin
Stefan Vigerske

Kiwis and open source rule!

This entry also occurs in the INFORMS Conference blog.

The Sexiness of Integer Programming

Suresh Venkatasubramanian, of the excellent Geomblog, is at SODA and covered some preconference conferences. When covering a paper that used integer programming (via CPLEX), his comment was:

It’s not the “sexiest” thing in the world to solve algorithms problems in practice by using large industrial strength packages.

Oh, he didn’t say that, did he?

I spend most of my life “solving algorithms problems in practice by using large industrial strength packages”. I solve sports scheduling problems, logistics problems, and even problems in social choice with large scale integer programming software as my primary tool. Who says I am not sexy? Or, worse, that my research is not sexy?

I can think of a few misconceptions that might lead one to doubt the sexiness of integer programming.

  • Integer Programming is uncreative. After all, you just formulate the problem in terms of variables, linear objective, and linear constraints, toss it in a code, and you are done. Where is the research?

    Such a view ignores the tremendous number of choices once must make in formulating integer programming. The choice of variables, constraints, and objective can have a tremendous impact on the effectiveness of the solver. While solvers continue to get better at automatically identifying formulation improvements, formulating integer programs is still an art. It is an art, however, enhanced by theory. As we better understand the polyhedral characteristics of integer programming formulations, we create better and better formulations.

    This creative effort is expanded when alternatives to “basic” formulations are included. Creating a branch-and-price, branch-and-cut, Benders, or other type of formulation can be the key to solving real problems, but may require significant research effort.

  • Integer programming is slow. This seems to be the most common response I get from those outside the integer programming subfield. One quote from a person at a well-known computer science-oriented firm: “I tried integer programming. It doesn’t work.” Not “It doesn’t work for this problem” or “I couldn’t make it work”. Just “It doesn’t work”. How can a topic be sexy if it doesn’t work?

    I think one of the great stories in all of mathematics and business is the incredible confluence between increased data, faster computers, algorithmic improvements, and implementation successes that have led to many orders of magnitude speed increases in integer programs. Over the last fifteen years, we have gotten much, much better at solving integer programming models. With the underlying linear programming solvers being more than million times faster (no hyperbole: both computers and algorithms provide more than a 1000 time speedup each), lots of instances formerly out of reach can now be solved routinely.

    Of course, integer programming is exponential time in the worst case. But I am not sure why a polynomial time algorithm that gets an approximate solution within a factor of, say, 42 is any “sexier” than an algorithm that finds the optimal solution in a reasonable amount of time for any instance of practical import.

  • Integer programming is expensive. Hey, if you have to spend tens of thousands of dollars for solutions, that really doesn’t count does it? It is like a troll dressed up in a $5,000 suit: it might look OK, but it’s not sexy!

    No one has to pay a lot for high quality integer programming software. Suresh refers to this in his post:

    This was surprising to me on two levels: firstly, that CPLEX is actually free for academic use (who knew!) and that such a simple approach is so effective.

    Actually, all the major programs offer a way for free academic use. I particularly like Gurobi’s approach, which is based on periodic validation through a “.edu” domain, but academics can also get CPLEX (as you would have read on my blog last year) and XPRESS.

    And if you are not an academic? COIN-OR offers “industrial strength” linear and integer programming in an open source approach.

In Suresh’s defense, here is the full quote, where he makes clear his support for this type of research:

It’s not the “sexiest” thing in the world to solve algorithms problems in practice by using large industrial strength packages. However, both CPLEX and SAT solvers are examples of tools that can be used in practice to solve fairly intractable problems. It still takes a lot of engineering and skill to make the heuristics work well, but it’s something that we should be using as a matter of course when designing heuristics before trying to invent an algorithm from scratch.

Suresh obviously gets it: let’s hope his post expands interest in integer programming methods for these problems.

Integer programming is useful, fast, and cheap. If that isn’t sexy (for an algorithm!), then I don’t know what is.

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!

Exciting Times for the INFORMS Meeting

Lots of great things are being planned for the upcoming INFORMS Meeting. Let me highlight two.

First, there is a wonderful series of panel discussions planned (if I say so myself:  I organized this particular track).  The idea is to explore issues of professional interest (rather than technical tracks, which are interesting in their own right but not what we were aiming for here).   I previously asked for advice and feedback on topics, and ended up finding some great panel organizers.  Here is the list we ended up with:

Sunday Nov 07, 08:00 – 09:30 : Panel Discussion: Social Networking and Operations Research
Chair: Laura McLay
Sunday Nov 07, 13:30 – 15:00 : Panel Discussion: OR in Engineering Schools
Chair: Mark Daskin
Monday Nov 08, 08:00 – 09:30 : Panel Discussion: INFORMS Journals
Chair: Terry Harrison
Tuesday Nov 09, 08:00 – 09:30 : Joint Session Invited Panels /JFIG: Success as a Junior Faculty
Chair: Burcu Keskin
Tuesday Nov 09, 11:00 – 12:30 : Panel Discussion: Operations Research/Management Science in Business Schools
Chair: Jeff Camm
Tuesday Nov 09, 13:30 – 15:00 : Panel Discussion: Academic Administration and Operations Research/ Management Science: A Good Combination?
Chair: Cynthia Barnhart
Tuesday Nov 09, 16:30 – 18:00 : Panel Discussion: Skills and Career Paths in Industry
Chair: Ranganath Nuggehalli

I think there is nice variety in the topics.  I am particularly looking forward to the session on social networks.   Laura McLay, Aurelie Thiele, Anna Nagurney, and Wayne Winston will discuss how twitter, facebook, blogs and so on can be used in the operations research world.  Sounds like a great way to start of the conference.  I’ll definitely be there live tweeting/blogging.

The second big activity I am looking forward to is “Forrest-Fest”.  I am a big fan of COIN-OR, the open source initiative in operations research (for a few more weeks, I sit on its Strategic Leadership Board).  John Forrest was one of the key people in the founding of COIN, and continues to play an extremely active role in code development and debugging.  John is “retiring” from IBM;  COIN-OR is turning 10 years old.  The combination is obvious!  It is time for a famous COIN-OR Party!  You can check out their extensive set of talks at their wiki.  The COIN-OR reception is always enjoyable, and is promised to be “thoroughly optimized”.  I do worry the shape of people Monday morning:  robustness constraints are often ignored during the Sunday reception.

Between the program and the city of Austin, I am very much looking forward to the conference.  I hope to see many of you there!

Open source replacement for Solver in Excel

Andrew Mason, who I got to know very well during my year in Auckland, has put together an open source Excel add-in that extends Excel’s built-in Solver (a product from Frontline Systems) and replaces the underlying optimization engine with the optimization code CBC from COIN-OR.  OpenSolver allows the solving of models without limits to the number of variables or constraints.  Andrew has also provided some enhancements including a model visualizer and the capability for fast reoptimization.

OpenSolver works with linear and (mixed-)integer programming models, but not with nonlinear models.  So keep those @IF and @POWER functions away from it!

This add-in a great illustration of both the strengths and weaknesses of open source.  On the plus side, all the work that people put into CBC can now find a much wider audience through the efforts of someone else.  No coordination was needed:  people like Andrew are able to use their own creativity and drive to put together something useful.

However, it is important to note that there are different open source licenses, and that Andrew has licensed this under GPL, while most of COIN-OR is licensed under CPL/EPL.  For most, this licensing difference is not of importance, but any work that is derivative of Andrew’s work can only be distributed under GPL.  Trying to figure out what is a derivative work is beyond me, but is important to those who would like to further develop systems based on Andrew’s work.  I note this fully respecting Andrew’s right to pick whatever license works best for him!

For me, this will be great to point to in class:  MBA student’s love Solver, but get frustrated with size limits.  I can now point to an easy to use add-in that removes those limits without requiring any changes in models.

Open Source = Geek?

The parent of SourceForge.net has decided to become Geeknet, Inc (how much did they have to pay for geek.net, I wonder). I have mixed feelings on this.  On one hand, I am trying to learn from Wil Wheaton and embrace my inner geek.  I have done this so well that my colleagues tell me my inner geek is leaking out quite a bit to my outer geek.  So celebrating geekdom is good, right?

Well, maybe not right.  I am involved in an operations research open source endeavor, COIN-OR.  Part of COIN-OR is convincing companies that open source is not too nerdy or experimental.  There are lots of good reasons to use open source software. Embracing your inner geek is probably not one of the more persuasive.  One vision of COIN-OR was to be “Sourceforge for operations research”.  Now should we become “Like operations research, only geekier?”.

The Sourceforge Blog has an amusing post on the top ten rejected names, including my favorite:

7. FLOSSdaily

I think the entry summarizes the issue correctly:

the consensus seems to be that, as long as we don’t change the name of sourceforge.net, it doesn’t really matter what we call the corporation, so I think we’re good.

But I would be worried about the next “branding” idea from the good people at Geeknet, Inc.  Perhaps their inner geek should stay a little more … inside.

Become Famous by Winning the COIN-OR Cup!

COIN-OR_CMYK-296Do you use COIN-OR (open source software for operations research)?  According to the log files, lots and lots of people do!  If you are doing something interesting with COIN-OR and are planning to attend the San Diego INFORMS Meeting, I strongly encourage you to enter the COIN-OR Cup!  You could join John Forrest, Jonathan Eckstein+Bill Hart+Cindy Phillips, John Tomlin and the team from the Environmental Protection Agency + Sandia National Labs (including Jonathan Berry) as a winner of this prestigious Cup!  Fame and drinks will be yours forever!  Despite appearances, you do not need a John or Jonathan on your team to win, though it seems to help.

More seriously, if you have used COIN-OR in a neat application (or have advanced COIN-OR in a significant direction), it would be great to hear about it through an application for the award.  This would let the COIN people know of all the great ways the software is being used and help bring together the COIN-OR community.  The deadline is October 2, so don’t delay.  And thanks to IBM for sponsoring the reception (which is always a real highlight for the whole COIN-OR community).

Google does Operations Research and Open Source

While Google is, of course, heavily active in analytics, the company has not been known for its operations research. The “ethos” of the company has been heavily computer science based. So, while I would count much of what they do as “operations research”, they probably would not use that label.

The line between operations research and computer science is not easy to draw, but linear programming falls pretty strongly on the operations research side: it is the sort of “heavy machinery” that occurs often in OR. Given the variety of problems a company like Google faces, it is not surprising that they would end up with some problems for which linear programming is the right approach. Or not. In a recent discussion, Vijay Gill, senior manager of engineering and architecture was somewhat cagey on how computer load redistribution was being done:

Gill even seems to be saying that the company hopes to instantly redistribute workloads between data centers.

“How do you manage the system and optimize it on a global-level? That is the interesting part,” Gill continued. “What we’ve got here [with Google] is massive – like hundreds of thousands of variable linear programming problems that need to run in quasi-real-time. When the temperature starts to excurse in a data center, you don’t have the luxury to sitting around for a half an hour…You have on the order of seconds.”

Heiliger asked Gill if this was a technology Google is using today. “I could not possibly comment on that,” Gill replied, drawing more laughter from his audience.

In possibly unrelated, but possibly related, news, the Google Open Source Blog has an announcement of an open-source simplex code:

SimplexSolver is an easy-to-use, object-oriented method of solving linear programming problems. We’re happy to announce today that we’ve Open Sourced the code that runs the newly released Google Spreadsheets Solve Feature and made it a part of Apache Commons Math 2.0.

Thanks to my former office mate in Auckland Hamish Waterer and to Andrew Mason for passing along these pointers.

Perhaps some clarity in Open Source?

I sit on the “Strategic Leadership Board” of COIN-OR (COmputational INfrastructure for Operations Research). There is a lot of great code at COIN-OR, and I find it very useful in my research.

Despite being on the SLB, I get very confused when it comes to open source. It seems that 90% of the discussions on the SLB hinge on either legal issues with regards to open source licenses or on the paperwork necessary to satisfy COIN-OR’s process for meeting those legal issues. It is rather unsatisfying: all of us on the SLB would rather talk about operations research and software rather than legal stuff.

A big part of the issue is the proliferation of “open source” licenses. Check out the listing at opensource.org. There are 65 licenses listed! Who can keep track of all those? And, while there are some sites to help you pick a license, things get more complicated when you combine codes under different licenses.

At COIN, there are a few different licenses used, but the most common is CPL (Common Public License), due in part to the influence IBM has had in supporting COIN.

IBM and Eclipse have announced that the Eclipse standard ECL will supersede CPL. See the postings by Ed Burnette at ZDnet, and by Mike Milinkovich of the Eclipse Foundation (thanks Robin for the pointers!). Mike explains why this superseding was done:

License proliferation in open source is a real issue. It costs businesses to review multiple licenses, and the plethora of licenses can be confusing to someone starting a new open source project.

Over the past five years we have seen the Eclipse Foundation go from a good idea that might work to one of the most successful open source communities out there. We have seen the Symbian Foundation adopt the EPL as its license, thereby bringing a huge community and code base in its own right to the EPL, plus demonstrating the utility of the license well outside of the Java domain that it is best known in. More recently, Google also added the EPL as one of the licenses it supports on Google Code. It is clear that if we wanted to consolidate on one license, that the EPL made the most sense.

Generally I am very happy about this. There will be some immediate hassles as we try to sort out what this means and how this affects COIN-OR. But perhaps this move to EPL will grow larger, and we can get on to the business of creating great code, rather than getting stuck on legal issues.

I do have one question to all developers of open source software in operations research: are you happy with EPL as a license? Are there aspects of that license that you find troubling? Is anything a deal-breaker, meaning you would not license under EPL but instead would insist on another open source license for your work?