The MIP Computational Competition 2023

On a random day in October 2022, Federico told me that there was a MIP competition, in which I could not resist participating. I knew that he participated in a MIP competition that year about developing heuristics for MIP solvers. I was not aware of it, so could not participate myself. Nevertheless, I helped Fede with some tips a few days before submission. This time he wanted to include me in his team for the competition this year.

A few weeks later, he sent me the competition details page. This competition is a part of the MIP workshop. I attended the 2019 edition at MIT. That was just a year before I started my Ph.D. This workshop is well-known in the community. Only the invited speakers get to present their work at this workshop. There is a special poster competition in the workshop for students. Winning this poster competition gives a big boost to a student’s career.

Before starting my Ph.D., I worked on discrete optimization solvers for about 4 years. I never published any of my work. So, naturally, no one in the MIP community knew me well. This competition was an opportunity to showcase my skills.

Besides the fame, the organizers also promised an expedited review process for publishing the competition work of finalists in the Mathematical Programming Computation (MPC) journal. That’s a good quality journal, in which I was anyway targeting to publish a paper for one of my Ph.D. projects. The finalists also get to present their work at the conference.

This competition was not limited to students. So, we can reasonably expect the ‘professionals’ to win it (like last year). However, the jury may recognize an outstanding student submission. Even that is a big deal for a student. Fede’s team won this recognition last year!

Anyways I realized that Fede’s planned team was too large (7+ people). I am usually not so comfortable working with large teams. So, I decided to participate alone. That’s a risky move. If I didn’t do well, there were many people just waiting to call me arrogant. But somehow, I was confident that I would do well.

So, the approach was simple. Start with the baseline approach and try to just beat the current best results. I listed down some ideas and started working. Very quickly, I realized that there were too many ideas and that a teammate might help. I tried to find one but couldn’t. I wanted a student member (so that I could keep my chances to win that student recognition), and Fede had hired almost all students on the floor. My lack of contacts was hurting me now.

So, I had to do it all by myself. Which means, I had to pay more attention to assigning priorities. Complex ideas with potentially big but highly uncertain improvements had to be deprioritized. Simple ideas first. A results-driven approach. Throw away the idea if it doesn’t improve the benchmarks, no matter how deeply I love it.

Later on, I also learned that one of my Ph.D. advisors, Andrea Lodi, was also participating in this competition. Whoa! The stuff just got real. He is a known expert in MIP. He worked with CPLEX (one of the state-of-the-art MIP solver) team for over 15 years. I was inspired by his research when I was working on solvers. That’s why I applied to do my Ph.D. with him as my advisor. Wouldn’t it be a dream to perform better than him in this competition? He said he was participating very lightly with a small team. So, I might have a chance! I was way too serious about this competition.

Anyway, some ideas worked, and some did not. I had to constantly keep my emotions under check. Don’t get demotivated or too excited. Just move on to the next idea. In the end, I was satisfied with the ideas I tried. I knew that I was not so good at academic writing yet. So, I spent extra effort writing my report.

The deadline was near. I was on schedule. I had nearly finished my tasks. Just around that time, the competition organizers decided to extend the deadline by 15 days. Like why? What do I do for another 15 days? I tried perfecting my report for a few days. Then I decided to submit my report a few days early. The competition chair pointed out that I was too early. I cited Parkinson’s law in reply: “The amount of work expands to fill the time available for its completion.” Besides, I have to behave like a champion if I want to become one, right?

That’s it. The competition was over. I was now counting the days till the results announcement date. They were going to announce the finalists (and potentially student recognition) on that day and the winner during the workshop.

Just a day before the scheduled announcement day, I received an email from the competition chair that said the following in the beginning:

Dear Krunal,

Thank you very much for your patience while we were evaluating the results of the MIPcc23 computational competition.  I am very happy to inform you that you have been selected as the winner of this year's competition. ...

Wait what? Winner? Really? Time to start jumping around (I did it literally! I am only grown up on the outside). They said they would officially announce it during the workshop. My submission needs some polishing, but they will give me an expedited review for publishing my work in the MPC journal. And I get to present my work at the workshop along with other invited speakers!

I shared this news with my Ph.D. advisors (along with a thank-you note for training me), and they were pleasantly surprised. After the results announcement, I also shared this news with the OR team manager at Google. My work on the solvers at Google gave me the essential training to win this competition, so naturally, my mentors there should feel proud too.

I received quite a lot of attention at the conference after my presentation. Some of my heroes in the community whose research I used to read (and still read) congratulated me, asked me questions on my approach, gave some suggestions, and said that they really liked my presentation! This opened some doors for future projects and collaborations as well. What more can I ask?

This is how the jury described by submission.

The submission convinced the jury not only through its computational excellence that was displayed by the top ranked performance on almost all public and hidden data sets, but also through its broad applicability and attention to algorithmic details. Building on top of an existing LP-based branch-and-bound solver, the approach distinguishes itself by targeting multiple aspects of the solving process in combination. The reuse of primal information and pseudo costs from previous solving processes is safeguarded by clever methods to re-evaluate and complete this information. By analyzing the success rates of individual solving techniques, the approach learns improved parameter configurations online despite the limited number of observations.

Moving forward, I will obviously work on this project and publish my work later. At Google, I learned a lot about solver development by reading various research papers. After reading each paper, I summarized the key ideas in a Google doc. This was like a personal library. So, now I decided to start a YouTube channel and record the summaries of the papers I read. This will hopefully help some students as well as will give me some teaching experience. I hope to build a video library for various solver development ideas over a long time. Here is the link to the playlist. It also has a video describing my ideas for this competition.

My favorites

Video: NASA reinvented the wheel (Veritasium)

Quote: “The quickest way to fail is through procrastination. If you make the decision quickly and you get it wrong, you can pivot and pull yourself back on track.”—Robin Waite, Take your shot