From Hard Problems to Proven Solutions: Solving Decision Problems with Gurobi

Speaker 1 [00:02]

Hi everyone. Welcome to Europium. We'll shortly start the talk in a few minutes. Before I start the talk, just housekeeping a little bit. If you have any ideas for or are interested in lightning talks, we really encourage you to submit your ideas at the lightning talks booth. I think it's going to be happening tomorrow. Next up, if you have not already muted your mobile devices please do so. I also encourage you to not possibly leave the talk in the middle of the talk if possible. So in this session we have Silke from Gurobi who is going to walk us through her talk about hard problems to proven solutions and at this point I'll just hand over the mic to Silke. During the talk if you have any questions please use the the website to add your questions and we'll take them after the talk.

Speaker 2 [01:12]

All right. Thank you, Shai, for that nice introduction. And thank you all so much for coming. So in this talk, I want to take you on a journey from hard decision problems to proven solutions for those problems using Gurobi. So let's start with a simple question. Imagine you run a consulting company. You have a handful of teams, a list of projects, and not enough capacity for everything. So the question is, who should work on what? How would you solve this? Well, you could try all combinations if you have a few million years. You could write a creed heuristic and hope for the best, or ask your favorite LLM, which will give you a very confident answer that may or may not make sense. But if you actually want the best solution, this is an optimization problem and the nice thing is we can solve this systematically so let me show you what that means what is mathematical optimization at its core every optimization problem has three ingredients first the decision variables what are we trying to decide in our In our example, this will be, should Team J take Project I? But the same idea appears everywhere, like trucks, investments, scheduling talks at PyCon. Second, the objective. What does good actually mean in our problem? Do we want to maximize profit, like in our example, or minimize cost, reduce risk, something else? And finally, constraints. What rules must we obey? Here, each team has limited capacity. In other problems, there might be budgets, time limits, the laws of physics. And these define the feasible space. And now, the goal is simple. Find the best solution within all constraints. All right. So far, this might still be a bit abstract. But the interesting part is this exact structure shows up in real-world problems all the time, and often at a much larger scale. So let me show you a few examples. The first one is the NFL, the National Football League, in the US does their game scheduling using mathematical optimization with Gurobi. They have 32 teams, 272 matches, and there's millions, trillions of potential assignments. So you can imagine this as an enormous combinatorial puzzle that actually used to live on physical boards, like the one in the image, with planners manually moving the fixtures around. But now this is translated into a mixed-integer optimization problem. and here there are many very complicated constraints like broadcasting time slots travel and time zone limitations rest days etc due to the size of the country and everything this is much more complicated than the German Bundesliga and of course you want to maximize the profits from broadcasting rights so the best games should be slotted into prime time and in fact this problem is so complicated that a decomposition and parallelization approach is needed to solve it in adequate time. Another example comes from aviation. Air France uses optimization for tail assignment. So what is this? The flight schedule is fixed, and it tells you when flights happen and what type of aircraft. But then you need to assign specific machines based on bookings on those flights and other operational constraints. And here we balance multiple objectives at once. We maximize fleet utilization, so we'd rather keep the planes in the air than park on the tarmac. We want to maximize on-time performance and, in particular, minimize cascading delays. We want to minimize fuel consumption, contain operational costs, like repositioning lags or airport fees. And we want to honor preferential assignments like assigning newer Airbus A350s to key long-haul routes. And now, of course, this real problem is quite complex, but we brought a much smaller and simplified version of this to our booth. So you can try solving an aviation assignment problem yourself. And even though it's simplified, it's still surprisingly tricky and if you solve it you get a free copy of our book optimization for dummies so come by later and visit us at our booth so all the problems I've told you about are too complex to solve manually so how do we actually solve them in practice this is where optimization solvers come in and and Gurobi is one of those solvers. Gurobi takes the mathematical problem formulation, like what we had before, decision variables, constraints, objectives, and computes an optimal solution. And what's important is, it doesn't just find any solution, it uses mathematical methods to give the best possible solution with guarantees. How exactly it solves the problems Algorithms is a deep topic on its own and definitely out of scope for this talk. But it's not magic and it's not a black box either. It's just mathematics. So, Gurobi uses well-established algorithms like branch and bound and cutting planes and others. So, everything is based on mathematical theory and the guarantees come from that. The company was founded by three people who have been shaping optimization for decades. From left to right, Bob Bixby, Song Hao Gu, and Ed Rothberg. And this is also where the name Gurobi comes from. So it's free for research and teaching, and what I'm really proud of for non-profit organizations. So we have many really amazing partners who use Gurobi to make the world a better place. For example, the ocean cleanup removes plastic from the oceans and they have quite difficult models to optimize their routes because they need to take into account weather conditions and the plastic concentrations in different areas. Or I just recently gave a license to a very small NGO in Ghana who built four vans into mobile clinics and then uses Gurobi to optimize their routes and equipment. So this is not just theoretical, Groby is used in real applications across many industries. We have more than 3,000 customers globally, you can see a few of them on this slide. And what's important is it's a general purpose solver, it's completely industry agnostic. So it doesn't come with a specific application, instead it's integrated into business systems. That's why you see it in such different domains from sports scheduling to aviation or cleaning the ocean. So, what types of problems does Gurobi solve? You don't need to read or understand every line here. The main point is it can handle a wide range of problems. At the simplest level, here at the top, we have linear optimisation. Here all constraints are linear and all decisions are continuous. That is, we allow fractional values. And then in the middle, we add integer variables and end up with mixed integer linear optimization problems, or also called MIP. So here you have to make discrete choices, like there's no decisions in our assignment problem, because we cannot assign half a project to a team or send half a truck somewhere. And this makes the problem much, much harder computationally, but of course also much more realistic. And beyond that, we can handle quadratic and even non-linear models. So this covers a large class of real-world problems. So the solver is very powerful. The next question is, how do we actually use it? Gurobi supports many programming languages, but Python is by far the most popular. Our Python package is called GurobiPy, and you can simply install it via pip install GurobiPy. And it already comes with a free size-limited license that is enough to solve the aviation problem at our booth, for example. And then the workflow is very natural. You define the variables, add the constraints, set an objective, and then call optimize. And that is what we'll see next. So let's go back to our example from the beginning. So the question was, who should work on what? Now let's turn this into something we can actually solve. So we have a set of projects and a set of teams. Each project gives us profit and consumes resources. Each team has limited capacity. So we define a decision variable, assign project I to team J, that's this one here in blue, and then we add two constraints. The first one, don't overload the teams, and the second one, each project should be assigned at most once. And of course we want to maximize the total profit. So, this is a classic mixed integer optimization problem. Mixed integer because of the binary variables, the xij should be 0 or 1 over there on the right. And this is exactly the type of problem that Gurobi is built for. So, now let's actually solve this problem in Python. Here you can see the data frames that we use as input. There are three of them, and I'll just show you the first few lines so you get an impression of what they look like. Let's go into the code. We use two packages, the main GurobiPy package, and we also use GurobiPy pandas that lets us combine this very naturally with pandas. So first we create a model and we want to maximise and not minimise. And then we define decision variables. And what's nice here is that we attach the variables directly to a pandas data frame. So each row corresponds to one possible assignment. And with this code, we also set the objective coefficients by using the profit column of the input data frames, the obj equals profit part here. And here you can see what this data frame looks like. It contains the optimization variables in the x column. Next we add constraints. Capacity first. So we group our variables by team and sum up the resource usage, and then this should be less or equal than the team's capacity. And again, this is what the result looks like. And similarly, we ensure that each project is assigned at most once. Again, we group a project, sum it up, and this should be less or equal than one. And then we just call model optimize, and that's it. Now we can query the solution. So we query the x attribute up there after the gppd.x, that's the x attribute that gives us the solution that the solver found. And then we pretty print the result. And we get something like team T0 does these projects and T1 does those, and so on. And we also print the maximum profit that we get from this assignment here. So we solved a problem using an optimization solver that would be infeasible to do manually. And we know, because of mathematics, that the solution is optimal. But a natural question now is, why did it give us this solution? So a manager might ask, team 1 wanted to work on project 9. Why didn't they get it? So let's just test it. We force this assignment. We say team 1 should absolutely get project 9 by setting this variable to 1. And then we solve again. And now we compare the result, and the objective value goes down. So even though this assignment might look reasonable locally, globally it's worse. And that's why the solver didn't choose it. Now let's ask a different question. What if we change the situation? For example, a manager might ask, what if we add more capacity to a team? That is, we hire someone or move someone between teams. So instead of solving the model again and again, we can define multiple scenarios and then solve them in one go. So let's see how. We need to set the number of different scenarios, three in this case, then walk through them and add our modifications. We keep scenario zero as our base model, then in scenario one, we increase the right-hand side of the capacity constraint for team zero, so we add capacity there. And in scenario two, we move capacity from team one to team two. And when we now call optimize, Gurobi solves all scenarios together. So let's compare the results. Here it is. We see that both changes improve the objective. But interestingly, we can see that in this case, moving the person from team one to team two is actually better than hiring a new person for team zero. So something like this can be very useful for decision support. Optimization doesn't just give you a solution, it helps you explore alternatives and understand trade-offs. So now let's compare this to a very different approach for solving such models. You might wonder, could I solve something like this using an LLM? And I've tried this with ChatGPT, and interestingly, it did solve it. So if you remember what we had previously, this is the exact same solution that Gurobi found, but ChatGPT used a MIP solver in the background. And I actually tried with different LLMs and different models, and it always recognized that this needed to be formulated as a MIP and solved using a MIP solver, even, for example, free version of ChatGPT did this. It was surprisingly hard to prevent it from doing this, I guess because the precise problem formulation was such a strong hint that this needed a MIP, but when I somehow forced it not to, it non-surprisingly arrived at a suboptimal solution. So this tells us LLMs are good at recognising the structure, but they still rely on optimisation to actually solve it. And also, this was a very small and simple problem for which TadGPT found the right answer. But this does not scale reliably to more complicated problems. Of course, you can also try this with the aviation problem that we have at our booth. Ask an LLM to solve it, and I tried it, and the result was pretty good. In the model it created, it had most of the main ideas, but it missed one constraint. So it was tremendous help at getting me going in the right direction, but the resulting model was not perfect yet. But maybe you will get something different. But interestingly, sometimes LLMs even fail on problems where the correct answer is obvious. So let me show you one. I'm sure some of you have seen this example before. I asked an LLM a very simple question. I want to clean my car. I live 200 meters from a car wash. Should I walk or drive? The answer was surprisingly complicated. It gave me pros and cons, environmental considerations, convenience arguments, but it completely missed the obvious point. If I want to clean my car, I need to bring the car. So sometimes LLMs get it right. Sometimes they completely miss the point. So let's compare this more systematically. Optimization requires a precise formulation. LLMs work with natural language. Optimization gives you guarantees, LLMs don't. Optimization is transparent, like we just saw. You can find out exactly why it shows one solution over another. LLMs are black boxes. Optimization is deterministic. If you solve the same thing twice, you get the same result. LLMs are probabilistic. Optimization needs structure. LLMs can handle messy data very well. And most importantly, with optimization, you can trust the result, while LLMs can hallucinate. So LLMs are great assistants, but not reliable optimizers. For example, they can help formulating optimization models, as we just saw in our consulting company example. But you still need to check that it's correct and that it didn't miss anything or misunderstand anything. Okay, before I end, one more thing. So, so far, we've seen how to build a model from scratch. But often, you don't want to start from scratch. And that's where our so-called optimods come in. So, what is an optimod? optimates, they solve common problems directly from data. So you just give it the input data and they give you a solution back. No modeling is required on your part. Or, which is probably more common, you use the code as a start for your problem and then modify it to your needs. So this is optimization, but packaged in a very user-friendly way. And of course, all of the LLMs out there also learn from the code that we provided there in the optimals. So let me summarize. Many real-world applications can be formulated as optimization problems. Optimization gives you optimal solutions with guarantees. and importantly it's not just about solving it helps you understand decisions and explore trade-offs and getting started is easy just do pip install GurobiPi and if you want to try it yourself just come to our booth and solve the airline puzzle thank you

