The (Un)common Lisp approach to Operations Research

Common Lisp is not getting the attention it so deserves. Last month, I posted a poll on the INFORMS LinkedIn group with the title: “What language do you use for prototyping in OR?”. The results are telling — it’s almost embarrassingly funny:

Yes, I am a loner. The more the reason for me to stick out my neck and try to make a case for using Common Lisp in the Operations Research (OR) discipline. This post is about how and when you may want to consider using Common Lisp as an alternative approach for OR. But first a preamble, why should you care?

The future of Operations Research

Well, what is Operations Research anyway? In 12 words, the Science of Better swears by OR as

“The discipline of applying advanced analytical methods to help make better decisions”.

When I chant this mantra in an attempt to explain what I do, I rarely get a sincere nod of genuine understanding — rather a polite “U-huh” followed by an awkward silence. It is not their fault; it is a rather vague and fuzzy multidisciplinary field, often confused with Operations or Research. And even though the field has roots extending well back to WWII, it hasn’t commanded the respect of the industry (yet).

One source of confusion is in the name. OR is currently the most commonly used name to describe the field, with terms like Management Science and Decision Science being almost synonymous. But these terms are useless when you search for jobs — you’ll have more luck pretending to be a statistician/mathematician or rather use the more commercial-sounding term ‘Analytics’. Since OR is such a diverse field, it overlaps with many other disciplines, e.g. Industrial Engineering, Statistics, Datamining, Operations Management and notably Artificial Intelligence.

Due to the advent of computing power, OR techniques developed in the 50s are finally becoming computationally tractable to solve complex real-life business problems. OR-ites like myself get the most excitement from tackling notoriously NP-hard problems, such as the Vehicle Routing Problem. When they were studied half a century ago, they were concerned with only small-sized laboratory problems. Larger real-life problems were simply computationally intractable. No longer the case.

You also need data to apply OR on. Well, that’s not a problem either anno twenty-twelve. To have a proper IT infrastructure has become de facto standard for sized corporation, which has allowed them to collect the prerequisite data, but unfortunately, the next step into OR does not come naturally yet.

To give you an example, I once saw a business proposal from an IT firm to set up an IT infrastructure for a South-East Asian shipping company. The shipping company even lacked a basic administrative system to keep track of their orders and their fleet, so to deploy an IT system would surely add a lot of value. But they stopped there and failed to hear the Pavlovian bell that those in OR hear loudly — such data/infrastructure can easily be leveraged to generate optimized routing and scheduling solutions!

Despite the fact that Genetic Algorithms are half a century old, they still carry the sound of futurism or shamanism. Thanks to waterfalls of success stories and the plethora of data at arm’s-length, businesses are ever so slowly but surely succumbing to the inevitable.

Research conducted by McKinsey Global Institute even shows that there is a huge shortage of people with analytical expertise. They also project that by 2018, the US may face “a 50 to 60 percent gap between supply and the requisite demand of deep analytic talent.”

So now that computation power has become a liquid commodity like raindrops in the cloud, the amount of data is doubling every two years, and words like Analytics and Big Data are ‘cool’ to be thrown around, is it finally time for OR to get buzzing this decade? Only time will tell — what say you?

Approaches to OR

Due to sheer diversity of the discipline, there are simply too many valid approaches to list/cover them all, but there are noticeably two major ways to go about applying OR: Modelling and Programming.

In short, modelling does not involve too much coding and uses (commercial) software packages to ‘model’ a problem. Programming would be about writing code from scratch or using open-source libraries, to custom-tailor a piece of software to the problem at hand. Different approaches for different problems.

Modelling

OR involves a lot of mathematical modelling. Almost every paper published in the field will have a chapter describing a mathematical model, before they go into the solution approach. Unsurprisingly, plenty of software packages have been developed that allow you to ‘feed’ these mathematical models into the computer, which then can be optimized with time-tested algorithms.

The logical approach would be to find a software package that closely resembles your needs, and abstract the problem at hand in a way that ‘fits’ in the software. You might have to cut corners here and there.

Some of the most recurring modelling software mentioned on the LinkedIn thread were Matlab, AIMMS, AMPL, R and even Excel. Modelling packages most likely account for the majority of the ‘Other’ category in the poll.

Note that Matlab is kind of floating in the middle in the diagram. I would still classify it under Modelling; even though it is possible to write your own algorithms/models in the scripting language, you wouldn’t use Matlab for that purpose — Matlab’s strongest features are its plotting tools and the extensive toolboxes that you can exploit to see something really quickly, very suitable for educational purposes. As for programming, even Java would be better suited.

Simulation is another very popular approach to OR — mainly due to the graphical aspect of it — and is another example of Modelling in OR. You model a real-life situation as closely as possible in your favorite simulation software, play around with some parameters, and study the results. Again, not much programming required when you use packages such as Simulink, Arena, Simio, etcetera. Of course, there are also plenty of low-level open-source simulation libraries in which you will need to code.

The Modeling approach is an appropriate way to solve a wide range of problems faced in the real world. However, licensing for such software packages are not always within budget and are, perhaps, an overkill by sledgehammer — we don’t need all the whistles and bells.

For the class of problems not properly covered under the Modelling approach — e.g. the complex large-scale NP-hard problems that require custom meta-heuristical approaches — we will need to get our hands dirty, and resort to coding to truly tailor the optimization algorithm to the problem. Alas, but not too dirty please!

Programming

