The Art of the Optimal: A Pythonic Approach to Complex Decision-Making

Speaker 1 [02:26]

Good afternoon, everyone. Welcome to the session, The Art of the Optimal, A Pythonic Approach to Complex Decision-Making, with Justine Broyen and Mohamed Soyturk. Hope I said it well. So, hand it up to you.

Speaker 2 [02:53]

Yeah, thanks for this introduction, and I hope everyone can hear me. I'm going to kick off my talk with a little mental game. So it's a mental exercise for all of you, and everyone is introduced to participate. So what do we see on this picture? This picture shows arriving cars in an assembly line on a conveyor belt. And in the picture, like in the bottom of the picture, there is a guy that has to decide how these cars are going to be painted. Because these cars, they will either be blue, black, white, green, you name it, the color. And based on the color that those cars will be in the final product, they need to get a base coat. And the base coat, that's either white or black. and the guy in the bottom is deciding which to paint in which color so which one's going to be white and which one is going to be black now the game here is you are that person in charge of deciding what car is going to get what color you're going to make it a little bit more complex so let's assume there is different car types that arrive on this conveyor belt we just saw and I'm depicting the different car types here with different letters, A to F and these car types, they arrive in a very specific order and as they are arriving on the conveyor belt you cannot change the order they are arriving so the thing here is each car needs to be painted it with the space code black or white. And each vehicle type, A to F, arrives exactly twice in this sequence. So there's one A and a second A, one B and a second B. Now, one of each type must be white, and the other one has to be black. And as I said, you cannot adjust the order. And the key here is that changing the colour from white to black and from black to white, that consumes time and resources. So, the idea is try to find a colouring sequence that colours each vehicle type, one black, one white, with the minimum amount of colour changes. So, how low can you go? If you have, like, a paper and pen or a tablet, You can take it and try to use two colours to come up with a colouring sequence that has the least amount of colour changes. You can also do a dots or dashes notation, or just think about it. Just take like a minute to think about how you would go about this. You do know the sequence in advance, yes. just raise hand just for the sequence so I'm gonna ask you if you found like what is the minimum number of changes you found you can just yell it in just yell a number to anyone that can go lower or that has a higher number five cool for Okay. So, we see there's different solutions here. And we heard the optimal solution, which is 2. I'm going to show it to you. So, you start A, B, B, D. Oh, it's not showing. Sorry. I'm not going to show the optimal solution to you. It's just not working. But let's just assume or believe me that two is the optimal solution. You can do it with two. Now, the second mental game is how did you get there? Like, can you describe how you got to this solution? So, usually, what I hear is when I do this with different audiences, this mental game, somebody says, well, I started in the very beginning, and so I started in the very beginning using one colour, in this case here, using white, and I use white as long as I can until the second car arrives that has already been painted white, and then I'm going to change the colour, and I keep on doing this. With this solution, you get to four colour changes. Now, if somebody tries to do that from the back, starting at the back of the sequence with the same, basically the same way, same solution approach, you would get to the solution of two. I've also heard very interesting things about let's pick the maximum length of non-changing letters and start from there. That's also a cool approach. And all of them lead to a solution. And this solution approach that we were just talking about, this is what we usually in mathematical optimisation call a heuristic, kind of a brute force algorithm. We describe basically on how we get to a solution, like different steps you take, right? You start with one colour and then sometimes you change, or you pick the longest sequence and then you change. And basically what this does, it's a local search, and it does do decisions based on like a local optimum. You're not looking into the future. You're just making decisions based on where you currently are. And I've been to a lot of companies that all do something like this. Usually they do it in an Excel notebook or it's a Python script where they have kind of written description on how to get to such a solution. It basically automates manual decision-making. And this is something we see very often, and it's what we love most, right? We can just think about the solution approach, the different steps we need to make, and we just put this into a Python script, right? You don't need to follow along all the lines here. I'm just going to briefly go over them. But the idea is you put the sequence of cars in, and in this case here we have six different car types, and then we're going to have a function that paints a car, basically tracks our decisions, and in the end, we're going to have an algorithm, we're going to start with a white colour, we walk through the sequence of our cars, if we have not yet painted the car in the current colour, we're going to paint it in this colour, if we have already painted it, we're going to switch to a different colour and track that there is a change in colour. So that's basically a very greedy brute force algorithm to come to, as I said, the solution here for colour changes. Very cool. The cool thing here is now that I have this implemented in kind of like a structured way, I can use even larger sequences, right, that on a piece of paper or as the human brain has problems to approach, I can use this for a lot larger sequences. So here we have 18 types of vehicles, not just six. And then with the solution approach we get to ten colour changes. And we can even make it more complicated, right? Try to approach the real world problem as it is in practice by saying, okay, now a vehicle type does not arrive exactly twice in the sequence, but at arbitrary times. Basically, the demand that we have. So you can do that as well. So you have, again, a random sequence. 128 vehicles arrive, and we do have a demand for white cars and a demand for black cars. So very cool. You can do some adjustments to the greedy algorithm in your Python script, And that leads you to number of changes, 38. So 38 changes with our solution approach to get, well, all the demand covered with our solution approach. And I bet in this room there is at least a handful of people that have done something like this or exactly like this. Just to give me, like, an idea of who has done something like this, give me a raise of hand. Okay. So there's a bunch of people that can, well, relate to what I'm doing here. So this is nothing new I'm telling you. But the problem is, how do I know if my problem or the solution approach that I chose is actually good? If we recall the start of this discussion, we thought about, okay, so we can start from the front. This gives us four color changes. We can also start from the back. gives us two color changes maybe for a longer sequence starting from the front is best for other sequences maybe starting from the back is better maybe there's a total different algorithm or approach i could use to give me an even better solution the point i'm trying to make is there is thousands of approaches you could come up with to tackle such a problem and depending on the sequence and how those calls arrive, one performs, outperforms the other, and you never know which one is the best. And in the real world, you cannot just brute force and try all approaches. At some point, you have to decide which one to use. And that is somehow problematic. But the good news is, here is the art of the optimal. This is where mathematical optimisation can work for you. So the art of the optimal, mathematical optimisation, what is the idea? The idea is that we change our perspective. So in the first part of the talk, we focused on, as I said, defining rules and, like, steps, procedures on how to get to a solution. So you can voice this to a colleague. You can easily tell how you got to the solution. And now we change a perspective to basically describing our problem, and not the rules, but steps that we have to take to actually come to the solution. So we do describe the problem basically saying we do have a decision to make, so we have to decide which car to colour and what kind of colour, and that's going to be our decision variable. And then there's going to be a set of constraints that says each vehicle has to be painted white and black. The cool thing is, if you can model something like this in a mathematical optimisation model, you define the problem space, and once you have the problem space, you can use off-the-shelf software that can mathematically solve this problem to prove an optimality for you. So there is no hallucinating or anything about it. It's just the mathematically proven optimal. Now, I'm going to show some math here. You don't need to understand the math. If you want to use it, there's OR specialists, like operational research specialists or mathematicians that can do the math for you. We do also offer consulting. But I just want to get the idea across what optimisation is. Here we do have two sets, i and j, and a subset, i, j. Basically, what this does, it's just a way of coding or encoding the sequence of arriving cars. So i, j is basically a tuple. 1 and j, or 1 and a, basically says, well, at position number 1, type a is going to arrive, and 2d is going to be, well, the second position, there's a color of type D arriving. And then we have the decision, X variable. So X represents the choice of the color. If X3 is going to be one, it's binary, it's either one or zero, so if it's one, we say it's going to be black painted, and if it is zero, it's going to be white. And this way, we can basically decode our sequence. Now, we want to find the minimum amount of colour changes, so what we do is basically we track the decision, x and the next x, so x at the position 1 and x at the position 2, and if they're not equal, then this is a colour change, so it basically gives us one point in our optimisation, in our objective function. And then we define that, well, every vehicle has to be painted black once, and white, and X can only take binary values 0 or 1. And that is all we need to do. And then this opens up the world of optimisation solvers, off-the-shelf solvers that we interface to, that as I said, do guarantee the optimal solution. So if you are able to formulate your decision problem as a mathematical optimisation problem, you can use off-the-shelf solvers and you You know there's no superior solution, so it guarantees you that there's no better solution than the one you are getting within the constraints you defined. And now you need to translate what you've written down on a piece of paper, like your algebraic model, into something that can be processed by solvers and computers. And this is where GAMSpy comes into place. It's a Python library that interfaces 36 different solvers, and it's basically a wrapper around our execution system. The syntax is very close to what you would write on a piece of paper, and the only thing you need to do is to say pip install gamspy. To give you an impression of how this would look like, everything related to your model is living in a container, and then you do create the sets, so i and j, we just talked about those, you say this is the number and the sequence and the card type, you have the subset of the sequence decoding, and then you have the decision variable, you're going to say this is over all of the i's, so the domain is i, it's a binary decision variable, it indicates the colour. And then, as I said, it's very close to the mathematical formulation, you say the objective function is the sum over all the i's and you square over the x i and the x plus i plus 1. And you do this for also the constraints, so you sum over the i j's and the x i's and then you say, OK, this is going to be equal to 1. Now, once you've done this, you can just call, this is my paint shop problem, this is the equations I'm going to look at, it's a minimisation problem, and then you can call paint shop.solve. And you can select from a variety of solvers, 36 as I said. Now, what we get here if we print the solution is our optimal number two colour changes. But we already knew that, But the great thing is, now that we have it, we can also make it more complicated. And also, we know we cannot go lower, so two is a proven solution. No better solution exists on the planet. Now let's extend this model, right? Not have the arbitrary amount of cars and different car types arrive. There's little changes we need to make to our algebraic model, little changes we need to make to our implementation, and what we get is an optimal solution of 23 colour changes, and if we recall that with our start from the beginning approach, we only got 38 changes. So you see, it's like there's a real difference in trying to write a solution procedure to get to a solution or really getting the optimal solution. You can think bigger, right? There's a lot of potential to really optimise the decisions you are making every day. And the cool thing is, this was just an example from, like, a car assembly line, but you can use optimisation basically everywhere. Everywhere where you have to do complex decision-making is a place where you can really use optimisation to improve different KPI measures. So just to name some of them, logistics, right, energy sector, agriculture, portfolio management, how to pick a good portfolio. This is all those applications where mathematical optimisation can accelerate. And before we're going to wrap this session up, I want to invite my friend Mohamed to basically give you a sneak peek into what you can do with machine learning and optimization.

