Optimizing in the Python Ecosystem – Powered by Gurobi

Speaker 1 [00:07]

Thank you very much for this nice welcome here, and thank you all for coming. So, as announced, I will be talking about optimizing, so this is mathematical optimizing, mathematical optimization in the Python ecosystem, powered by Gurobi. So, what is Gurobi? First of all, Gurobi is the name of our company and of our product. The company was founded by Zonghao Gu, Ed Rothberg, and Bob Bixby. And this is also where the name comes from, from their last names, Gu Ro Bi. Very creative. Gu Ro Bi, the product, is a mathematical optimization solver. It can be deployed on all types of hardware. You can run it on your own laptop, on your data center, on the cloud, or you can use our cloud product. Gurobi is free for academic users for research and teaching. And what I'm really proud of, also for non-profit organizations. So this is a project that we started last year. We are now second year now. And we have a growing list of non-profit partners that are using Gurobi and optimization to do good. And Gurobi is a generic math optimization solver. So there is no application or domain-specific API. We don't have a GUI. Our core libraries are implemented in C. And the customers, integrated in their business applications, or they have partners do so. And depending on how you count, we have about 3,000 global customers across more than 40 industries. And here you can see a short list of some of our more important customers. And on our website, you can also find, by now, more than 60 customer case studies to see how they are using our product. And of course, Gurobi has a heart for Python. That is why we're here. Gurobi's Python API is called GurobiPy and has been part of the product from the start. This is a powerful, popular Python package. And we're proud that it is among the top 1% most downloaded packages on PyPI. And of course, we continue to work on it. And we continue to invest in Python. So how do you use Gurobi? So it's very easy to use it with Python. You just do pip install gurobipy. And if you do this, you will also get a free size limited license. So you can just install it and start playing with it. If you're interested, we have other APIs as well for other programming languages, but Python is by far our most popular API. And we also have some exciting open source projects that you can look into on GitHub. So there's GurobiPy Pandas, and as you can guess, this is the integration of GurobiPy with Pandas, and I will walk you through an example of how this can be used later in this presentation. Then we have the GurobiOptimods. these are examples for data-driven optimization interfaces. I will also give a short example of this later. And then we have Gurobi machine learning which helps you integrate trained regressors into an optimization model as constraints. Okay and of course we also have links to standard mathematical modeling languages if you're familiar with them, and there are some third-party frameworks, not officially supported by us, but you can still use Gurobi together with them. So now, I want to give you an idea of a few use cases of some of our customers. First, the NFL, the National Football League in the US, uses Gurobi to do their game scheduling, And there are 32 teams and 272 matches each season. So this would give you millions and millions of potential game assignments. The schedule is an enormous combinatorial puzzle. It used to be solved on physical boards with planners manually moving the pictures around. But now this has been translated to mixed integer optimization problem. And there are many very complicated constraints. So first there are the broadcasting time slots, then there are travel and time zone limitations, there are rest days of the players, and of course you want to maximize the profit. So the best games should always be slotted into the prime time. And in fact, this optimization problem is so complicated that a decomposition and parallelization approach is needed to solve this in adequate time. one is our customer Air France. They use Gruby for their tail assignment. So they have flight schedules that tell you when the flights happen and what type of aircraft is used. But then you need to assign specific machines based on the bookings of those flights and some other operational constraints. And here we balance multiple objectives at once. So we try to maximize the fleet utilization. So we rather keep the planes in the air rather than parked on the ground. Then we want to maximize on-time performance. So we want to minimize delays. We want to minimize the fuel consumption. And of course, there are some other preferential assignments. And of course, if you imagine that a customer like Air France can save only 1% on their fuel or on their staff costs, this is already massive in terms of cost saved and also in terms of the environmental impact. Okay, so what is a mathematical optimization problem? Mathematical optimization problem has several key components. The first one are the decision variables, and here I have a few examples of those. For example, when you have a shipping problem, you could ask how many trucks should I send from one logistics hub to some other? Or you could ask how much, if you're doing portfolio optimization, you could ask how much of my portfolio should I invest into NVIDIA? Or if you do scheduling, like for this conference, you could ask should I assign this talk to to room Helium 3 in the Thursday 4.15 time slot. And if you think about it, the first one here, if you are asking how many trucks, then this will be what we call an integer variable, so because you can only send integral amounts of trucks. The second one here, the proportion of capital invested into an asset, this can be a fractional value. And the last one down here, this is a binary variable, so this is either zero if we do not schedule this session in this room at this time, or it is one if we do. The next key component is the objective function. So this is what measures the metric that we're interested in. And in shipping, we could be interested in minimizing the total transportation cost. In portfolio optimization, we could be interested in minimizing the total risk of a portfolio. And in scheduling, we could try to maximize the sum of time slot preferences across the entire conference schedule. And finally, we have constraints involving these decision variables. So for shipping, an important constraint is that the predicted demand must be met by the incoming shipments. In portfolio optimization, you could have something like, I do not want more than 20% in any one specific asset. And for the conference scheduling, of course, each room can host at most one session at a time. All right, and what types of problems can Gurobi solve? So the easiest one is a linear optimization problem. So in this case, the objective function is a linear function of our decision variables x. The same as the constraints, they are also linear functions of the decision variables. But we can also have it a bit more complicated. We can have mixed integer linear optimization problems, so basically this is the same as up here, but now we also have constraints that say that some of the decision variables should only take integral values, but we can actually also use quadratic functions. We can use other non-linear, non-convex functions, and we are adding more and more different functions that we can handle okay let's work through one example of an optimization problem so imagine that we are running a fantasy consulting company and in this company we have different teams a set of teams capital J and we have a set of projects capital I that we can work on and now the question is which team should work on which project. We have some input data for this so of course each project I has a different profit associated with it if we complete this project. Then also each project has a different resource requirement so this is what we will call WI and then of course the different teams may have different capacities. So let's model this as an optimization problem. We need decision variables and in this case we only need one type and we will call this xij. This is going to be a binary decision variable and this is going to to be one if project I is assigned to team J now we need constraints the first constraints is we need to honor the capacities of the teams so we cannot oversubscribe the teams this is the first constraint over here so for each team J, the sum of the resources times the decision variable should be less or equal than the capacity of this team. And the second constraint is that we do not want multiple teams completing the same project. So we want at most one team for each project. And this is the second constraint down here. So for each project I we want at most one team working on this so we want at most one of the X I J to be one and we can get this if we add the constraint that the sum over these X I J should be less or equal than one because up here we made sure that X is either zero or one and then our objective function is of course to maximize the profit. So we sum up the PI for each project that is completed and we get this if we just multiply the PI by the Xij. All right, so let's implement this using Gurobi PyPandas. So we have some example input. We have three data frame so here's a data frame that contains the resource requirements for each project we print the the first three lines of this then we have a data frame teams that contains the capacities of the different teams and we have a third data frame project values that contains for each combination of project and team that is viable, the profit that we would get from this project. And with these inputs, we are now going to build the model using Gurobi PyPandas. So first, we need to create the decision variables. And with Gurobi PyPandas, we attach them to the data frame. So we need some imports, and then we create a Gurobi model object. And since we want to maximize the profit, we set the model sense to maximize. And this is now where the interesting stuff happens. So we add the variables to the models. We want them to be binary variables, so each x should be either 0 or 1. And we want to give it the name x. And while adding the variables, we also set their objective coefficients to profit. So this then refers to the profit column of this data frame. And that's it. We have created our variables. And we can again take a look at our data frame. And now we see that we have the team and the profit combinations here, and we have a new column X that consists of Gurobi decision variables. So let's add the constraints. So we had two different constraints. The first one was for the resource constraint for the capacities of the teams. Okay, let's walk through this. So this is the left-hand side of the constraints, and here we use the resource column of the data frame, of the project's data frame, times the decision variable x that we added, we group this by the teams, so this is all very nice Pandas functionality that we use here. And then we just sum this up. And this term should be less or equal than the capacity, which we get from the capacity column of the data frame. And that's it. So we can also take a brief look. So here we see we now get linear combinations of our decision variables with the coefficients from the data frame. We have a second constraint, type of constraint that we need to add. works in a similar way, so we need to make sure that only one team works on each project. So we get the X column of our assignments data frame, we group a project, we sum this up, and then this should be less or equal than one. And that's it. Again, you can see what these linear terms look like. And now we're done building the model, and we ask Gurobi to optimize it. So we just call Gurobi optimize, and in this case, it will work very quickly and solve the model. And it will store the values for the decision variables in the X attribute, this capital X attribute of these variables, and we can just access this using this accessor here, And yeah, the rest is making it nice, so we make it into a data frame. And then we do some massaging to get some nice output. So here's one interesting thing that happens. So our variables are binary, so they should be zero or one. But we still use linear algebra operations. So this means there will be some rounding errors. So the values will not be exactly zero or one. There may be some very tiny deviations. And this is why we do not check that x should be equal to 1, but we allow some tolerance. So we just get all the variables that are greater or equal than 1, sorry, than 0.9. And then we do some Pandas magic. We group them by team. We put them into lists. And then we get the optimal solution down here. So we see that team T0 should be working on projects P4 and P5 and so on. And you can look this up on GitHub down here, github.com slash Gurobi slash GurobiPipeHandles. Next I want to talk a bit about the GurobiOptiMods. So an optiMOD, this is a tool to solve a specific problem. It has a data-driven API for a common optimization problem, and it takes data in a natural form, whatever this may be for the specific problem, and it also returns the result in a natural form. It solves mathematical optimization problems using Gurobi, but you cannot actually, you don't need to be an expert in Gurobi or optimization. You just put in your data and you get out a result. And very importantly, they are also meant to be a reference implementation for common optimization problems. So a really good way to learn how to do this yourself is just to do copy and paste. So you can look into this. If something is similar to what you're trying to solve, you just copy it and adapt it. And of course, having all of this code open source and available for everyone will also your favorite AI tools to get better at modeling this. So you could ask your favorite AI tool for help with writing this modeling code. I will show you one example of an optiMOD. So this is about portfolio optimization. So imagine you're a fund manager and you want to build a portfolio of different assets. Those assets could be stocks or cryptos, maybe real estate or bonds if you want. And now you want to build this portfolio so that you minimize the risk and maximize the expected return. And we have an opt-in mode for this. So you import the specific objects, then we include some example data. But if you really want to use this, of course, you have your own data. And then you just pass the data. In this case, these are the return and risk estimators, the mu. And this is usually called sigma, the covariance matrix. And then you compute the portfolio. So gamma is a risk aversion parameter that balances how much you want to focus on minimizing risk or maximizing return. And in this case, I said I want to allow short selling, but only up to a certain point. And I don't want very small positions. So if I invest either long or short, I want to do at least 5%. If you're interested in portfolio optimization, you understand these terms probably. There are many more things that you could ask of such a portfolio. You could also ask that I only want a maximum of five positions or I want at least ten positions or I want transaction costs, linear or fixed. You can also add market impact costs and turnover constraint, whatever. And then you just get the result back. And in this case, with our example data, we have these interesting assets here, and it tells us that this is the optimized portfolio. So if you were a portfolio manager, you could optimize your portfolio without knowing anything about Gurobi. Or you could use this reference implementation to adapt it to what you actually need. And the last example I want to talk about is the Gurobi machine learning package. So you can use trained regressors as constraints. And here you have an input variable vector x and an output variable vector y and a trained regressor f. And then you can add this to the model as a constraint function y equals f of x. And we support different APIs like SKLearn, Keras, PyTorch, and so on. And just to give you a very quick example what one could do with this, so this is called adversarial machine learning. So assume you have a trained network and you want to find out how robust is this with respect to noise. So here is one example. We have a network that takes these graphical inputs and then classifies what it sees as Number as a digit in this case this one here is classified as four and now With this constraint we can find out. What is the minimum change that you need to do this to make It be classified as something else and the result is actually if you just add some random noise here around the edges Then this is suddenly classified as a nine And some Summary and takeaways so groby is a mathematical optimization solver Mathematical optimization is a very full very powerful tool, and it is Completely industry agnostic, so it can be used Whatever kind of problems you have and you should really try pip install groby pi and just play around with it And that's it. Thank you very much

