Prescriptive Analytics in the Python Ecosystem with Gurobi

Speaker 1 [00:05]

Thank you, Florian, for the very kind introduction, and thanks to the organizers for having me. I'm thrilled to talk in front of such a keen audience, and I hope you get something out of it today. All right, so I'm going to spend a couple of minutes on explaining what Gurobi is. I'm going to put it into context of prescriptive analytics. Then I'll dive a little bit more technical, going towards what is actually mathematical optimization. I'll give you a good example, a very simple one. semi-contrieved, I would say, on project team assignment. I'll walk you through a couple of open source offerings we're having at Gurobi, data-driven optimization examples, and finally conclude with an adversarial machine learning example where optimization plays a surprisingly interesting role. All right, so what is Gurobi? Gurobi is a commercial solver engine for mathematical optimization problems. We are worldwide, all remote, from the start company, founded in 2008. Our software is pretty deployment-friendly, from laptop to data center or just via our cloud service. It's free for academia and free for non-profit. And we position ourselves in the realm of prescriptive analytics. So unlike predictive analytics, which tries to get some insight into how made future data look like from past data that I know, we take the prediction and based on that, take optimal decisions to make business, to solve business problems in the future. So Gurobi is a prescriptive analytics tool. and yeah as you could have guessed we're not like a small smart startup we have 3000 plus global customers across various industries if you are not so much from the technical side but more from the business side check out all the case studies we have on our website to give you an idea where Groovy may fit into your business for the more technically oriented so we are not a consulting company where we don't have an application-specific framework that allows you to, say, solve supply chain problems or logistics problems or whatever. No, we throw you the engine for the car. We throw it over the fence, and then you build the car around it, or you have consulting partners to help you succeed with that. That said, everything's implemented in C, so that's how I spend my day. I sit in my basement hacking on C algorithms and the code, and the result is this library. Yep, that's it. How do you use Gurobi in practice? Well, you do what you do. You pip install GurobiPy. That's what I would say more than 80% of our customers are doing. But for sure, we have APIs for most of the popular languages. Well, notably missing is Rust. I know there's a Rust intersection of Python Rust fanbase here, even in this room, but we're not there yet. Too few commercial customers in the Rust space, I guess. We have a couple of more interesting packages to play with. We have GroovyPyPandas, which makes it terribly easy to build optimization models directly from Pandas data. We have GroovyMachineLearning that allows you to integrate trained regressors as constraints into optimization models. We're going to talk about that a little bit later. And yeah, so if you are from the traditional side, so of course, Groovy is also accessible via all the existing infrastructure tools in the optimization space, Ames, Ample, GAMS, MPL, and CVXI, Paiomo, Pulp, Jump, Google, our tools, you name it. Typically, all these tools will offer you to use Gurobi in the back end. Okay, so what is prescriptive analytics anyway? Let's approach it from a couple of use cases. So the NFL, of course, a big thing in the U.S., and designing a schedule for the season plan of the NFL is an enormously challenging problem. So, in the end, you know all the data in advance, but you know what are the teams, who will meet which team when, okay? But you have to arrange the exact timings, the locations, and there are enormously complicated constraints because it's so highly commercialized, NFL. So you have to take into account what do the broadcasting agencies, what are the requirements for them to allow a game. You have free agents, which changes mid-season, the composition of the teams and then you cannot send the same team three consecutive days in away games somewhere else. It doesn't work. So in the end, NFL uses Kurobe to create a season plan. So that's their business problem. They solve it that way. France is just an important customer for us, a very good customer. I'm sure many of you travel a lot. So I think you notice that if you hop on a plane, the plane will just not go back and forth, back and forth between the same two locations. It will hop actually on a circular rotation until it hits maintenance time, and then goes to maintenance. So that's in the undisturbed case, right? There can always be like exceptions, and then you can reschedule. But typically, you have a rotation plan. And well, how do you, so you have your flight plan from, this is the business input, and you have to solve the problem, which plane serves which lag at which point in time? and you need to do this by respecting fuel constraints, you need to utilize your fleet, you don't want to have airplanes sitting on the ground because on the ground airplanes just cost money and doesn't do anything, you want to minimize fuel consumption for obvious reasons and operational costs like crew scheduling, you don't want to have empty flights, you don't want to bring crew just to fly the plane empty bags, that doesn't make sense, so it's a highly complicated scheduling problem and Air France uses Guarubi to do this. Third and last case study, if you're on the farming side, you have to somehow make multiple passes over your fields to either seed crops or to maintain or to whatever you need to do. So there's always a routing problem. How do I traverse this field? And do you have boundary restriction? How much from the edge are you allowed to drive? how many turns, should you minimize the turns, should you minimize the distance, should you minimize the fuel. So Enverge is a company that has an app essentially for farmers in the end to help them designing the optimal routings on their fields. So that's another happy customer with Gurobi. Alright, so what makes them all happy? It's mathematical optimization that makes them happy in the end. If you haven't heard of it, let me let me start with a complete non-technical verbiage on that. So there are typically three major components in optimization problems. Number one is decision variables. So that is the thing you want to get out of the optimization problem. You want to have a decision, what should I do? So here are three examples. Should I stock cat litter boxes in fulfillment center Ludwigsvelde, south of Berlin here? from Hubschreuditz, which is an airport near Leipzig. You could also stock it from Amsterdam, you can stock it from Warsaw, so plenty of choices. So that's a decision that you would like the optimization problem to give to you. Yeah, you should do that because that's best. Another example, if I'm investing into stocks, how much should I put into NVIDIA? Well, if we had been 15 years back, probably 100% we are now sure, but of course we cannot tie back time. but that's a decision problem you want to take. What should I invest? Or another classical scheduling problem. Should I assign Robert's talk to room B09 at Wednesday, 10.30? You have to plan a conference. You have to plan who speaks where when. So that's a decision that you want the mathematical optimization problem to take for you. Second important component. You have decision variables, granted. Now it's about what do you want to optimize? so and this is a key performance indicator you typically put in so in the first example with the cat litter boxes what you want is you want to minimize the total transportation cost that was the shipping example or in the case of portfolio optimization you want to minimize the expected so the expected value of the risk for your portfolio of investments or for the third example you could say well here pycon we are not allowed a speaker to to to voice preferences but other conferences do, so it's a bit contrived. So what is the conference schedule that maximizes the speaker happiness in terms of timings? So that would be the objective to me. All these are key performance indicators. Finally, the third thing, and this makes it very, very different from just, oh, but I use stochastic gradient descent to solve my problem. So here's the thing that makes mathematical optimization much, much different. You can enforce constraints on the decisions. So you can say, with the replenishment, with the fulfillment of demand of cat litter boxes in Ludwigsveld, I must meet the predicted demand. A solution that does not meet the demand is not feasible and hence cannot be considered among the choice. Or you could say, yeah, if I'm into portfolio optimization, and you know, whenever you open position you pay a transaction cost and that's typically not desirable to have like 1000 tiny positions open because you pay 1000 times the transaction cost for that you say okay give me the best possible solution under the restriction that i invest only in 20 different assets and among these minimize the risk or for scheduling well there's a very very obvious constraint that you definitely want to put each room can host only at most one session at a time i mean would be nice to have, like, a peer standing next to me, but it's kind of async. That doesn't work. Okay. Good. Now, for the more tech-oriented math notation people in the room, so this is the essence of what I just said. Anything, any business problem that you can translate into, hey, I have decision variables, I have linear constraints, I have inequalities. So These are optimization problems in standard form. Of course, you can have inequality constraints, AX less or equal than B, or whatever. Anything you can phrase into this framework is what our solver then eats. I want to point out one specific thing here, which is the integrality restriction here, right? This is something that... This is a differentiating factor for mixed integer optimization. So you can enforce on the decision variables that variables may only take binary or generally integer variables, right? You cannot send three and a half trucks from Schreuditz to Ludwigsfelder. This doesn't work. Even it would be optimal. You have to settle the question, should it be three or four? And the solver takes the decision for you and gives you a guaranteed globally optimal solution for that. It's not heuristic. It's guaranteed. All right, and then you can put twists and turns on top of it. Mixed integer, quadratically constrained optimization problems, mixed integer, non-linear, non-convex problems, and so forth, you can go through with the whole taxonomy of optimization problems, and typically, Grobby will be able to solve them. Okay. I want to do one full example from model to code that you have seen at least one thing concrete. I cannot put the most complex thing here on the slides in a couple of the few minutes I have. I still hope you get the essence out of it. So the setting we're having here we're running a fantasy consulting company, and we have a fixed set of teams, so this is indexed by the set J, and we have a set of projects I that wait to be worked on. And now we have to decide which team should be assigned to which project. And so let's check out what is the data. So first of all, for every project on the board, we do have an expected profit. So this is the money we get from completing the project. Then we also have a resource requirement for each project, which is like how many person weeks does this project take? So like senior consultants say, yeah, I would say it's two and a half person weeks. And that's the number you get as input. Then you have a capacity of the team. You cannot put all the work into one team because the team has maybe only capacity for ten person weeks of projects. Alright, so this is the data you get in. Then you have decision variables and that's pretty obvious. So these are binary variables and that indicates should project I be assigned to team J? If it's zero, it's no. If it's one, yes. That assignment is optimal. What is the objective function? Well, we want to maximize the profit from all completed projects. It doesn't mean we need to do all. Well, if we would be able to do all, then there's no optimization we just do everything fine but we want to select right so what what is the optimal assignment of projects so that we maximize the fantasy consulting company's profit and there are constraints so we cannot oversubscribe to teams we cannot put everything on the most efficient or the most or one team each team has a capacity to to work on and finally at most one team works on each project. So even though we may have a project that is extremely profitable, we cannot complete it ten times by ten different teams. Only one team can work on it. And if you, what I just put out in verbs, yeah, so this is the mathematical formulation we get out of it. Like you maximize the sum over the profits pending assignments, subject to the capacity for all teams is met, and each project is assigned at least at most once, and of course, half an assignment doesn't make sense, so this is a binary decision variable. So how does it look? The input data, we have two theories on data frame, one for the resource of each project, one for the capacity for each team, and finally for each admissible matching between project and team, so this is a Pandas multi-index here, we have a profit we can put into it. All right, so don't be disappointed to get lost in the data. I'll walk you through as good as I can. So how does it look in the code? First thing, you import our libraries. So GrowPi is our standard. It's our wrapper on the C library. And then the GrowPi Pandas is our convenience tool. This also registers automatically as the accessor API of Pandas. So you'll see some magic coming out of it in a bit. You create an optimization model. So this is the container data structure, more or less, to hold constraints, variables, and so forth, and to query the solution in the end. You could either maximize or minimize. Here you want to maximize. It's mathematically the same thing, right? Maximizing the minus of something is the same as minimizing it. So it's not... But here, in that case, we want to maximize. So here goes the thing that is important. So the project values. This is the multi-index data frame with the profits in it. We go through the accessor, GPBD, and say add variables and this will add the decision variables that I talked about earlier stuff it into the model they have the type binary and the objective function coefficients, so this is the profits we get of it it should read them out directly from the data frame from the profit column and then there's also some descriptive name and you see what happens here this is the multi-index, this is the data we had in the data frame and now we got another data frame that has attached another column with the decision variables. And so x p2 t0 is the decision variable for should project 2 be tackled by team 0? So we ask in the end the ultimate dissolver, should it be 0 or should it be 1? That's the ultimate question we will answer in the end. All right. And you build up the model by similar constructs further. So now the resource constraint. Here you broadcast the project resources along the missing dimension of the multi-index to the assignment variables. You group by team, sum it up, and guess what? You want to bound the sum by the total team capacity. So that's what we want. Teams cannot be oversubscribed. That's what's happening here in the code. Finally, last constraint. Now we do the aggregate sum paradigm the other way around. This time we take the assignment variable, group by project, and sum it up, and say, yeah, that must be at most one. And that's the whole model in the end. What we now do is we call model.optimize. This will solve in a split second for a toy problem like this. That's like 10 teams and 15 projects. I don't know, this is ridiculous, but it's a nice toy example. And then we need to query the solution. So we go to the assignments, which were the decision variables. Get that column out of it. This is now a series. Go through the pandas accessor. query the Gurobi attribute x which is shorthand for the optimal solution values put it in the frame, reset index, select da da da da da and since these variables were binary we can just query for greater or equal 0.9, that's just some number so this is still a numeric algorithm so there's an integrality tolerance of like 10 to the minus 5th or something so querying exactly 1.0 may just not work well with that tiny tolerance, so better saved than sorry does greater than 0.9, and what comes out of that is definitely 0.1 for all what makes sense here. Alright, we group by an aggregate, and finally what we got is the schedule, so this is a series with, a data frame with the schedule we have, so each team has now a list of projects to work on, and the solver is guaranteed that this is the optimal assignment for these project team combinations. All right, that was my contrived little example. Now I walk you through a little more high level on other open source tools we have. So the first is the Gurobi Optimods. An Optimod is a tool to solve a specific practical problem. It has a data-driven API for common optimization problem. It takes data in natural form, returns it in natural form and solves in the back end. You won't notice it uses to do this so maybe if you have like a stem or mint background from university you may have seen some of these projects some of these problems here like maximum bipolar matching or maximum weighted set is typical what you what you learn in computer science and when it comes to discrete problems somehow or optimal power flow i know that many people in the power industry actually here so that's that's a big big thing for us and for for society actually in general how to do that Or Kubo, due to the quantum hype, people are talking about Kubo, so we have something for that. So these are data-driven APIs. So you should think about these optimos as examples on how to leverage optimization technology into your business. So you take it in the back end, and the front end you communicate with data in, solution out. And that is how it's done. So one example, quick. So many of you may know from scikit-learn like the ordinary least squares regressor. So this is just a two norm of the regression error that you want to minimize, right? This linear algebra more or less. So here we have an alternative which does not look at the two norm, but at the one norm. I'll show in a bit why this actually makes a difference. And so what comes from Gorobi optimus is you import the regression module. you instantiate it, you train it, and then you get the predictor, you get the regression weights back by predicting your test data. This is all the standard workflow you have to do for regression problems with scikit-learn anyway, so that environment takes input in natural form, so you do it exactly like you would do with scikit-learn, but in the back end it doesn't use scikit-learn, it uses Gurobi to solve the problem. So why is this one norm thing actually interesting. So I noticed that while playing around a little bit with that. The thing is that if you take the one norm instead of the two norm, that's much more resistant to outliers. Like somebody enters an Excel sheet with the BMI of certain test people and then they just flip two numbers. Of course, it doesn't make sense for the BMI in most of the cases. That's a typical outlier that happens on the sparse cases into the data. So here I've done a nice comparison. So in blue, we have original data and in orange, I've added some few random gross outliers into the training's data set. And by using absolute value as the regression paradigm, you avoid that your regression coefficients change a lot because in a 2-norm, right, there's a square in it. So if you have anything with a large deviation, this will hit extra hard because you square the error, essentially. So this just shows for if you expect your data to have random few outliers. Better not use ordinary least squares. Think about something using more robustified any other way like the other techniques, but least absolute value deviation is for me the easiest one. Anyway, final topic, using trained regressors as constraints. So as part of the key components for optimization problems, I featured that, yeah, you have to put constraints like no room can be used twice at the same time. So how about if we don't put linear constraints or linear inequalities, as I've shown in my example, but instead we input a trained regressor. So what does it mean? So we take any package to train a regression model, and then instead of just predicting values, we say, hey, take this regressor and regard it as a constrained optimization model. So this means your variables on the input side, you have variables on the output side, you solve some mathematical optimization problem, but you add also the constraint, by the way, the input variables, the values of the input variables must be connected to the output variables, and you use that exactly like any other linear constraint. So this is cutting-edge research. This is not in our commercial project. This is part of our open-source project. So take a peek at that. Here's one fun application. So you all know this number database that everyone has used for the last 30 years for paper publications. So here, you can ask yourself, if I have a regressor and I find a correctly classified picture, here's the four on the left-hand side, you can ask the optimization problem then, what is the minimum perturbance I have to add to the picture so that the regressor fails? And so on the right-hand side, you see I changed a few pixels, actually not I changed, but Gorobi figured out That is the minimum change I can apply to an image so that this picture is no longer classified as a 4. And, of course, this has a name in the literature. This is adversarial machine learning, and optimization is a perfect tool to explore exactly these robustness boundaries. All right, so I hope I could convince you that mathematical optimization is a powerful industry agnostic tool, and Groby is in the game for helping you to solve these. Try it out, pip install group, Appendice, and thank you all.

