LSE - Small Logo
LSE - Small Logo

Bento Natura

October 22nd, 2020

5 Minutes with Jim Orlin: algorithms for network flow

0 comments | 1 shares

Estimated reading time: 10 minutes

Bento Natura

October 22nd, 2020

5 Minutes with Jim Orlin: algorithms for network flow

0 comments | 1 shares

Estimated reading time: 10 minutes

Jim Orlin is the E. Pennell Brooks (1917) Professor in Management at MIT Sloan School of Management, and is currently a Visiting Professor with the Department of Mathematics at LSE. Jim also gave a talk at the Department’s Seminar on Combinatorics, Games and Optimisation in February 2020.

In this interview, Bento Natura discusses Jim’s research, his work at MIT and what he liked most about his time at LSE.

Hi Jim, can you just tell us a little bit about yourself?

I’m a faculty member at the MIT Sloan School of Management and I’ve been on the faculty for more than 40 years now. My specialty in research is optimisation algorithms, especially relating to network flow algorithms. I worked a lot on shortest path algorithms, max flow algorithms, min-cost flow algorithms and related other optimisation problems as well as some applied problems.

Could you explain in layman’s terms, what these optimisation problems that you mentioned are about?

For the shortest path problems, the easiest way to consider it is in GPS systems where you’re trying to get from one place to another. And if you look at your GPS, it will tell you the fastest path.

The shortest path algorithm is what lies underneath that, let’s assume that you’ve got all the data about how long it takes to travel along any street, then you can compute the shortest path from your starting point to your destination efficiently.

For other problems such as the max flow problem, imagine you’ve got a communication network and you’ve got bandwidth and you want to communicate with someone, let’s say communicate between someone at LSE and someone in the United States.

The question that arises if you know all the bandwidth is: what is the most communication you can send per unit time? And that can be computed as a maximum flow problem.

You mentioned that you are for more than 40 years a faculty member at MIT. You also wrote one of the classic books on network flows and now nearly 30 years later still publish exciting research on faster shortest path and min-cost flow algorithms. Do you feel that for one of these problems, we finally found the lower bound, where even some logarithmic factor cannot be shaved off anymore?

One can almost always make things a little bit faster on real computers.

If you think about the improvements in computers and computer programming over the last 50 years there have been amazing improvements in hardware, in speed and in costs. But for a lot of problems there have also been important improvements in the speed of algorithms themselves and people are always developing new algorithms.

That is the mathematics of computer science. So, there’s an incredible amount of mathematics in that area that is constantly being developed and that is important.

Within shortest paths we might reach our limits as to how fast we can improve things. Within some of the problems I’ve worked on like max flow and min-cost flow, it is hard to know whether we have reached our limit.

Now that you also just mentioned that you work not only in theory but also a lot on practical applications. Can the fastest or the best theoretical results be applied in practice,  or do you almost always have that in practice your algorithms will be application specific and many heuristics that in theory might not work that well instead are in practice the best performing? How big is the difference between the two?

For many problems, the best practical approach relies on starting with the best theoretical approach and then using some heuristics to speed them up. So, theoretical algorithms have often contributed to important results in practice. That’s not guaranteed to be so. A classic example is fast matrix multiplication, which is theoretically incredibly fast, but unfortunately the size of the matrix where it’s faster than ordinary matrix multiplication is too large, and it ends up being impractical.

Would you say that in the last decades your focus in research has changed?

I would say that more than most people, I am a creature of habit and my research over the years has been pretty similar. I like being eclectic occasionally and working on something different, but my research over the years has been pretty consistently on trying to develop faster algorithms for network problems. In terms of a focus, I would say that I’ve had a constant focus, both on research and teaching.

In particular, at MIT, with the CSAIL lab, the new Schwarzman College of Computing and start-up spin offs like Boston Dynamics and you being yourself affiliated with the Sloan School of Management, did these initiatives influence your research, your collaborations, or maybe the roles and responsibilities that come with it?

There’s a lot of exciting things going on at MIT in the area of computing and the Schwarzman college, I think, is very exciting. On the other hand, although I’ve tried to keep up with what’s going on at MIT, I’d say it probably hasn’t had much impact on my own research.

Computer science is getting more popular, especially because of the rise in machine learning in the last decade. Could you, for a student who decides what degree to choose, explain how your research might also relate to machine learning, how these two intersect and what tools are used in your area and in the area of machine learning?

Optimisation, not necessarily the specifics of my own research, but optimisation plays a huge role in machine learning and I have a colleague Dimitris Bertsimas who has been using what’s known as integer programming to solve lots of problems in machine learning. Sometimes with results that are better than the more well-known techniques in machine learning. Integer programming is just solving an optimisation problem where the objective is a linear function, and the constraints are linear. But the sum of all the variables are constrained to be integer. It sounds quite technical, but it can model an incredible number of real-world problems.

In recent years research in the areas of optimisation is increasingly also done at companies. What would your advice be for young researcher, who decides between joining a research group at a university or alternatively a research group in a company?

I think for a number of companies, it depends on the student as to which they will enjoy more, and which gives them a better career path. I think academia and industry both have a lot to offer for people interested in computer science, machine learning and optimisation.

LSE does not teach pure mathematics, electrical engineering or computer science. What would you recommend to a student who studies at LSE, and in the course on operations research suddenly realizes or develops a fascination for these topics, or even more general for theoretical computer science?

I don’t have specific recommendations, other than talk to faculty and administrators and tell them what you’d like to do and see what they can recommend. I really liked the people at LSE. They were very friendly and very concerned about doing a great job for students. I interacted almost entirely with the math department. I thought the math department is filled with very good people.

Unfortunately, your visit was cut short. Nonetheless, what would you say was the best part of your stay at the university?

Two parts. One was, of course, just being in London with my wife, and we really enjoyed our time in London. The second thing I would say is that I worked with a colleague, László Végh, at LSE and really enjoyed my interactions with him. And actually, the research has led to already one very good paper (Note: The paper just got accepted to SODA 2021).

About the author

Bento Natura

Posted In: 5 Minutes with | Algorithms | Featured | General | Machine Learning | Networks | Operations Research | Optimisation

Leave a Reply

Your email address will not be published. Required fields are marked *