[ad_1]
It could be shocking, however on this article, I want to speak in regards to the knapsack drawback, the basic optimisation drawback that has been studied for over a century. In line with Wikipedia, the issue is outlined as follows:
Given a set of things, every with a weight and a worth, decide which gadgets to incorporate within the assortment in order that the whole weight is lower than or equal to a given restrict and the whole worth is as giant as attainable.
Whereas product analysts might not bodily pack knapsacks, the underlying mathematical mannequin is very related to a lot of our duties. There are quite a few real-world purposes of the knapsack drawback in product analytics. Listed below are a couple of examples:
Advertising Campaigns: The advertising group has a restricted finances and capability to run campaigns throughout completely different channels and areas. Their purpose is to maximise a KPI, such because the variety of new customers or income, all whereas adhering to present constraints.Retail House Optimization: A retailer with restricted bodily area of their shops seeks to optimize product placement to maximise income.Product Launch Prioritization: When launching a brand new product, the operations group’s capability could be restricted, requiring prioritization of particular markets.
Such and comparable duties are fairly frequent, and plenty of analysts encounter them usually. So, on this article, I’ll discover completely different approaches to fixing it, starting from naive, easy methods to extra superior strategies similar to linear programming.
Another excuse I selected this matter is that linear programming is likely one of the strongest and well-liked instruments in prescriptive analytics — a kind of study that focuses on offering stakeholders with actionable choices to make knowledgeable choices. As such, I imagine it’s a necessary ability for any analyst to have of their toolkit.
Let’s dive straight into the case we’ll be exploring. Think about we’re a part of a advertising group planning actions for the upcoming month. Our goal is to maximise key efficiency indicators (KPIs), such because the variety of acquired customers and income whereas working inside a restricted advertising finances.
We’ve estimated the anticipated outcomes of varied advertising actions throughout completely different international locations and channels. Right here is the information now we have:
nation — the market the place we are able to do some promotional actions;channel — the acquisition methodology, similar to social networks or influencer campaigns;customers — the anticipated variety of customers acquired inside a month of the promo marketing campaign;cs_contacts — the incremental Buyer Assist contacts generated by the brand new customers;marketing_spending — the funding required for the exercise;income — the first-year LTV generated from acquired clients.
Be aware that the dataset is artificial and randomly generated, so don’t attempt to infer any market-related insights from it.
First, I’ve calculated the high-level statistics to get a view of the numbers.
Let’s decide the optimum set of selling actions that maximizes income whereas staying throughout the $30M advertising finances.
At first look, the issue could seem simple: we may calculate all attainable mixtures of selling actions and choose the optimum one. Nonetheless, it could be a difficult activity.
With 62 segments, there are 2⁶² attainable mixtures, as every phase can both be included or excluded. This leads to roughly 4.6*10¹⁸ mixtures — an astronomical quantity.
To higher perceive the computational feasibility, let’s take into account a smaller subset of 15 segments and estimate the time required for one iteration.
import itertoolsimport pandas as pdimport tqdm
# studying datadf = pd.read_csv(‘marketing_campaign_estimations.csv’, sep = ‘t’)df[‘segment’] = df.nation + ‘ – ‘ + df.channel
# calculating combinationscombinations = []segments = record(df.phase.values)[:15]print(‘variety of segments: ‘, len(segments))
for num_items in vary(len(segments) + 1):mixtures.lengthen(itertools.mixtures(segments, num_items))print(‘variety of mixtures: ‘, len(mixtures))
tmp = []for chosen in tqdm.tqdm(mixtures):tmp_df = df[df.segment.isin(selected)]tmp.append({‘selected_segments’: ‘, ‘.be a part of(chosen),’customers’: tmp_df.customers.sum(),’cs_contacts’: tmp_df.cs_contacts.sum(),’marketing_spending’: tmp_df.marketing_spending.sum(),’income’: tmp_df.income.sum()})
# variety of segments: 15# variety of mixtures: 32768
It took roughly 4 seconds to course of 15 segments, permitting us to deal with round 7,000 iterations per second. Utilizing this estimate, let’s calculate the execution time for the complete set of 62 segments.
2**62 / 7000 / 3600 / 24 / 365# 20 890 800.6
Utilizing brute pressure, it might take round 20.9 million years to get the reply to our query — clearly not a possible choice.
Execution time is fully decided by the variety of segments. Eradicating only one phase can scale back time twice. With this in thoughts, let’s discover attainable methods to merge segments.
As traditional, there are extra small-sized segments than greater ones, so merging them is a logical step. Nonetheless, it’s necessary to notice that this strategy might scale back accuracy since a number of segments are aggregated into one. Regardless of this, it may nonetheless yield an answer that’s “ok.”
To simplify, let’s merge all segments that contribute lower than 0.1% of income.
df[‘share_of_revenue’] = df.income/df.income.sum() * 100df[‘segment_group’] = record(map(lambda x, y: x if y >= 0.1 else ‘different’,df.phase,df.share_of_revenue))
print(df[df.segment_group == ‘other’].share_of_revenue.sum())# 0.53print(df.segment_group.nunique())# 52
With this strategy, we are going to merge ten segments into one, representing 0.53% of the whole income (the potential margin of error). With 52 segments remaining, we are able to get hold of the answer in simply 20.4K years. Whereas this can be a important enchancment, it’s nonetheless not ample.
Chances are you’ll take into account different heuristics tailor-made to your particular activity. For example, in case your constraint is a ratio (e.g., contact fee = CS contacts / customers ≤ 5%), you can group all segments the place the constraint holds true, because the optimum answer will embody all of them. In our case, nevertheless, I don’t see any extra methods to cut back the variety of segments, so brute pressure appears impractical.
That stated, if the variety of mixtures is comparatively small and brute pressure could be executed inside an inexpensive time, it may be a super strategy. It’s easy to develop and offers correct outcomes.
Since brute pressure is just not possible for calculating all mixtures, let’s take into account an easier algorithm to handle this drawback.
One attainable strategy is to give attention to the top-performing segments. We will consider phase efficiency by calculating income per greenback spent, then kind all actions primarily based on this ratio and choose the highest performers that match throughout the advertising finances. Let’s implement it.
df[‘revenue_per_spend’] = df.income / df.marketing_spending df = df.sort_values(‘revenue_per_spend’, ascending = False)df[‘spend_cumulative’] = df.marketing_spending.cumsum()selected_df = df[df.spend_cumulative <= 30000000]print(selected_df.form[0])# 48 print(selected_df.income.sum()/1000000)# 107.92
With this strategy, we chosen 48 actions and bought $107.92M in income.
Sadly, though the logic appears affordable, it isn’t the optimum answer for maximizing income. Let’s take a look at a easy instance with simply three advertising actions.
Utilizing the highest markets strategy, we would choose France and obtain $68M in income. Nonetheless, by selecting two different markets, we may obtain considerably higher outcomes — $97.5M. The important thing level is that our algorithm optimizes not just for most income but in addition for minimizing the variety of chosen segments. Subsequently, this strategy is not going to yield one of the best outcomes, particularly contemplating its lack of ability to account for a number of constraints.
Since all easy approaches have failed, we should return to the basics and discover the idea behind this drawback. Thankfully, the knapsack drawback has been studied for a few years, and we are able to apply optimization methods to unravel it in seconds reasonably than years.
The issue we’re attempting to unravel is an instance of Integer Programming, which is definitely a subdomain of Linear Programming.
We’ll talk about this shortly, however first, let’s align on the important thing ideas of the optimization course of. Every optimisation drawback consists of:
Determination variables: Parameters that may be adjusted within the mannequin, usually representing the levers or choices we wish to make.Goal operate: The goal variable we intention to maximise or decrease. It goes with out saying that it should depend upon the choice variables.Constraints: Situations positioned on the choice variables that outline their attainable values. For instance, making certain the group can not work a unfavourable variety of hours.
With these fundamental ideas in thoughts, we are able to outline Linear Programming as a situation the place the next circumstances maintain:
The target operate is linear.All constraints are linear.Determination variables are real-valued.
Integer Programming is similar to Linear Programming, with one key distinction: some or all resolution variables have to be integers. Whereas this will likely appear to be a minor change, it considerably impacts the answer strategy, requiring extra complicated strategies than these utilized in Linear Programming. One frequent method is branch-and-bound. We received’t dive deeper into the idea right here, however you’ll be able to at all times discover extra detailed explanations on-line.
For linear optimization, I desire the broadly used Python bundle PuLP. Nonetheless, there are different choices obtainable, similar to Python MIP or Pyomo. Let’s set up PuLP by way of pip.
! pip set up pulp
Now, it’s time to outline our activity as a mathematical optimisation drawback. There are the next steps for it:
Outline the set of resolution variables (levers we are able to alter).Align on the target operate (a variable that we’ll be optimising for).Formulate constraints (the circumstances that should maintain true throughout optimisations).
Let’s undergo the steps one after the other. However first, we have to create the issue object and set the target — maximization in our case.
from pulp import *drawback = LpProblem(“Marketing_campaign”, LpMaximize)
The following step is defining the choice variables — parameters that we are able to change throughout optimisation. Our principal resolution is both to run a advertising marketing campaign or not. So, we are able to mannequin it as a set of binary variables (0 or 1) for every phase. Let’s do it with the PuLP library.
segments = vary(df.form[0]) chosen = LpVariable.dicts(“Chosen”, segments, cat=”Binary”)
After that, it’s time to align on the target operate. As mentioned, we wish to maximise the income. The entire income will likely be a sum of income from all the chosen segments (the place decision_variable = 1 ). Subsequently, we are able to outline this method because the sum of the anticipated income for every phase multiplied by the choice binary variable.
drawback += lpSum(chosen[i] * record(df[‘revenue’].values)[i] for i in segments)
The ultimate step is so as to add constraints. Let’s begin with a easy constraint: our advertising spending have to be beneath $30M.
drawback += lpSum(chosen[i] * df[‘marketing_spending’].values[i]for i in segments) <= 30 * 10**6
Trace: you’ll be able to print drawback to double examine the target operate and constraints.
Now that we’ve outlined every part, we are able to run the optimization and analyze the outcomes.
drawback.clear up()
It takes lower than a second to run the optimization, a major enchancment in comparison with the hundreds of years that brute pressure would require.
Consequence – Optimum answer discovered
Goal worth: 110162662.21000001Enumerated nodes: 4Total iterations: 76Time (CPU seconds): 0.02Time (Wallclock seconds): 0.02
Let’s save the outcomes of the mannequin execution — the choice variables indicating whether or not every phase was chosen or not — into our dataframe.
df[‘selected’] = record(map(lambda x: x.worth(), chosen.values()))print(df[df.selected == 1].income.sum()/10**6)# 110.16
It really works like magic, permitting you to acquire the answer rapidly. Moreover, observe that we achieved larger income in comparison with our naive strategy: $110.16M versus $107.92M.
We’ve examined integer programming with a easy instance that includes only one constraint, however we are able to lengthen it additional. For example, we are able to add extra constraints for our CS contacts to make sure that our Operations group can deal with the demand in a wholesome approach:
The variety of extra CS contacts ≤ 5KContact fee (CS contacts/customers) ≤ 0.042# outline the problemproblem_v2 = LpProblem(“Marketing_campaign_v2”, LpMaximize)
# resolution variablessegments = vary(df.form[0]) chosen = LpVariable.dicts(“Chosen”, segments, cat=”Binary”)
# goal functionproblem_v2 += lpSum(chosen[i] * record(df[‘revenue’].values)[i] for i in segments)
# Constraintsproblem_v2 += lpSum(chosen[i] * df[‘marketing_spending’].values[i]for i in segments) <= 30 * 10**6
problem_v2 += lpSum(chosen[i] * df[‘cs_contacts’].values[i]for i in segments) <= 5000
problem_v2 += lpSum(chosen[i] * df[‘cs_contacts’].values[i]for i in segments) <= 0.042 * lpSum(chosen[i] * df[‘users’].values[i]for i in segments)
# run the optimisationproblem_v2.clear up()
The code is easy, with the one difficult half being the transformation of the ratio constraint into an easier linear type.
One other potential constraint you may take into account is limiting the variety of chosen choices, for instance, to 10. This constraint may very well be fairly useful in prescriptive analytics, for instance, when it’s worthwhile to choose the top-N most impactful focus areas.
# outline the problemproblem_v3 = LpProblem(“Marketing_campaign_v2”, LpMaximize)
# resolution variablessegments = vary(df.form[0]) chosen = LpVariable.dicts(“Chosen”, segments, cat=”Binary”)
# goal functionproblem_v3 += lpSum(chosen[i] * record(df[‘revenue’].values)[i] for i in segments)
# constraintsproblem_v3 += lpSum(chosen[i] * df[‘marketing_spending’].values[i]for i in segments) <= 30 * 10**6
problem_v3 += lpSum(chosen[i] for i in segments) <= 10
# run the optimisationproblem_v3.clear up()df[‘selected’] = record(map(lambda x: x.worth(), chosen.values()))print(df.chosen.sum())# 10
One other attainable choice to tweak our drawback is to vary the target operate. We’ve been optimising for the income, however think about we wish to maximise each income and new customers on the identical time. For that, we are able to barely change our goal operate.
Let’s take into account one of the best strategy. We may calculate the sum of income and new customers and intention to maximise it. Nonetheless, since income is, on common, 1000 occasions larger, the outcomes could be skewed towards maximizing income. To make the metrics extra comparable, we are able to normalize each income and customers primarily based on their whole sums. Then, we are able to outline the target operate as a weighted sum of those ratios. I might use equal weights (0.5) for each metrics, however you’ll be able to alter the weights to offer extra worth to certainly one of them.
# outline the problemproblem_v4 = LpProblem(“Marketing_campaign_v2”, LpMaximize)
# resolution variablessegments = vary(df.form[0]) chosen = LpVariable.dicts(“Chosen”, segments, cat=”Binary”)
# goal Functionproblem_v4 += (0.5 * lpSum(chosen[i] * df[‘revenue’].values[i] / df[‘revenue’].sum()for i in segments)+ 0.5 * lpSum(chosen[i] * df[‘users’].values[i] / df[‘users’].sum()for i in segments))
# constraintsproblem_v4 += lpSum(chosen[i] * df[‘marketing_spending’].values[i]for i in segments) <= 30 * 10**6
# run the optimisationproblem_v4.clear up()df[‘selected’] = record(map(lambda x: x.worth(), chosen.values()))
We obtained the optimum goal operate worth of 0.6131, with income at $104.36M and 136.37K new customers.
That’s it! We’ve realized the way to use integer programming to unravel varied optimisation issues.
You will discover the complete code on GitHub.
On this article, we explored completely different strategies for fixing the knapsack drawback and its analogues in product analytics.
We started with a brute-force strategy however rapidly realized it might take an unreasonable period of time.Subsequent, we tried utilizing frequent sense by naively deciding on the top-performing segments, however this strategy yielded incorrect outcomes.Lastly, we turned to Integer Programming, studying the way to translate our product duties into optimization fashions and clear up them successfully.
With this, I hope you’ve gained one other helpful analytical instrument in your toolkit.
Thank you a large number for studying this text. I hope this text was insightful for you. If in case you have any follow-up questions or feedback, please go away them within the feedback part.
All the photographs are produced by the creator until in any other case acknowledged.
[ad_2]
Source link