Speaker 2 [24:37]

Thank you so much, Dr. Lutze, for this interesting talk. We have so many questions. The top voted one is, what is the cost to switch from IPOP to Gurobi?

Speaker 1 [24:47]

like the cost, the philosophical cost or money cost. Yeah, so there are many metrics we have to regard. So IPOpt is, so maybe to put it in the right scope. So IPOpt is a very robust solver for local nonlinear optimization. So IPOpt guarantees within the boundaries of what you can do with numerics to find a local optimum of an arbitrary nonlinearly constrained optimization problem. Gurobi, in contrast, guarantees that you get back a globally optimal solution. So it's a different discipline, and it's hard to compare. So in terms of money, it's zero versus something, because is open source, and Gurobi is not. So that answers the question. But I want to just point out, these are two different things. You cannot really compare them.

Speaker 2 [25:38]

Thank you. The next question is, when should I use Gurobi and when SciPy optimize fmin?

Speaker 1 [25:43]

You should use Cypher-optimized admin if that's most easy for you to use to get started in your project. And if you ever feel like, wait a minute, if I scale up my problem, this doesn't seem to work anymore, it runs forever, solution wrong, then you should give Gurobi a try whether our year-long work of the R&D team pays off by providing a faster and more robust solver than the open-source landscape currently provides.

