Multi-Objective Optimisation

Key Takeaways

yeah so I think uh thank you so much for the kind words and I think uh let's just go forward with the uh optimization and application to ads and yeah so I think the major agenda today is that like we look at the mathematical programming or the uh commutator optimization that we have and how we can actually use that to solve bunch of problems in ads the primary focus today is to actually develop a motivation as to why we can use uh optimization techniques number one and number two uh use Google or tools to like handle couple of problems that we discussed today so that's the whole agenda and the success of this session would be like if if I could actually uh basically motivate people to start using those or tools and they can start thinking in terms of like optimization um one thing I just want to call out that mathematical optimization or sorry mathematical programming or commenter optimization as it says um it's a very vast field and we won't be able to cover up even a bit of it in this session but this is more like to wet the appetite of people so I hope this screen is the font sends all those things visible good yeah so let's just go on to a simple example just to motivate a a typical scenario so what what you want to do is that like let's assume I am an ad Channel and like I have three channels available to me and uh I I can actually receive clicks across those channels I just call them ABC this could be like Google this could be like Facebook and so on uh and and also I have is things like age range so if you look at this table right so on the um on the rows are the age range and what it tells you that like for example column uh like the the cell which is corresponding to column A and the age range 18 comma 25 which says 10 it says that like for generating clicks uh on this channel I I need 10 Impressions from 18 to 25 range now the question that you want to ask is that what is the maximum number of clicks that we can achieve provided we have this kind of data now this is one of the key problem for bunch of people right bunch of folks agencies ad agencies and so on who are advertising across multiple channels and this is a key problem for them so now we want to as you understand right like there are multiple ways we can actually uh primarily Focus only on a and then consume some number of clicks or we want to do a mix of a b and c and so on so this is a kind of uh problem that we talk about in optimization which is the Crux is that like you have some information available and then you want to optimize a certain criteria so uh if we talk about like what are the various ways in which this problem could be solved so I think there are a lot of modern languages so there are like ampl Gams and so on these are like sort of formal languages which have been devised to uh pose this previous problem like whatever uh this operation program is and similarly there are a bunch of solvers so what does what does it mean between modeling language and solver so modeling languages like programming language they they sort of explain ex Express this mathematical model in terms of uh like something that computers can understand and solvers are like sort of like uh if you think about like they're actually like machine learning algorithms or these are algorithms which will optimize it like these are these are ways of taking up this formulation and then so coming up with a solution that is optimized for it and then we have bunch of solvers for this now if you think about it uh there's like huge research that has happened in past uh past 1500 years and these are like primarily use across multiple um multiple kind of modeling in fact uh just for the sake of this thing right so in I think in 1940s or 50s there was work done by uh Economist Scholars Leon Tiff who who actually further received on Nobel Prize where he used like bunch of equations to express how does economy work so such kind of formulations can actually be solved using these for solvers now one of the key aspect of this kind of solvers is that like many of them are actually commercial uh they're pretty expensive and uh like it's not applicable in lot of uh day to day usages so that's come the place where we say Google or toolkit so or is basically operations research and this is a toolkit that is provided by Google and it's available like well integrated into Python and so on and this is the focus of today's talk uh it's very easy to install like you just do pip install or tools um the advantage of Google or tools is like multifold so first thing is that it has bunch of solvers as we see linear and integer solvers which are integrated into the software package that's one of the first Advantage number two it's it's rightly integrated into a python thing so like you just do pip install and then you can start solving it through your jupyter notebook or something like that that's the second major advantage number three is free of cost so if you want to solve a problem in your business use case and you want to just see whether the optimization is actually working or not you can go ahead and do that through or toolkit if you realize that okay your problem is really large scale and you need to invest into some class uh the actual commercial solver then you can actually take a call between Google or and the that's the kind of solver so it's sort of like the same kind of freemium model that Google has applied elsewhere like basically take these things and like you can try this and then go forward so the Simplicity and the uh and the and the way it has been done uh that's where I think I picked up Google or solver to demonstrate today's term now let's just come back to our original problem so I think let's just not focus on the top part of it right now let's just focus on the bottom part of it and uh what we are saying is that like we uh want to figure out um uh this problem which is like you can generate ad clicks across multiple channels you have audience coming from multiple age ranges and then and each age range you have like number of Impressions available which is given by the total uh the row total and so on and now you want to figure out what's the maximum number of clicks I can generate so the first thing that comes up to your mind is that how do you even approach this problem so we need to start thinking about what is the variable here like what are we exactly solving in response so in this case if you look at right the the row totals which are like 800k 500k 100K corresponding to age range of 18 to 25 25 to 35 and greater than 35 respectively that is a given quantity so we can't control that right so you can't change the Impressions which is possible there are the opportunity where you can show your uh ads and so on so um that's that's not a variable there now we look at the other part right so what what else could be a variable so if you think about it in this case right uh if you think about the the sorry so the number of uh Impressions like number of the the number of participants participation from each Channel that's one of the variable so let's assume we denote that how many times I participated in a uh B or C across these channels like say x0 X1 and X2 so the objective that we have is that we want to maximize this clicks which is being generated by a x0 sorry A B and C now what are the constraints that we have so let's assume we have x 0 clicks being generated from a so if that's the case then um it would have taken uh 10 impressions in the range of 18 to 25 or 15 Impressions from range of 15 uh sorry 25 35 of eight Impressions from greater than 35 to generate this click so this is like one of those things that can happen so what we have constraints here is that like for every time I pick up uh a a Channel of like x0 I need to have like uh so that's where the constraint comes we say that like uh if I consume uh x0 units so 10 into x 0 plus 12 into x 1 and 22 into X2 that sum should be equal to 800k or lesser than 800 like if I don't want to use a complete age range similarly I have things for like um uh 25 to 35 and greater than 35 so if you look at the top right what we are trying to say is that like you can have the quantity x0 X1 and X2 such that these three constraints are satisfied these are the constraints in terms of the total available things so whatever is the ideal value of x 0 x 1 x 2 is what is going to maximize the number of clicks now if you just go for a solution to this like how do we actually solve this problem so if we think about logically right in terms of uh algorithmically uh we would try to do some sort of like um like either um a kind of a three for Loop which is basically running the x0 into something or you write a DP or something like that so that's the typical setting which we are working now let's just one minute move on to the solution for this put so I think let's just look at this right so this is our problem add allocation problem that we are looking at in now as we discussed before right so we have um the objective where we want to maximize the num uh the X1 plus X2 plus x0 now again in this case I just took an addition just for the sake of demonstration but you can actually have different kind of functions you can say that maybe there is some second order utility such that x0 the utility from x0 is like twice of X1 then we say like okay x0 plus 2 of x one because for x one to be like for every unit of x one to be valuable should have generated like uh twice or like half of what x0 is generating so we need to basically make sure that the quantity should be much higher than so those things can be changed like this is just a simple objective now let's just come back to how do we actually solve this problem so I think let's just start with this uh or two so I think this is just a solver that we are picking up what it tries to say is that like from the tools we want to pick up a linear solver now if you think about it uh is this basically the added location problem so in this case what we are trying to say is that we have a solver uh T is just the name of the solver now we have a solver where we want to uh say that we want to go for a linear program now why we are saying we want to go for linear program because in this case if you look at it the objective is a linear function what does it mean by linear function because there is no uh term which is there's no power there is no uh like there is no x square there's no x0 into X1 and so on so everything um every every term of this equation is linear in the variables so that's where we want to go for a linear program now linear programming has lot of beautiful properties and it's like much more tractable it's much more solvable and if you go for the mathematics like if you go to mathematics of it it's a nice property that the solution lies on a Simplex like basically a convex Hull of the potential points which are there so it has neat uh computational properties because of which it's very fast so we just want to pick up one of the linear solvers now what we want to say that in this notation right in this uh what you call is the or2 notation the key thing that you want to do is that you want to First Define the variables so we want to say that I have some variables X so I say that these X's are basically a number like here I have just arbitrarily put another constraint that uh like the value of x need to be bounded by between 0 and um 100K so you can have a different number but what we are trying to say that like X is basically a vector of numbers so we say s is like our solver and we are just adding a numeric variable whose lower bound is 0 and upper bound is 100k and we just denote it by name like X of i x sub of I and what you are saying like it's basically a name that we want to represent to like it's basically you to refer that is like a sub of I like it's a variable of I that we want to do and similarly there is another variable that we Define which is again a numeric variable which is the pop which is like summation of these two all these three and um we say like since the maximum values of each one of them could be 100 case I just set it to 3 entity so now if you pick up this whole thing then I want to say add more constraints to it so in this case I'm saying saying that 10 of X like as we discussed I was just like the directly mathematical translation there so it's a 10 times x of 0 plus uh 12 times of x x of 1 and 22 times of X of 2 should be less than 800 k so that's my first thing and similarly like uh it's like the second equation and third equation finally I would want to say that like the pop which is there should be uh sort of that's equal to the summation of these three so this is because I am going to ultimately I want to make sure that I want to maximize pops when I'm maximizing that variable it practically means that I'm actually maximizing x0 x 1 plus X2 and then I go ahead and solve it and I get the solution value so if I look at it right in this case if I try with this uh set of numbers where I've actually put this thing and there is no other constraint that is there so I can just go ahead and solve it and uh so basically I I here I get the solution so what it says is that like primarily it's trying to say that the maximum value uh that you can get uh for the summation is by uh like 19 000 at the close to twenty thousand so this is just a numerical so twenty thousand if that is coming from only picking up these so it's basically saying that like you want to maximize uh you can maximize the clicks from uh by actually consuming the maximum quantity from the B side of things uh if you look at um uh if you just say maybe change these values to say smaller like say I just change it to say eight or something could you please zoom in a bit pardon can you assume the screen oh this is only one minute [Music] is it good yeah and now it's fine thank you question till this point unfortunately I'm not able to see the chat you know okay sure okay so I can't show you guys how can I share this is what this is running on my localhost so I can uh shall I just copy The Notebook to some some place so maybe you could uh down load this Jupiter notebook and you can share it via chat session or you can send it to us we can share it okay so I think there is one question from uh rutuja Sanjay and I think okay so which is basically like how was the uh value of uh 100K uh decided in third line so as I said like this is uh this is I just put as uh as I told like this is just a reasonable constraint I put together was nothing in the problem and I uh if you don't put it it's like going to uh it just what you call is uh uh nothing uh changes there because ultimately since it's a constraint problem the numbers X cannot actually take a negative value we have zero so it's all all there all strictly uh non-negative numbers so the addition will be a positive quantity and it cannot go beyond certain number so just for the sake of uh Simplicity and like performing this thing it takes two arguments and it's like much simpler to give like the maximum limit that's how I put it if even if you don't do it mathematically it's not even required so if you think about in this maximization um since these are all positive quantities and there is a constraint for uh and this like x 0 x 1 these are all positive quantities everything is positive here so there exists a limit Beyond which this number cannot actually increase so it will still converge mathematically it just eases up a deep thing here so there's no um uh what you call as any specific reason it's just for the Simplicity of things perfect I think there is a very good question by uh Omar uh kurban and I think yeah so I think I would want to evaluate on that so I think that's a very good question so what he's trying to say is that like uh what can we do the sensitivity analysis now a very interesting question comes up is like what does it mean by sensitivity analysis so um that's the thing is that like um when we say sensitivity so we have actually got a solution here like if you look at there's a solution that is generated um the natural question that would come up is that like how sensitive uh this equation like how sensitive or objective is to this uh solution like for example instead of 19 000 if I would have taken uh say 20 000 or 21 000 or say something else um is it is it that like of the optimality will get impacted too much so if the solution is very sensitive uh even the neighborhood points uh to the optimal solution will actually cause the uh optimization to be to become drastically worser than what is optimal solution so yes what tools do allow us to do that uh particular kind of optimization now in terms of check its optimality so the optimality is usually uh the way this is linear equation is given up here in the thing um this uh tool is actually this solver actually returns back the optimal value um and in this case like it's guaranteed because it's it's guaranteed by the way Simplex algorithm runs uh it is bound to uh return you the optimal given um the current problem solution it's not it's not a it's not in that phase it's not a Monte Carlo algorithm where the um the uh that that it will come back within some fixed time if the solver if the solution is like much complicated requires like traversing the whole Space it will do that so it is going to guarantee you that it's going to give you the Optimal Solutions um does that answer your question number one perfect let me just go back to my thing so yeah I think uh we were um yeah so this is one of the solution that we have and the Crux of the thing that we did here was that like we actually uh took that problem and we defined the problem in terms of an optimization objective and we also Define what are the constraints that we are operating with and then we uh use the uh or Tool uh library to specify the problem and uh like just specify the constraint and the objective into this uh solo into the word language and then use it to solve the problem so I think that's the beauty of this kind of uh situation Solutions uh is that like we sort of still take the uh take the seat of the uh formulating the mathematical optimization and let the solver solve it now and for most of the interesting problems uh we have good Solutions available but at this Junction I also want to call it out that like although one of the caveat that goes with this formulation is that like uh mathematical optimization um is invariably specifically in this zone is invariably written with problems which are all NP complete on NP hard when we say NP complete and pick up NP hard it basically means that uh the the actual Solutions will be explanation like their their exponential complexity and hence uh sometimes the solution is not even feasible and sometimes Solutions are like um approximate and that's where what has happened is that over the over like last 50 years of research we have identified some very uh fixed forms of mathematical problems so one of those forms is linear optimization so when we talk about these fixed forms like which are very specific forms of problem uh formulations it also guarantees that there are like exists uh like completely accurate algorithms and so on yeah I will share the material for this session okay so the second question is uh uh uh from Bal subramaniam yeah so in case of second or third or four degree Point okay so cool I think uh the moment you start going to second third or fourth uh degree polynomial we have to go for quadratic and even more complex optimizations uh note that like third degree or four degree polynomial um it becomes really uh complex to optimize it and they are like computationally very expensive so typically uh what we do is that like if you if you firstly we try to go ahead for um so by the way Oscar I'm going to share all these things it's just that I was like uh like I was not I didn't know how to share it right now but otherwise I will share all of these things so don't worry about that part both uh these slides and the um uh and the what you call Jupiter notebook yeah coming back to uh bala's question so uh in case of um like if you go for this uh quadratic kind of uh function so if it's like quadratic objective uh we have uh solvers available which are called as quadratic programming and one of the very celebrated example of the quadratic programming is like svm Optimizer so svm uh support Vector machines that we solve in your machine learning is actually quadratic optimize uh quadratic uh objective and linear um what you call as constraints uh higher even higher degree uh polynomials um though what we typically do is that like if the if it's like four degree vertical optimization it is objective it's like super complex what you call this objective and technically we avoid them so usually if you're getting a third or a four degree thing we just have to think about is it your variables that are coming into picture like if it's a variable then you can still pose it as a linear combination of variables which are uh third degree or four degree of the so for example if it's X right so you can still like if it's like X Plus x square plus X Cube plus X fourth kind of thing you can still treat that okay I don't want to play around with the degree so I will just assume there are four variables which are x x 1 x 2 x 3 expose like that x i is equals to x to the power and that power like that it's that component so it's like what you call as like uh mixing uh polynomials but so the function will still be linear so you have a linear objective which is like X One Plus x 2 plus this Lambda 1 x 1 plus Lambda 2 x 2 plus Lambda 3 x 3 and so on where X2 can be squared and X3 can be cubed if your objective is naturally uh four degree um there are like the standard linear programming and these things don't work you might have to go for more approximate what you call is optimization there but you have to think about like because the four degree polynomial as an objective is rarely encountered like typically we don't encounter it uh hopefully that answers your question so um let's just come back to sorry let's just come back to um the linear optimization so I think we want to discuss about what does linear optimization mean so there are three things that is happening up here number one the variables so we are saying that variables are always continuous that's one of the fundamental things uh if the variables are not continuous this becomes like really complex problem and why that's happened because it becomes like a combinatorial optimization and the thing is that this continuity factor is is very uh is something which is not well appreciated but it has like tremendous benefit in optimization so what does continuity means continuity means that um if you are if you have a variable X and you are in a region you just say X Plus small value like X was one and then you you consider a value for that function for X for x equals to 1.01 if the function is continuous you can make some assumptions that um the value in the neighborhood will not be too different from value at x equals to 1. so if if value at x equals to 1 is sub optimal and I have some like I can make some reasonable assumptions about what will happen at Expo x x equals to 1.01 so with this assumption I can optimize things I can actually say that okay if x equals to 1 if the function is decreasing function and if x equals to 1 it has some value I can have some reasonable judgment about where the next nearby value will be and I I may not even have to evaluate that function so if you think about this whole optimization you are nothing doing nothing you are actually just taking a big loop a big for Loop across all the variables like it's a nested for Loop and they're just iterating and generating a values and iterating and seeing evaluating the function whether what's the value and keeping the maximum this is the name way of implementing it but with all this continuity and all those things what we have figured out that there are better ways of doing it like we can actually evaluate the uh differential and say okay what's the rate of growth of the function and which direction you should go ahead and so on a similar thing happens even in your neural networks when you do solve this sgds and so on that's a similar kind of thing so that's the that's the underlying thing so that's where being very variables being continuous is a very good benefit that we have number two the constraints have to be linear so when we say constraints have to be linear what it means is that whenever you solve this linear problem you can actually represent a constraint by straight lines so the moment you put straight lines you have nice properties that you can Define convex cells you can say that okay if x is one of the constraint is X should be greater than 0 the second constraint is X should be greater than 100 so you know that there are two parallel lines which is x equals to zero and x equals to 100 and the the solution spaces between them now you say Y is equals to 1 y should be greater than one and Y should we get less than 10 so you know there are two horizontal lines um which are parallel horizontal line and which restrict the thing so you can and you can be very sure that the the solution lies in the rectangle and you can further be sure because it's a it's a linear optimization that the solution will lie at the vertices of the uh of the rectangle now people who are interested in knowing why that is so I can actually connect them often but basically say that the solution lies at the convex cell so instead of evaluating every point in the rectangle you can now just evaluate the points of the Four Points of the con the rectangle which becomes is much simpler and to ensure that this happens the third thing which is super critical is like objective function is linear so the if the objective function is not linear what does it mean it means that your objective can actually make huge strides like for example it can actually go arbitrarily big and small uh if the function is not uh if the function is not linear so for example let's assume it's a tan H function there can be sudden jumps very spiky gems uh in the function for a small change in the value of x so those functions again violate the principle violate the conclusion that Solutions are going to lie at the convection so that's why it's very super critical for linear optimization to actually have constraints and objective both to be linear now the the strength of this method is that is super efficient like these are one of the most efficient algorithms and they are like sort of a linear in in the input variables and so on so one question that Bala was asking right like if suppose you don't have something which is linear so the the computational complexity of linear optimization is so so so uh lucrative that people actually go ahead and solve like in fact even if if it wants they will actually we pose the problem forcibly into the linear function because now we know that it's a stable solution available so let's just go into one of the another problem which is very common in nowadays so everybody is influencer today so let's assume I am a social network and I have M influencers so they don't exist on my uh platform and I want to incentivize them to basically create content for me so now what happens is that like each influencer uh that we have sorry there's a typo it's not M yeah the Eminence so there's like M influencers and and for uh say Nigeria um categories so each inversion can generate content Over N categories now what we want we also know that we don't want too much content in uh each category so we want minimum content in each category but also maximum so we don't want to take sharechat and like make it like a bhakti Channel or a devotional channel so we want we want it to have like say maybe X percentage of content maybe from devotional from Bollywood from movies Sports and so on so we want to have min max on the content that each category needs to be generated the Crux here is that like we need to pay some cost to the Creator so every time we want to engage our creator we need to pay a cause there and then what we want to do is that we want to solve a problem that how do you create a combination of creators so again I have posed this problem so let's just focus on the left hand side firstly so we will again solve this through python code base so what we're trying to say is that like we have c0c1 C2 and C3 these are four creators that I have and uh T1 T2 T3 T4 are like type of content they can generate so what it says is that c0 can generate um six uh six units of content of type T1 uh 10 units of content of type T2 and so on and we also have things like what is the minimum content I want to get from c0 and what's the maximum I can get from c0 so that's that's the that's a kind of constraint that business has given to me and the cost is associated which is like what is the cost that I get for actually taking this Creator um similarly I have uh vertically if you go down deep down in the T1 column it says that whatever the minimum number of type I need so I need to have like so that my audience can engage with me I need to have at least 50 units of T1 but I don't want to have more than 154 units of T1 so this is basically a setup okay perfect awesome so I think um one other thing right so I think there are two things that we are talking up here so when we actually talk about neural networks uh note that like neural networks have uh the the atom and those things that we do there they do not guarantee you the optimal uh it's a Monte Carlo it's a Monte Carlo algorithm which is that that's very unlike epox and X number of epox and so on so it's not guaranteeing any kind of optimization per se uh the optimization that I am talking about these are all optimizers which will actually converge and give you a solution out of it so that's the first first difference there number two what you what you see it uh which is actually very true and that's that's what I said in the beginning of my talk that um this Optimizer or tools and so on they are great um because uh they give you uh initial solution or initial proof of concept and if you feel that uh it can actually answer your questions and you want to literally go to a like a billion or trillion kind of uh firstly like 1 trillion parameters and so on cannot be solved from I don't think that even the C Plex or even the best available solvers can solve it I think the largest LP problem let us solved is I think with a million constraints and I think a million I think a million constraints that's what I remember um and so uh it's like for much larger problem than this I think uh the computational you don't have any solutions available in that case we need to go for something like a more approximate solution and neural networks are just one another way to do that optimization so if you think about it what we are talking is like their exact optimizers if the exact Optimizer don't work you go for an approximate Optimizer neural network is one of them it can be neural networks it can be genetic algorithms it can be uh like simulated or needling so a bunch of those things can happen but those are more uh approximate algorithms um today the talk is more about the exact uh what you call it optimizers I hope that answers your question perfect good so yeah so coming back to uh this influencer part of it so we also have this uh what you call its constraints on various uh type of content now I think the if you look at this problem right it is invariably complex in its bees right now and I think that's where again we as if we just start thinking from our perspective right the way we thought about it uh I think we can simplify it very easily so let's just focus on what are the cons what are the um what are the variables there so here there's no variables in terms of cost so a Creator cost cost is freezed there is no variable in terms of Min or Max engagement that you want to derive from a Creator like how many times you want to how many days you want to engage them and so on um there is no constraint uh there's no variable in terms of like the minimum Max of a type of a Content that is required so I think if you think about it the only uh variables they exist is basically um How many um days or how many times you want to engage a Creator so basically what we say is that like let's assume um there is a Creator which is uh like we denote this variables F0 F1 F2 and F3 to be number of times we engage c0 C1 C2 C3 every time we engage c0 we get six uh units of T1 10 units of T2 5 units of T3 uh two units of T4 and cost is nine thousand and F 0 has to be minimum seven and F 0 can go beyond 17. now astute readers here or astute listeners here will I identify that the engagement with the Creator is actually an integer variable and what I'm using here is a real number now that happens because uh if I go by integer program it's much more complex and it's much more intractable than going by a linear program and hence I actually saw I assume it to be a linear and that's where I connect it back to one of the questions that's writing over us which is the sensitivity so this will become very critical in this case case because when I'm actually taking an integer and I'm relaxing it to a fractional number it may happen that the solution says that consume 1.2 of c0 but I will either consume one or two and hence if the if the solution is very sensitive changing 1.2 to 1 or 2 will actually make it completely worse and then you have to like repeat that uh like we have to study the sensitivity of the solution and then take a call like whether can I go one or two or shall I change the program itself but coming back to this so variables are F 0 F1 F2 and F3 now one of the thing that we want to do as a platform is to minimize the cost like that's a very uh currently this has a very simplistic objective results to maximum minimize the cost so the cost is basically how server times you have engaged a particular Creator and the cost increase so that's basically CI into fi the CI is the cost and F is the times you are going to engage that Creator now what are all the constraints so obviously the constraints are like uh L I A UI are given by the Min and Max columns um which is corresponding to each of the Creator so we say that fi lies between the lower and upper limit and similarly we have some content constraint we want to say that if I want to restrict the number of content uh type content units in the system so that's what is a Ag and BJ which is represented by Min and Max rows so the quantity which is there is like which is ngi which is z which says that like for the jth for the J Term unit uh when I'm actually taking the ith creator for the jth unit what is the the nji is actually the uh the the type of content that the Creator I produces for the jet type of content so the nji is again given based on this Matrix so for example uh n and of like two uh which is like type 2 from um something C1 is basically six so this quantity tells us that I'm actually consuming F5 of this Creator and hence I will get nji units of the jth type and this whole thing should be uh below like the Min and Max given for that particular content now that's basically the form that we have now let's just go back to again yeah so I actually go back to something like uh uh the influencer content part of it so the same thing like the same table here and uh we are actually talking for the variables and uh constraints there now let's come back to I think this is I have actually uh the by the way um there's this very good book I can share you uh which is this this code is actually uh based on the book and the problem uh pose up there and what I did was I actually mapped it to the problem in the ad space so uh basically what we're trying to do here is that like this is our uh solver now this new solver is nothing just but a function that we have kept up here and we just say that whether if you want to go for a integer programming or a linear programming so in this case we by default we don't go for our integer programming and we typically pick up the linear program but the same thing can be used for integer programming as well so we want to just say that this is my uh solver I'm actually uh taking this whole Matrix n now if you look at this n here right so this is sort of the N Matrix which is given at the top one another thing that you will note up here is that like in the uh the if the if you take a single row of this Matrix last three columns are min max and cost and last two rows are basically min max for the type so that's what we have done up here we say that from The Matrix number of influencers is basically length minus 2 which is like the last two rows are removed and that number of types are basically whatever is the first row minus three the last three columns and then what we have done is that basically we have actually extracted these uh few uh things out of uh this is just like um basic maths like basic uh manipulation so we want to figure out like what is the minimum number of this influencer what's the maximum of influencer what's the influence the cost uh what's the Min and Max for the type and so on and now what we're trying to say is that like I'm actually adding up like an F is my function where I'm again adding variables and what I'm trying to do is that like I'm actually uh taking up uh different variables for uh basically different influences for in basically providing the info the influencer count variables which are F zeros one unit um yeah sorry yeah so for each influencer actually uh provided so this is uh this this has to be a variable I'm actually uh sorry for that there's a typo here but what I'm trying to do is that for each influencer I have taken the minimum and Max that is allowed for it and and and that's how I'm creating this F variables which is F0 to F1 with the limits of info minimum and Max now what I'm trying to do is that like I'm actually uh specifying this second uh so this this is this was the constraint I have specified minus specifying the second constant which is saying that the type Min which is the uh the the current uh minimum value like wherever the type mean is the corresponding for the jth thing I am saying that all the places where this particular type has been used based on the FIS that is there I am saying that it has to it has to be lower than the minimum of this and similarly it has to be less than the maximum which should be greater than the minimum and uh greater than lesser than the maximum so these are the second level of constraints which I have specified uh which are from this one like this n i n g i f I should be greater than AJ which is given from the uh type Min uh whatever column the type mean is there and similarly this the f i n i j nij should be less than the type Max column now what I want to do is that I want to minimize the total cost and this cost is again uh given from this which is basically the cost and the times fi is being used and so that's where I'm saying that it's f i into ni INF cost like basically you go to the ith uh go to the vectors of ith like n vector and um vertical array go to the ith row and pull out the cost of the um the influencer which is like basically the same thing so wherever the info this index for each of the influencer go to the index and pull out the cost so that's what I'm trying to do up here and I say like I am actually using fi units so I have to multiply each one of them and then I finally um uh solve it now if I just look at this function again so this is just one simple uh content uh thing I have calculated so if you take it it sorts of shows me like uh this is the distribution like I have to pick up if suppose I increase uh some number to be high here like like sorry um so it doesn't change as much because um it's still going for the uh fourth creative to be maximum now uh let me okay foreign so this is one of the thing that I want to demonstrate so in this case if you think about right I've actually added uh the uh so let me just okay just let me just remember this line okay so this is the line okay and we run this so this is this we were getting and what it tells us that that maximum unit of um uh you can actually get is from like for satisfying other things the maximum unit you should be consuming is from the fourth one now let's just uh take this and uh comment this out and uh I actually increased this arbitrarily so I I sort of make it like okay whenever I'm cons using this and I'm actually consuming higher volume of um um this type T1 now no note that right I actually cannot uh satisfy I I like in order this particular Creator is producing um the type one too much and ideally what happens that I can't I cannot actually take at Max five units if you think about it this is like five units is something like 1100 so I can use only five units of this but because uh that will just uh make this content ahead like if I take five minutes of fourth I will actually sort of exhaust this one and then none of them can be taken uh if I don't take the fourth one uh others one cannot actually meet the minimum of given this thing based on their maximum limit so if you for example this is 360 and so on so they cannot uh sort of meet everything from this thing so if you take this scenario and run the equation it actually gives us the no solution because there doesn't exist a solution where you can satisfy all these things if I do this again it actually sorts of um uh does this note that I want to minimize the cost right but I'm so I'm actually sort of in this Zone if I increase start increasing um this numbers uh maybe do and say uh maybe nine or say 15. so you start seeing that it is still um okay it still doesn't makes any difference here we need to play around more but I think uh What uh let me just try more here so maybe say three no it is still taking one only I think uh am I specifying this correct yeah okay I think I need to figure out something but the the Crux of the matter matter is that layers like uh basically we can actually again uh take this problem and uh uh sort of solve this using this particular kind of optimization now any question till this point no Okay cool so let's just go to the final thing I think we have very uh we are close to uh the time um so let's just go to the final thing uh so uh after this there's one quick problem and then I will just quickly uh tell that problem and then we move forward so I think one other thing that we can do in this kind of problem is that like currently what we were doing was that we are only focusing on cost um now we can actually maximize The Profit I think um in the case when the cost and profit is uh linearly like they are monotonically increasing or like related to each other directly proportional to each other uh my maximizing profit versus maximum cost is the same thing however uh sorry minimizing cost is the same thing but if the profit and costs are like differential like uh the most expensive ones are not done necessarily the most profitable ones then this becomes like a sort of a multi you have to have two objectives there we can also have content level restrictions so for example we want to say that given up our engagement we know that Bollywood content should be at least twice out of devotion content so the in in that case it's not very difficult we just like we have more constraint we say that okay one particular uh kind of content has to be twice of the second kind of content um the third thing can be a bit more complex uh which is like basically two influencers cannot be shown in the same feed so now if you have content from one feed uh sorry one uh influencer you cannot have content from another influencer and so on and so forth um it's not feasible in the current setup because when we're talking on linear thing you cannot have this engagement basically you want to do an xor gate you want to say that uh content one is zero then the other one has to be one and if it's one is one that has to be zero and so on so that's where uh it cannot be done and that's why we need to have like a higher degree uh kind of uh model now um after this let's just move on to the final problem that I want to demonstrate here which is around ad networks so now what happens you have Publishers like Yahoo uh MSN and so on they they have users to whom we can show ads we have advertisers who have inventory and they want to show ads now every publisher ideally every publisher cannot talk to every Advertiser so I have a Blog I cannot reach out to every Advertiser that okay do you want to show me an ad and single ad network is not feasible because for example if it's only Google then um it's like competition is not there so they have the complete Liberty to drive the prices and so on so obviously for this there's a situation where we have demand side platform and there's like multiple level of agencies out there so demand side platforms are like basically aggregators of advertisers so advertisers come and say fine uh take my you know take my ads and show and give me the best best Roi return on investment so the Publishers say that okay they come to supply side platforms they say take my uh user request and then you generate me maximum Revenue so in this setup it's basically like a complex piece of graph that exists so we are saying that there are a lot of Publishers sitting there are a lot of advertisers sitting and then they each one is talking to different uh platform and then they we want to match the uh ads there now if you talk about in terms of like um the optimization here you can think of this as a graph and uh one other thing that the variables here are like the different edges like all the xigs that are there there can be multiple objectives that we can talk about so if we assume that n capital N denotes the uh the the the basically the nodes uh s denotes Source like basically Supply and T denotes the destination in this case it could be ads and so on like basically matching publisher and Advertiser then we can have like the first objective is trying to say that like uh you want to maximize all uh outgoing from Source like basically all the supply is being consumed so you consume the supply as much as possible this objective just says that maximize those edges which are coming which are taking the supply uh this second objective is saying maximize um everything uh which is like consuming the ads like one is consuming the users one is so these are basically mutually same like they are one and the same thing you're saying like either a number of uh opportunities on which ads are shown you count that or number of ads that are consumed you counter it's one and the same because for every opportunity there is one ad um they can also be another objectives that we can say for example internally there's an Arbitrage happening so one supplies platform is sent selling to another Supply platform and if you want to discourage that then this could be the third objective which is saying that inside the node if you're actually consuming within one uh internal node is giving to another internal node we want to discourage those kind of uh solution where you are seeing that okay one Supply platform is sending to another supplier platform that is send it to another Supply platform and the actual ad is not delivered there uh so uh if you go by this uh sort of setup again I think this is a slightly different formulation again a similar kind of thing but in this what we are trying to do here is that like now it's all about the XJ so uh basically uh just in the sake of time it's like since I'm going to share it's the same thing like we are actually taking the X and we have specified the uh this particular objective here now as just a simple example uh to Showcase that this is happening right so C is one of the networks so and what I've done is that like C said c is a network that I have shown so this is say like zero to uh the other node so it says that like node 0 which is on the source sign has edges from uh it has edges to uh node one node two and no adjust to node three the node one has adjust to node three and node to node four and node 3 has adjusted to node so node 12 I just so basically saying that uh the source has uh nodes to one and two from uh node one today is a node three and from node 3 to Note 4 so I think there's only one path like this which is of capacity 12. ah which is going there and now if we can solve this problem right so we say that I want to this is what it tells us that so if you look at it uh cool so what it tells us that like uh the total uh Supply that can happen from uh like Supply to ads is actually 12. so if you think about it from where it is coming it's saying that passing 10 on this Edge which is here and this 20 we have we can pass it on two and um this particular thing can actually uh so this if you take about right so this 10 to 10 to 10 here and there's an additional 2 going directly from here which is being consumed by 12 here so this is what this particular now if I change this to maybe say 15. right uh you will immediately oh sorry yeah you will immediately see that the the supply has increased by uh 15 here so what it says is that now if you take it it says like I'm passing on this 10 to 10 now let's assume I increase uh this to say 20 so I'm actually increasing this particular DSP or something has higher what you call this capacity uh it doesn't matter because this node is still bounded by 10 so it only takes 10 and so on so basically what I'm trying to say here is that like this whole complex problem of how do you schedule was actually again posed back in a very succinct manner in a in a mathematical formulation and that we can again solve now let's just assume that we have uh we want to increase it more we add 10 here which is like the first node is actually directly connected to the fourth node so again if I do this um right so this is certain increaser so it's not saying that I can go 25 because I think uh this bottleneck is removed off okay so um just another extension to this uh that is visual right so currently what we said is that like we just want to distribute the uh ad in the network now we can actually do a differential thing for example um the the cost of showing and the cost that a supply can get from an ad Network Facebook or Google may be different it can have a different weight which is associated and if we come back uh to our formulation right so in this case wherever there was this maximization currently we were just using excise we will start having a cost associated with it and the moment you have cost it will start uh it's based the effect of cost is that like basically you are saying that if something is uh like currently we are seeing the number of Impressions now I say that uh one impression is double the cost of the second one so what it technically means like in terms of algorithm what it means is that the first one has increased the capacity it has sort of become two and now you want to consume that capacity more and hence it will actually drive more impressional first from then on second one uh the second one could be a guaranteed payout so this happens like for example there's a movie launch happening and uh advertisers want to say that okay if you don't give me X number of users I'm not going to pay you anything and if you want to get uh like if you get me million I pay you 10 million if you get me less than a million I pay you zero so again what this means is that like uh when when we have uh this kind of edges like basically this particular thing it will have constraints on uh the quantity um the final quantity that is coming up into J so summation over all the t's like for for a particular T you will summation sum over all these things so like everything that is coming into a into a Target node and you can say that okay if you give me a certain number of Impressions then only I will uh I will take it otherwise I will not take it so you have more constraints which are added there so this problem becomes like it's still the same problem but we just add more constraints update okay um yeah so that's one thing um okay so I think I just want to sorry for five minutes over uh I just want to summarize up here um uh what there are two things that I want to derive from this like number one is that mathematical optimization provides uh interesting formalism for solving very interesting problem like very uh in a very succinct manner number two uh I think Google or tools is a great package for day-to-day job because it's actually easy to use it's easy to integrate into a software it's free of cost and once it shows benefit then we can actually start uh going for like more commercially uh powerful packages which can actually solve much bigger problems note that Google war is not going to solve like as I think Bala was referring right it is not going to solve your a million um uh what you call is constraints it's not going to do that it's also not going to solve like all sorts of most complex solution like it cannot do many kind of mdps and so on but it's a good thing to start with for linear problems and so on and many of your problems for example if you're like I think a big chunk of you must be having working in some form of feed ads or some sort of like some sort of website optimization and I think these things can play a very good role uh in any of those problems like every of those problems wherever there's an allocation happening uh it's a portfolio allocation happening you can always specify that as a problem between a utility across different channels and then optimizing it yeah with any questions uh if there are no questions then um ah the monitor how do we want to go ahead from here yeah I'll let know how will it be sharing the materials uh since the attendants are keeping on asking for that sure so I can do one thing right I can share you that I can actually share the um the slideshow right away uh I think I can share the link there's some way to do that right okay so that makes sense so I can paste it right away [Music] yeah so this is the link part of it um the other thing which is uh uh okay uh there's my oh like for this uh I can share save this file I think this is self-continent the way I've created it's actually self connected I can copy this as well um one minute in just a minute meanwhile I would like to request the activities to place a fill in the poll about the feedback as it is helpful as to help for us to conduct more such sessions um how can I share you the file I have the file now how can I share that uh yeah like if you have downloaded this Jupiter file I have it downloaded okay uh can you uh send it to us through WhatsApp like okay I can do that one minute or if you can share me share the Google Drive Link here I can just put it there uh I I got a pink like can I can I just send it through to Prashant right Prashant from analytics with you yeah okay let me just do that one minute yeah done yeah I have shared him the file okay so I think yeah so uh yeah I think there are a lot and lots of research paper and I think most of the problem like if you read uh so the way to approach this thing right I think it's not about um approaching um a paper which is talking only about optimization in fact every paper talks about that in uh optimization uh for that matter so let me just uh let me just give an example oh this one so let's assume this is the click prediction paper and I think if you think about it uh there's a um yeah this is the this is the solution that's happening up here and uh yeah uh one minute yeah I think this is not and this is sorry I think this is not done but I think the the the the thing that I'm trying to tell you is that like uh most of the papers that you solve with respect to your uh problem space will actually be talking about uh optimization formulation someplace and solving that we usually will be done through this kind of solvers and for that matter neural network itself is like uh one of these odd uh solvers yeah I think this is not done it's I think I forgot that paper but it uh okay it was probably I think this was yeah I think uh moderator you can call it okay thanks a lot Rahul uh on behalf of analytics Vidya I'd like to thank you for your time and for delivering such a wonderful session I'm sure our audience found it insightful and hopefully we can connect more such as in the in with you in the future and the LinkedIn profile of the speaker is shared in the chat session I hope you guys have filled in the feedback poll if not I request you to please fill in the call about feedback as it is helpful for us to conduct Moses sessions yeah and the recording of this session will be available in a few days in our YouTube channel and the link for the same as well as the link for upcoming few sessions is shared in the chat session thank you everyone and if you could wait for few more minutes we'll be sharing the Google Drive Link uh with a jupyter notebook thank you it's already shared okay uh thank you so much everyone so yeah I think that's one thing for rutuja right I think this is the book uh it's such crook practical python AI project so I literally uh the the thing that I presented today I think is first one or two or one or for fifth chapter something like that I just picked that up and um that's the book I learned uh used to learn this or tools kind of thing this is very good documentation on net also available but this is one of the book and it is pretty good intent in terms of like it has seven seven or eight chapters and it discusses all variety of problems like I did a very Peak View at two problem uh linear program and Network program uh it also has I've already pasted that honest now yeah so it has a look at multiple kind of problems so um that's a pretty neat book that I have seen yeah that's what I want to say thank you thank you so much I think it's it's it's above uh the search quick book there thank you bye