Speaker 1 [23:52]

Thank you for the great talk, Silke. We have some time for the questions, so I'll just read some of them by the upvotes that they have. So the first question is, are multiple optimal solutions identified if they exist?

Speaker 2 [24:11]

Yeah, so the way Gurobi works, it might find other solutions on the way to the optimal solution and it will store them up to a limit that you can define. But by default, once it found the optimal solution, it's not going to go looking for more of them. But there are settings that you can enable that make it go on and find the second best and the third best and so on. So it doesn't do it by default, but if you need it, you can enable it.

Speaker 1 [24:48]

I think, like, they're not asking for a ranking of solutions, but they're asking if there are multiple solutions that are optimal. So is that what you also meant?

Speaker 2 [24:58]

Yeah, both. So if there are multiple optimal solutions, this setting will find them. But if there are not, it will find the second best with the second best objective value.

Speaker 1 [25:14]

Thank you. The second question is, how does the number of input variables, constraints, etc., affect the runtime of model Optimize? Like, does it scale linearly or worse?

Speaker 2 [25:31]

Yeah, so that's really difficult to say. So there are customers who routinely solve problems with millions of decision variables and constraints. But on the other hand, there are MIP problems with just five variables that no solver can solve. So it really depends on the structure of the problem. For the same structure, I mean, obviously, more variables and constraints will take longer. But there's no general rule for whether it's linear or quadratic. But in most cases, it's more than linear.