Speaker 2 [26:11]

And then in the same line of thought, what are the indicators that I should switch from an OSS solver to a commercial one like a robot?

Speaker 1 [26:17]

Yeah, same thing you're reaching the boundaries of what open source service can do for you And you have to benefit from the years of engineering work. We've put into our product and just give it a try It's free evaluation is available free for academia free from non-profit anyway, so you'll find out

Speaker 2 [26:34]

Okay. And then another question. I heard that commercial solvers are performing much better time-wise than non-commercial ones. Is that true? And if so, why?

Speaker 1 [26:43]

Okay, I think it's almost the same question again. So all the technology back end that we use, so branch and bound, linear optimization, I mean, that's all known. You can buy a textbook and read what we do. What makes the difference is if you have an R&D team of extremely highly specialized mathematicians and computer scientists that make their living on figuring out what is the best way to implement an algorithm, what are the tricks I need to put into it to make it work in practical problems, what you get from customer interactions. You learn from customers, oh, that's how we do it. We should adapt our algorithm to cover that in a better way. All these opportunities that open source servers typically do not have. Hence, we are typically faster and more robust than open source.

Speaker 2 [27:30]

There's another question to you. I guess as an optimization expert, Microsoft has the term of quantum computing inspired optimization. Could this be advanced over classic optimizers?

Speaker 1 [27:40]

Yeah, this is an interesting marketing thing. I totally agree. So here's the thing. So quantum has some enormous momentum both in the press and in people's minds, and I appreciate that. The thing is people are somehow, they start with, oh, there's quantum, maybe I can solve my problem. Then they get into reading, and they found, oh, wait a minute, but if I formulate my problem not as something for quantum, but just use mathematical optimization which exists already for 30 years, maybe I should try that now. So maybe not wait for the quantum revolution, just solve your problem today with the tools that are already there, even if they're not called quantum.

Speaker 2 [28:20]

Evolution is a wonderful segue to the next and last question. How is Gurobi better than SciPy optimized differential evolution?

Speaker 1 [28:29]

Yeah, so I have to admit, so that must refer to some particular method in SciPy Optimize, right? That one I don't know. I think we are a global NIP solver. That one doesn't sound like a global NIP solver. I think that's the best I can answer for the moment. Sorry.

Speaker 2 [28:46]

Thank you so much.