Operations research (OR), or operational research in British usage, or recherche opérationnelle en français, is a discipline that deals with the application of advanced analytical methods to help make better decisions. [source: Wikipedia]

If you grab your favorite text book, you will learn about its origin as part of the war planning efforts. In this blog post, I will describe three practical "mundane" problems I had to deal with recently and how you can solve them using off-the-shelf OR tools.

For people who want to go deeper, Cornell Tech offers a Masters of Engineering in Operational Research and Information Engineering (more info about MEng ORIE).

Problem #1: assigning reviews conference papers

I am helping my good friend Gideon Mann at Bloomberg with the 2016 Data for Good Exchange conference (check the call for paper; we still accept submission). This is a modest size conference but we have a terrific program committee (PC). PC members have their respective expertise, interests and also conflicts, e.g. papers they authored or papers authored by someone they know. Humans being humans, reviewers are more likely to do a good job if the papers they are assigned to correspond to their tastes. Also each papers must have at least 3 reviewers. You may also think of advanced rules, e.g. for papers authored by a PC member.
What's the best assignment of papers to reviewers?

Problem #2: assigning students to company challenges

During their first semester, Cornell Tech students take part in company challenges, where students work on a challenge submitted by a company (if you want to submit a challenge, check here).
Students express preferences about challenges based on the company and the challenge itself. Teams have to be balanced in terms of skills, expertises and profiles (MBA vs MEng). Teams also have to be balanced in terms of numbers with no single-member team.
What's the best assignment of challenges to students?

Problem #3: hacking the hackathon

For the last 3 years, I have had the great pleasure of helping with the organization of the NYU Abu Dhabi International Hackathon for Social Good in the Arab World.This is a three-day programming marathon where teams of computer science students from all over the world (the majority of the students will be from the Arab world) work to solve social good problems. This a special event because it mixes students, mentors, experts from totally different origins. The goal is not only to create awesome hacks but also to create connections between people and culture.
Unlike other hackathons, participants first do ideation to come up with interesting ideas. Then they vote on the ideas and we pick the best 15. Finally, they choose which idea they want to work on.
Teams have to be of reasonable sizes, no less than 3, no more than 7.
Teams have to be balanced in terms of gender, region of origin and skills.
The event is hosted by NYU AD, in the United Arab Emirates. We want NYU AD students and UAE students to be working with people they don't necessarily know.
What's the best assignment of ideas to students?

A proposed solution

As you have probably guessed already, these 3 problems are very similar and can be solved using the same method. We are going to walk you through the solution we used for the NYU AD hackathon, based on linear programming.

We have a set of students and a set of projects.
Students express preferences about projects by ranking them (e.g. 1 for first choice, 2 for second choice, etc.). This defines a matrix Student × Project where each cell contains the ranking.
One way to represent an assignment is to consider a matrix Student × Project where each cell tells us if the student will work (value = 1) on the project or not (value = 0).
We also define an objective function that will represent how well we respect the choices of students.

We also define some constraints:

  • each student is part of one and only one team
  • each team consists of a minimum and maximum of students
  • each team consists of a minimum and maximum of international students
  • each team consists of a minimum and maximum of female students etc.

Given the nature of the hackathon, it would counter productive for someone who generated an idea that got selected not to be able to work on their idea. Therefore, for some special cases, we want to pre-assign students.

A mathematical formulation

Here is how this kind of problem is formulated.

S, set of students.
P, set of projects.
Assignment project–student: A[i][j]∈{0,1}, i∈P, j∈S.
Students express their preferences by ranking projects (first, second, etc.): R[i][j], i∈P, j∈S.
Students have some specific properties, e.g. gender G[j], j∈S.

The goal is to minimize the objective function

Given the following constraints:
1. each student is assigned to only one project.
2. each project has between r and r' students.
3. each project has between g and g' students of a given gender.

mathematical formulation

A possible implementation

Here is how this can be encoded using Google OR-tools.

Experience and future work

Does it work? Yes it does. You can get an assignment in less than a second. And if you don't like it, you can tweak some values, add or remove constraints and get another one instantly.

The hackathon was the second time I ran the algorithm. I ran it very successfully when 80% of the students had expressed their choices. When I tried with the full set, the algorithm kept returning an empty solution. I thought this was due to a limitation in the algorithm (no!), some arabic name encoding glitch with Python (no!). I did not realize that some of the constraints could not be satisfied (silly me!).

Here are a few things I am looking at for the future:

  • a better packaging of Google OR tools to make it super easy to install
  • a way to encode more interesting constraints like "A or B"
  • a way to define constraints that reference dynamic values, e.g. "the size of the team"
  • a way to create soft constraints to avoid the "no solution" outcome
  • a nicer user interface that can automatically generate the form to be sent to students and display the results.

Conclusion

Large companies like Uber, Google, Amazon, etc. deal with optimization problems every day and make a fortune solving them at scale.

But such optimization problems are everywhere. Whenever you need to assign people to "things" and you know you cannot make everyone happy, you have an optimization problem in hand.

In this blog post, we showed you how you can quickly and easily leverage integer programming using Google OR tools to solve such problems. We hope OR techniques are going to be part of your toolbox from now on.

Interesting resources

Some software

Some books

  • F. S. Hillier and G. J. Lieberman, Introduction to Operations Research, McGraw Hill, 2009, 2012, 2014.
  • R. J. Vanderbei, Linear Programming: Foundations and Extensions, Springer, International Series in Operations Research and Management Science, 2014, 2007, 1998.
  • D. Bertsimas and J. N Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, Series in Optimization and Neural Computation, 1997.

Special thanks to Jai who encoded a first version of problem for me, using the Google OR-tools.