Speaker 1 [26:11]

There's also one question about like if you have because you have a package Gurobi by pandas Do you have also similar package for other data frame packages? So for example, this question is asking if you have implemented it in narwhals so that it can be package agnostic in certain way

Speaker 2 [26:31]

And no, we don't have that. Okay. It's an interesting idea But yeah, we don't have that yet. We just have we have pandas. We have other open source packages, but Not nothing like that

Speaker 1 [26:46]

Yeah, so nothing that could work with, for example, I'm not sure of all the libraries, but Polars is one of them.

Speaker 2 [26:52]

Yeah, now we have packages that help create constraints from deep learning models but nothing for other data frame type.

Speaker 1 [26:52]

Yeah. There is one interesting question about formulation of the problem. How critical is it to correctly formulate the problem? And how do I know if I made a mistake during the formulation?

Speaker 2 [27:20]

So, there are two ways to see this. So, first of all, if you make a mistake, like if you completely model something else, you will usually see it because the result does not work in practice. Like if you forget a constraint, you will get a result, and when you want to implement it, you realise, oh, wait, this is actually too expensive or whatever, and then you might see that, oh, yeah, I forgot a constraint. And then there's also the aspect that there may be different ways, correct ways, to model the same thing, but there might be a difference in performance. Some ways would be much better for solver performance than others.

