Linear Programming Applications in E-Commerce
In this article, you will have a brief idea about linear programming use cases, learn how to transform optimization problems into mathematical form, and solve a real-life e-commerce optimization problem in python using PULP.
Introduction
Linear programming is an optimization method to achieve the best possible output for given constraints. Here, achieving the best possible output means maximizing or minimizing the objective function that is subjected to constraints. As the name suggests, objective function and constraints are represented by linear relationships.
Linear Programming has been applied as a decision-maker in various cases in Agriculture, Logistics, Manufacturing, E-commerce, Finance etc. Some of the most common use cases are resource allocations, asset management and profit maximization.
Real-life problem to mathematical form
The representation of a linear programming problem has shown below:
If we define c = (c₁, …, cₙ) as the coefficients of the objective function,
x = (x₁, …, xₙ) as the variables of the problem, A as a p×n matrix, and
b=(b₁, …, bₚ) as the boundaries for the constraints.
Now we can set our problem as an equation.
maximize Cᵀ x
subject to Ax≤b and x≥0
For example, a printer company has 3 machines. While a printer named x₁ prints 4 pages an hour, x₂ prints 3 pages an hour, and x₃ prints 5. But, somehow the company has a limit on the usage of machines. The company is not allowed to run x₁ and x₂ combined for more than 12 hours in a day. Also, the total number of working hours for x₂ and x₃ can not exceed 16 hours.
If we try to maximize the number of pages printed in a day for given constraints, the canonical form of the problem will be:
maximize
4x₁ + 3x₂ +5x₃
subject to
x₁ + x₂ ≤ 12,
x₂ + x₃ ≤ 16,
x₁ + x₂ + x₃ ≤ 24,
x₁, x₂, x₃ ≥ 0
Linear Programming in e-commerce
Now, let’s dive into a real-world business example. Assume you are working in a marketing team and trying to reach your customers in the most efficient way. There are several ways to do that, but one of the strongest one is investing in a different types of channels. The performance of each channel differs by category. You should allocate your budget considering the data to get an optimum solution with maximum return.
Define the problem
The table below shows the return for each unit of investment by different channels. For example, channel_1 has a return value of 240 in category_1 for one unit of investment. We will define matrix A as the number of average returns for a given channel and category.
A₁₁ = 240, A₁₂ = 120, … , A₅₅ = 180
Now, set X as a 5x5 matrix and each cell represents the allocation for a specific channel and category pair. For example, when we say X₁₁ = 0.05, it means “invest 5% of your total budget for channel_1 and category_1”.
The only terminology that remained undefined is the boundaries for the constraints. Boundaries should be determined on top of the business needs and limits. For example, your company may demand at least 50 return value strategically. So, rather than investing in the channel and category pair that has the most return, sometimes you may want to split your budget according to business needs and interfere your problem by adding rule-based constraints.
Let’s say we want at least 50 return value for each category.
The formulation will be:
Maximize
∑∑ AᵢⱼXᵢⱼ
Subject to
∑ A₁ⱼX₁ⱼ ≥ 50,
∑ A₂ⱼX₂ⱼ ≥ 50,
∑ A₃ⱼX₃ⱼ ≥ 50,
∑A₄ⱼX₄ⱼ ≥ 50,
∑A₅ⱼX₅ⱼ ≥ 50,
∑∑ Xᵢⱼ = 1
Since we represented the problem with objective function and constraints, we are ready to solve it. In this article, we will solve it in python with PULP. PULP is an open-source linear programming package.
Solve it with PULP
- Transform the dataframe into a more useful format.
coef = pd.DataFrame()
cats = coef_prev['category'].values
cols = [col for col in coef_prev.columns if col != 'category']
for cat in cats:
for col in cols:
data = {
'category': cat,
'channel': col,
'coef' : coef_prev[coef_prev['category'] == cat][col].values[0]}
coef = coef.append(data, ignore_index = True)
coef.head(10)
2. Create the LP problem and define variables
#define the linear programming problem
prob = LpProblem("myProblem", LpMaximize)#generate variables
variables = []
for i in range(len(coef)):
var_name = coef['category'][i].replace(" ", "_") + "__" + coef['channel'][i]
lower_bound = 0
upper_bound = 1
#variables.append(LpVariable(var_name))
variables.append(LpVariable(var_name, 0, 1))
3. Create the constraints
#we want at least 50 return value for each category
targets = pd.DataFrame(data = {'category' : ('category_1', 'category_2', 'category_3', 'category_4', 'category_5'), 'target' : (50, 50, 50, 50, 50)})
targets.head()#define constraints
for cat_name in coef['category'].unique():
category_coef = coef[coef['category'] == cat_name]['coef']
var_name = cat_name.replace(" ", "_")category_variables = [var for var in variables if var.name.startswith(var_name)]prob += lpSum(lpDot(category_coef, category_variables)) >= targets[targets['category'] == cat_name]['target']
coef_list = coef['coef'].values
object_fnc = lpDot(coef_list, variables)prob += lpSum(object_fnc)prob += lpSum(variables) <= 1print(prob)
4. Print the final design of the model
myProblem:
MAXIMIZE
240.0 * category_1__channel_1 +
120.0 * category_1__channel_2 +
60.0 * category_1__channel_3 +
100.0*category_1__channel_4 +
170.0*category_1__channel_5 +
50.0*category_2__channel_1 +
90.0*category_2__channel_2 +
80.0*category_2__channel_3 +
450.0*category_2__channel_4 +
200.0*category_2__channel_5 +
200.0*category_3__channel_1 +
180.0*category_3__channel_2 +
130.0*category_3__channel_3 +
80.0*category_3__channel_4 +
20.0*category_3__channel_5 +
80.0*category_4__channel_1 +
80.0*category_4__channel_2 +
400.0*category_4__channel_3 +
50.0*category_4__channel_4 +
180.0*category_4__channel_5 +
180.0*category_5__channel_1 +
280.0*category_5__channel_2 +
80.0*category_5__channel_3 +
70.0*category_5__channel_4 +
180.0*category_5__channel_5 SUBJECT TO
_C1: 240 category_1__channel_1 +
120 category_1__channel_2 +
60 category_1__channel_3 +
100 category_1__channel_4 +
170 category_1__channel_5 >= 50
_C2: 50 category_2__channel_1 +
90 category_2__channel_2 +
80 category_2__channel_3 +
450 category_2__channel_4 +
200 category_2__channel_5 >= 50
_C3: 200 category_3__channel_1 +
180 category_3__channel_2 +
130 category_3__channel_3 +
80 category_3__channel_4 +
20 category_3__channel_5 >= 50
_C4: 80 category_4__channel_1 +
80 category_4__channel_2 +
400 category_4__channel_3 +
50 category_4__channel_4 +
180 category_4__channel_5 >= 50
_C5: 180 category_5__channel_1 +
280 category_5__channel_2 +
80 category_5__channel_3 +
70 category_5__channel_4 +
180 category_5__channel_5 >= 50
_C6: category_1__channel_1 +
category_1__channel_2 +
category_1__channel_3 +
category_1__channel_4 +
category_1__channel_5 +
category_2__channel_1 +
category_2__channel_2 +
category_2__channel_3 +
category_2__channel_4 +
category_2__channel_5 +
category_3__channel_1 +
category_3__channel_2 +
category_3__channel_3 +
category_3__channel_4 +
category_3__channel_5 +
category_4__channel_1 +
category_4__channel_2 +
category_4__channel_3 +
category_4__channel_4 +
category_4__channel_5 +
category_5__channel_1 +
category_5__channel_2 +
category_5__channel_3 +
category_5__channel_4 +
category_5__channel_5 <= 1
5- Solve the problem.
status = prob.solve()print(f'Current status: {LpStatus[prob.status]}')for variable in prob.variables():
print("{} = {}".format(variable.name, variable.varValue))print(f'Solution: {value(prob.objective)}')
Conclusion
Our model achieved the Optimal solution. The maximum return value is calculated as 307 for given constraints. To achieve the optimum solution the allocation of the budget is shown above.
Linear programming helps you to find the optimum solution for the business problem. It is already widely used and applicable in many areas. This article aims to give you only a brief introduction to linear programming but there are lots of sub-topics that contain different techniques which should be carefully selected on top of the business needs and limits. I hope this article helped you to get into the basic concepts of linear programming.