Speaker 3 [21:26]

I guess the microphone works. Nice. Thank you, Justine. So Justine already gave the example of paint shop, right? But let's make it a bit more realistic. Whenever you go into one of those car factories, there is this machine like an oven, right? On each side, there is a curing heater. And at the bottom, there is a conveyor belt, as you can see. The conveyor belt moves the car, and the curing heater heats the paint so that it sticks. Otherwise, it bleeds or it sags down, right? And these are two important parameters, but there is no mathematical equation for this known, right? So as a good old Python developer, what you do, you usually train an ML model, right? Maybe a linear regressor to find the defect rate, right? and we want to minimize the defect rate as much as possible so that we don't lose money. So normally when people think about machine learning and optimization, they think of it like two very different things, right? And they are not so wrong in terms of software packages until GAMSpy. So, GAMSpy is basically converging machine learning with optimization. Normally, in machine learning, you have some sort of data, you did some experiments, and you train a model on it, maybe a neural network, and you make a prediction. But in the world of OR, you specify basic rules, your constraints, and your objective, like what you want to optimize, basically, and you make an informed decision. So, here is an example of a model. It's a very simplified model. So, we have two features, which is the speed of the conveyor belt and the temperature of the heater. If the conveyor belt is too slow, or the temperature of the curing heater is not that great, then you you have more defects, right? You already have a lot of experiments in your factor. OK. So you load your data, and you make predictions with this model. But here is how we can turn it into, oh, can I see the cursor here? Nice. Here is how we can embed that PyTorch model into GAMSpy. We have certain formulations, like torch sequential in this example. So we first define our machine settings via one batch and two features, which are the temperature and the speed of the conveyor belt. We did some relabeling. This part is not important. And we put some constraints on it. So this means that the conveyor belt speed can be between 10 and 100 meters per second. And the temperature can be between 150 degrees and 300 degrees, just like in a real production setting. And this is all you need to do to turn your PyTorch model into GameSpy algebra. You just give it to it and GameSpy generates the mathematical equations for you, which is pretty cool. We do a lot of magic in the background so that you don't have to come up with the mathematical equations and you just put your machine settings and it gives you the predicted defect rate. And let's be a bit more smart about it. Our main constraint is that we don't want too much defect rate. Let's say up to 5% is acceptable, right? So we have a quality control equation, and we put a constraint saying that it cannot be more than 5%. And we define our objective variable, which is the speed of the conveyor belt. So what we are interested in is to optimize the speed of the conveyor belt so that our defect rate is as low as possible. Here you define your model. It's a smart paint shop model. You get the equations and you want to maximize the target speed. That's your goal. Sorry. Since we have a ReLU in the PyTorch model, and it's a nonlinear function, it's a non-continuous function, it becomes an MIP problem, which is mixed integer problem. And you solve it, and it gives you the best value for the conveyor belt speed without exceeding the defect rate of 5%. So in this way, you actually combine machine learning and optimization, right? It's pretty cool. And beyond PaintShop, there are lots of use cases for this thing, and I think it's very promising. Not a lot of people are working on it, it's my feeling, because it might be a potential game changer. For example, there are smart energy grids. Just like in the PaintShop model, you have a prediction, and you have something to optimise for. Here, you predict for the energy output, and you optimize for the coal power. For example, currently in Germany, they are pushing more and more for renewables, but renewables are not enough to satisfy the whole demand. But we don't want to use coal plants too much, because it is destroying the environment. So we actually want to minimize the coal usage that we have. That's one case. Or you can use it for dynamic pricing. You usually predict the customer demand based on the previous year's data. And what you want to optimize is the price so that you can sell more. Or you can also do neural network verification. This is a very classic example. Probably most of you already know about it. It basically tries to recognize the number here. But what you can do is that you can train an optimization model to find the minimal perturbation to fool the neural network. Like, how many pixels should I change to make neural network think that it's not a 4, but it's actually a 2, let's say? So there are some fun use cases like this as well. So that's the end of it. This is our boot. Most of you probably have seen us, but for those of you who didn't visit our booth yet, we expect you anytime. If you have any questions about potential use cases, we would be happy to help our panel answer your questions. And you can contact us via our emails or our website. Thank you.

Speaker 1 [29:13]

Thank you very much for your presentation and for the time management. It was very good. We have some questions for you. One of them is, how does GAMS-PAI differ from PAI-OMO?

Speaker 2 [29:31]

That's a very good question, one that we get very often. So, as I said, GAMSpy and Pyomo, they both are Python packages and they both allow you to write your mathematical models in Python. And they are solver independent, so they interface with different solvers. The main difference here is, first of all, the syntax, which is for GAMSpy much closer to what you would write on a piece of paper. It's super easy, readable. And the main difference is probably