Speaker 1 [28:11]

the last question is a little bit vague so I'm not sure if you can decipher it how to add capabilities I'm not sure what did they mean by this maybe you can decipher it and understand what does the question mean

Speaker 2 [28:26]

Can the person who asked the question maybe elaborate? So what is this about? Yeah, so I only had this in my model implicitly in that not all teams could work on all projects. Like the project values data frame only had certain team and project combinations. But it might also be that, for example, example, a certain team would be more efficient on a project than another team, that would be a bit more difficult to implement, but you could maybe model it by having the capacities of the teams differ based on the projects that they work on. So there are ways to model this, but it's going to be a bit more difficult than what I showed in the simple example.

Speaker 1 [29:52]

And just the last question. Is it possible to optimize an overbooked system and detect which project should be rejected?

Speaker 2 [30:03]

So, the way I understand this, sometimes you ask Gurobi for a solution and it tells you the problem is infeasible, so there is no solution. In that case, there are two main ways to investigate. The first one is computing what we call an IIS, an irreducible infeasible subsystem. So this gives you a smaller subset of the variables and constraints that is already infeasible. And if this is small, you might look at it and realise, oh yeah, that is where I made the mistake or that is what makes it infeasible. But sometimes those IISs can also be really big and difficult to interpret. And the other thing is what we call a feasibility relaxation. So you can ask Gurobi for the minimal change required in the model to make it feasible. Like you can say, for these variables it would be possible to change the bounds, like because this is a budget or whatever, and for others that might be laws of physics that you cannot easily relax, so you say these need to stay fixed, and then within the ones that it is allowed to fix, to relax, it can find the cheapest way to make the model feasible.

Speaker 1 [31:25]

Thank you. Please give a huge round of applause for Silke.

Speaker 2 [31:29]

Thank you very much.

Speaker 1 [31:36]

Thank you for joining the session. And please also don't forget to rate the talk on PyCon's website. Thank you.