Speaker 2 [23:41]

Thank you, Silke, for an amazing presentation. I think we still have some minutes to look at some questions that may have popped up in Slido. So let's wait. Okay, we have multiple questions, but we have like five minutes, so we're going to attend to any of the questions that are going to fit in our time frame. So someone is asking, anonymous again, do you know about performance benchmarks of Gurobi compared to other solvers like GLPK?

Speaker 1 [24:21]

Yes, there are benchmarks, there is one, I think the most famous one is by Hans Mittelmann. Gurobi has very recently opted out of this, but I think you can still access the historical data. Okay, I hope you could not hear this, because my son is talking to me on my Apple watch. Yeah, so there are performance benchmarks. Gurobi is, like, Hans tests Gurobi on a set of different models and then puts the resulting running times on the website. And for most problems, Gurobi is a lot faster than open source solvers. There are other commercial solvers that get close to Gurobi, but compared to open source Gurobi and the other commercial solvers are usually a lot faster.

Speaker 2 [25:22]

The other question is, do you know, I mean, how fast is Kurobi for optimizing general objective functions, like not even continuous? I don't know if the question is clear. Yeah.

Speaker 1 [25:41]

I mean it really depends. So we get this question very often like how long does it take to optimize a model with so many variables and so many constraints but it it really depends. There's really no way to predict this without trying because there are some very very small models that take hours or longer to solve and there are some very huge models like thousands or millions of variables and constraints but somehow they have a nice structure and it is easy to find good solutions so they are solved very quickly so there there's really no way to predict this