Programming is an experience. The experience is contingent with the choice of your programming language. Remember that experience is personal; it is therefore important to know what you get yourself into — especially when you are trained in OR and not Computer Science. The agonistic experience I had with Java and Matlab (my only exposure to programming at the time) got me derailed from my OR career. I went on to become a stock trader instead. Now I’m back with a vengeance. My programming passions have been reinvigorated by a discovery of an alternative: Common Lisp.

To get a grip on all the programming languages out there, it is useful to classify them by low/high-level. Disregarding machine and assembly languages, C would be a very low-level language, requiring you to deal with all sorts of garbage that keep Computer Scientist busy, but are a nuisance to most OR people. On the other end of the spectrum, you have the higher-level languages of Python, Ruby and on top of the hill: Lisp.

With abstraction comes power. The higher the level of the langauge, the quicker you can get to a working prototype. Your code is more concise, hence agile, so you type less and you debug less.

“Writing code in CL may be really quick but writing a fast running program may be really hard,” Ozgur I. from Anadolu University commented. Even though Ozgur concluded with “I love Common Lisp,” he still voted for Python for prototyping and left me remaining as the only one voting for Common Lisp. “[When] implementing real life systems which require heavy number crunching, C/C++ will be the choice,” he added.

It is a fallacy, however, that higher-level languages are by definition slower than lower level languages, as Peter Norvig — Director of Research at Google — points out in a benchmark study, further corroborated by a NASA study at CalTech. Although in most cases it is true that low-level languages are faster, Lisp seems to be an exception to the rule.

“[I] have never really found [Lisp] more suitable … for anything other than my grad school AI course or for teaching AI,” as Muaz N. from Springer CASM commented while voting for C++. During his 16+ years of professional and academic career, he said he hasn’t seen any Lisp outside of AI and stuck to C++ because of its presence.

Lisp has strong associations with Artificial Intelligence — not surprising since John McCarthy coined the term AI and was the inventor Lisp.

OR extends widely in the field of AI (data mining, meta-heuristics, optimization,…), so why did Lisp not catch on in the OR community by association?

The AI boom that happened during the sixties was around the same time the OR field was taking shape. At that time, there were only three modern programming languages, including Lisp in 1958 (Common Lisp as we know it today appeared in 1984). Java only appeared in 1995, yet has a much larger presence in general and even specifically in the OR industry. Lisp is a much stronger language by objective standards and had a four decades head start. What went wrong?

I don’t know, it could’ve been due to the random, but unfortunate course of history, akin to the Maya collapse. A mystery and a pity. Not completely the same, to be fair, since Lisp can be revived.

“I use Java. I like the flexibility, the ability to connect easily with databases, and the many algorithms already coded up for Java and freely available on the web,” says Charles R. from Conway Freight.

I think one of the biggest factors at play here is the ‘Network Effect’. The more a language is used, the more libraries there will be created, the more optimized the solvers would be — the more people will choose that language. This is kind of the reasoning behind Muaz’s decision as well. I suppose I fell for this myself; I opted for Java to write a Tabu Search algorithm, because of the Open Tabu Search framework hosted on COIN-OR. Now I think I know better.

When you choose a library/framework, you’ll have to learn how to use the library/framework, which requires you to use the language that they were originally designed in. So I landed back in Java and I probably wasted 80% of my time on debugging and figuring out Java’s workings under the hood in order to debug. In about half the time I wasted, I rewrote the whole model from scratch in Common Lisp earlier this year, now available as open-source.

To come up with an idea for a great algorithm or model can take a few hours on the whiteboard — to test that idea can take months. To shorten the idea-implement-test cycle is beneficial to mankind, which is why I vouch for Common Lisp. Because of the power of the language (dynamic typing, functions as first-class citizens, metaprogramming with macros,…) algorithms can be written much more concisely. Not only will it save you typing, it will be much easier to debug.

I started this section with an emphasis on experience — programming should be fun. The experience of programming in Common Lisp is especially pleasant because of the REPL — an interactive environment in which you can evaluate chunks of code and get immediate feedback; the best way to quickly test your steaming idea while it is still developing in your head. It truly enables rapid prototyping in a way ‘rapid’ was not defined before. The biggest complaint I have for the otherwise beautiful high-level language Ruby, is the lack of a true REPL — interactive shells just don’t do the trick.

Concluding remarks

Nobody in business likes equations; they just want to see results.

Mathematical models are a wonderful convention for maintaining the intellectual discussion in academia. To know the common language of mathematics is imperative if you want to contribute to literature or be able to stand on the shoulders of giants. The Modelling approach is designed for the mathematicians who think primarily in mathematical models, and facilitates the translation from the mathematical models to the computer.

But what if you don’t like math, but have a knack for coding and a lust for applying OR in practice? Note that the Programming approach to OR does not require any mathematics at all! Programmers may skip the step of mathematical models altogether and just focus on the true problem that the business is facing. When devising a meta-heuristical algorithm, producing 5-pages of LaTeX math symbols may seem impressive (perhaps required to get your grades/brownie points), but are surely unnecessary and irrelevant. Just focus on the problem at hand and model it directly in a piece of software.

Keep in mind that in many cases using the Modelling approach may save you a lot of time. But once you need more control or prefer open-source software, then the Programming approach is more fit; do yourself a favor and give Common Lisp a true try — trust me, it’s not just another language. Just Google it when you have a moment. I think the only reason why Common Lisp does not have many users, is because of the lack of users.

Advertisement