Speaker 2 [26:22]

Okay, I think we can take two more. Are there differences in runtime performance when using Gurobi directly versus using it as a solver when defining the optimization problem with Payamo?

Speaker 1 [26:35]

Again, the answer is, it depends. So PyOMO is a modeling framework that is solver agnostic, so you can use it with different optimization solvers. And usually the modeling should be only a very small part of the total running time, so the solving time should be a lot more. And if this is true and PyOMO actually models the same model as GurobiPy, then it should not make a big difference. But sometimes these frameworks, they model things in a different way that might not be ideal, and in that case, it may take longer. So if the model, the resulting model is the same, there should not be a big difference. If the resulting model is different, then there may be a difference in running time, maybe more performant to do it directly in Gurobi Pi. And of course, there are some very specific features that you can only use if you use Gurobi directly via our own APIs.

Speaker 2 [27:47]

Are constraints computed prior to the objective max mean step? If so, how can you model soft constraints?

Speaker 1 [27:56]

So, soft constraints are constraints that you would like to hold, but it would be okay to violate them under some cost. And I would then basically add the cost of violating the constraint to the objective function with a coefficient depending on the cost you want for the violation. So, yeah, you make the violation a variable and put this in the objective function with with a sufficiently high coefficient.

Speaker 2 [28:35]

I think that's it we can take any more questions because time doesn't allow us to do so so we only have five minutes to migrate to any room or if you want to stay here for the next session you can stick around and thank you again