Framing and solving your own Optimization problems
Whenever we talk about ML systems, we generally like to think about the common use cases such as:
e-commerce products, movies, songs, friends, followers etc.
user will click an ad or not, sentiment analysis, post is offensive or not etc.
ETA estimation, surge price prediction, house price prediction etc.
- Sequence Modelling
stock price prediction, entity extraction, language modelling etc.
The core of any ML problem is the Loss Function and the Optimization Problem.
Almost every Data Scientist/ML Engineer is familiar with the following Loss Functions used by different ML algorithms:
- RMSE (Linear Regression)
- Logistic Loss (Logistic Regression)
- Binary & Categorical Cross Entropy (Neural Networks)
- Contrastive Loss, Triplet Loss (Ranking, Siamese Networks)
… and so on.
Most ML problems can be formulated in terms of the above loss functions. But it becomes a bit interesting when we are not able to fit a problem into one of these loss functions.
Most often these problems are Constrained Optimization problems (although SVM is also a constrained optimization problem)
Let’s look at some day-to-day problems and try to formulate ML (as well as non-ML) approaches for solving these.
Problem 1: Choosing your own IPL Fantasy League team
- Your team consists of 11 players.
- Each player has some price tag denoted by p(i) for player i. In order to include a player in your team, you have to pay an amount equal to that price tag.
- Each player has some “value” to you denoted by v(i) for player i.
- You only have a limited budget to work with denoted by W.
- Assume that these are virtual players and a single virtual player can be added by multiple teams.
- There are 4 types of players: Batsman, Bowler, All-Rounder and Wicket Keeper.
- Your team should consists of one Wicket Keeper, at-least 2 Batsmen, at-least 2 Bowlers, and at-least one All-Rounder.
The goal is to maximize the total “value” obeying all the constraints.
If we try solving this problem using a dynamic programming approach similar to the Knapsack Problem, we see that the additional constraints on the exact number of players and the minimum number of player types in the team makes this NP-Hard.
On the contrary if we take a Greedy approach i.e. select the players with the highest values, then there is no guarantee that total price for the 11 players is at-most W.
Can we try to fit this problem into a classification problem ? For e.g. if we build a classification model that predicts whether I should select a player or not i.e. a label of 0 or 1.
- Select the minimum number of Batsmen, Bowlers, All Rounders, WK from the highest values for each type with predicted label of 1.
- Select the remaining players with the highest values with label of 1.
The problem here is that it also does not guarantee that total price for the 11 players is at-most W. Another problem here is that it assumes we have training data for training the model.
Let’s see how we can solve this NP-hard problem using the brute force approach first:
The array ‘assigned’ is a boolean array where assigned[i]=1 denotes that we select the i-th player. For each of the 11 positions, we choose from one of the unassigned players and recursively compute the cost.
Time complexity is exponential. For a total of N players and a selection of M players at a total price of W, worst case complexity is O(N^M*M*W).
Let’s assume that Ai denotes the i-th batsman, Bi the i-th bowler, Ci the i-th all rounder and Di the i-th wicket keeper.
Also lets assumes that ai=1 if we select the i-th batsman else 0. Similarly bi, ci and di for the other 3 types of players.
Then our optimization function is:
X = a1*v(A1) + a2*v(A2) + … + b1*v(B1) + b2*v(B2) + … + c1*v(C1) + … + d1*v(D1) + … and so on.
Our goal is to maximize X.
But we also have the following constraints:
- a1+a2+…+b1+b2+….c1+c2+…d1+d2+… = 11
- a1*p(A1) + a2*p(A2) + … + b1*p(B1) + b2*p(B2) + … + c1*p(C1) + … + d1*p(D1) + … ≤ W
- a1+a2+…ak ≥ 2
- b1+b2+…bl ≥ 2
- c1+c2+…cm ≥ 1
- d1+d2+…dn = 1
This is a linear optimization problem which can be solved using the PULP library in Python.
This approach is much faster as compared to the above brute force.
The values of each player comes from historical data. For e.g. we can take v(Ai) to be the runs scored, v(Bi) to be the number of wickets taken and so on.
Problem 2: Allocating discount coupons
Often we need to provide discount coupons to our customers to prevent them from churning. Given that we have only a limited budget for our coupons, we can distribute those to only a selected few, high value customers.
- We have N coupons to distribute among M customers (N << M)
- Each coupon has some discount price on purchase denoted by p(i) for the i-th coupon
- Each customer j has some “value” to the company denoted by v(j).
- Total budget for discount coupons is W.
- Each customer can be given at-most one coupon.
- Each coupon should be given to at-most one customer.
Let h_ij = 1 if the i-th coupon is given to the j-th customer else 0, then the total value is:
X = h_11*v(1)+h_12*v(2)+…+h1m*v(m)+h_21*v(1)+h_22*v(2)+…+h_nm*v(m)
Our goal is to maximize the total value X under the following constraints:
- h_11*p(1)+h_12*p(1)+…+h1m*p(1)+h_21*p(2)+p_22*p(2)+…+h_nm*p(n) ≤ W
- h_i1+h_i2+…+h_im ≤ 1 for all i=1 to n (each coupon given to at-most one customer)
- h_1j+h_2j+….+h_nj ≤ 1 for all j=1 to m (each customer gets at-most one coupon)
The values v(i) can be computed using the total money spent by the i-th customer on our platform.
Python solution implementation using the PULP library:
Problem 3: Matching delivery guys to orders
Food delivery companies employs delivery executives to pickup and deliver orders to addresses. A critical decision to make is which delivery executive to assign to an order.
- There are N orders and M executives available.
- There is a cost to assign an order i to an executive j denoted as C_ij
- Each order should be allocated to only one executive
- All orders should be assigned.
- Each executive is assigned at-most 2 orders.
Let h_ij = 1 if the i-th order is assigned to the j-th executive else 0, then the total cost is:
X = h_11*C_11+h_12*C_12+…+h1m*C_1m+h_21*C_21+h_22*C_22+…+h_nm*C_nm
Our goal is to minimize the total cost X under the following constraints:
- h_i1+h_i2+…+h_im = 1 for all i=1 to n (each order should be allocated to only one executive)
- h_1j+h_2j+…+h_nj ≤ 2 for all j= 1 to m (each executive is assigned at-most 2 orders)
The costs C_ij can be computed based on multiple factors such as:
- Distance of executive from restaurant
- Rating of executive
- Current traffic estimates such as time taken for travel.
Before solving the above linear optimization problem, we will look at 2 other approaches for solving the same problem:
- Brute Force Recursion
- Min-Cost Max-Flow Algorithm.
Approach 1: Brute Force
We allocate an array ‘executives’ with each element 2 i.e. maximum orders supported by the i-th executives.
Since each index can have 3 possible values 0, 1 and 2. The worst case complexity is O(N*M*3^M) where N is number of orders and M is number of executives.
We can optimize the algorithm according to whether N > M or N < M and so on but the worst case complexity would still be exponential in either N or M.
Approach 2: Min Cost Max Flow Algorithm
Basically we modify the Ford Fulkerson Max Flow algorithm to find the augmenting path with the minimum cost everytime (using Bellman Ford algorithm).
Djikstra algorithm will not work here as reverse edges have negative cost.
To handle the constraints on number of orders an executive can deliver we add a maximum flow of 2 from the executive nodes to the sink node.
Let n = max(N, M)*2+2 be the number of vertices and m = O(n²) be the number of edges in the above graph.
Time complexity is O(n²m²) or O(n⁶) which is still polynomial in N or M.
Approach 3: Linear Programming
Using the PULP library in Python
Problem 4: Pricing seats on an aircraft
One of the biggest challenges in the demand-supply market is to correctly pricing your resources so as to maximize your revenue. A bit off here and there can adversely affect your revenues.
One such demand-supply market is the airline seating. Since the demand for a window or aisle seat outnumbers that of the middle seat. Also demand for the seats near to either entry is more than the middle rows.
- There are total 180 seats in a plane.
- There are 30 rows of 6 seats each. 6 seats are further divided into 3 seats to the left and 3 seats to the right of the aisle.
- There are 9 types of seats — window(rows 1–10), window(rows 11–20), window(rows 21–30), aisle(rows 1–10), aisle(rows 11–20), aisle(rows 21–30), middle(rows 1–10), middle(rows 11–20), middle(rows 21–30)
- We want to find 9 different prices corresponding to each type.
- Each seat type has a demand function associated with it denoted by d_j(p) where j is the seat type and it is a function of price p.
- Each seat type has an upper bound price of Qj.
- Prices of the window seats and aisle seats are greater than prices of the middle seats.
- Prices of the rows 1–10 and 21–30 are greater than prices of the rows 11–20.
Let p_j be the price of the j-th seat type, then the total revenue is:
Our goal is the maximize the total revenue X under the following constraints. Note that d_j(p_j) are not constants but are functions of p_j. Assuming a simple linear form for the function i.e.
d_j(p) = a_j + b_j*p
where a_j and b_j are constants learnt from the historical data using least square regression. Generally b_j < 0 because with increasing price, demand decreases and vice versa.
Our objective X is non-linear (quadratic) in p: (a_j*p_j + b_j*p²_j).
- 0 ≤ p_j ≤ Qj for j = 1 to 9 to handle the maximum seat price constraint.
- Demands are positive quantities i.e. a_j + b_j*p_j ≥ 0, for j = 1 to 9
- p_1 ≥ p_2, p_3 ≥ p_2, p_5 ≥ p_4, p_6 ≥ p_4, p_7 ≥ p_8 and p_9 ≥ p_8 (prices of the rows 1–10 and 21–30 are greater than prices of the rows 11–20)
- p_j ≥ p_k for j=1 to 6 and k=7 to 9 (prices of the window seats and aisle seats are greater than prices of the middle seats).
We are going to use NLOPT package in python to solve as follows (since it is a non-linear optimization):
We are setting b_j=-2 constant for all demand functions. But this would be determined from the linear regression model for price vs. demand.
Maximum price set is 500.
Problem 5: Allocating tasks to developers in a Sprint
During sprint planning at most software companies, engineering managers creates tasks to be completed in the current sprint. The goal is to assign tasks to developers in an optimal way:
- There are N tasks and M developers (N > M).
- Each task has a “satisfaction level” in the range 1 to 5 to a developer, denoted by S_ij for task i and developer j.
- Each task has some story points associated with it, denoted by p(i).
- Each developer should be assigned roughly equal number of story points.
- Each task should be allocated to only a single developer.
- A developer can be allocated multiple tasks.
- All tasks should be allocated.
Let h_ij = 1 if the i-th task is allocated to the j-th developer else 0, then the total satisfaction is:
X = h_11*S_11+h_12*S_12+…+h1m*S_1m+h_21*S_21+h_22*S_22+…+h_nm*S_nm
Our goal is to maximize the total satisfaction under the following constraints.
- h_i1+h_i2+…+h_im = 1 for all i=1 to n (all tasks should be assigned)
How to handle the constraint with the story points since it is not possible to define what “roughly equal” means. If we define strict equality or criteria on maximum variance then it would likely be that it is not possible to allocate the tasks at all.
One thing we can do is to add a loss term to X to handle the variance.
Let c = p(1)+p(2)+…p(n)/m (the average number story points allocated per developer).
Y = (h_11*p(1)+h_21*p(2)+…+h_n1*p(n)-c)² + (h_12*p(1)+h_22*p(2)+…+h_n2*p(n)-c)² + … + (h_1m*p(1)+h_2m*p(2)+…+h_nm*p(n)-c)²
X = h_11*S_11+h_12*S_12+…+h1m*S_1m+h_21*S_21+h_22*S_22+…+h_nm*S_nm — Y
h_1j*p(1)+h_2j*p(2)+…+h_nj*p(n) is the total story points allocated to developer j and (h_1j*p(1)+h_2j*p(2)+…+h_nj*p(n)-c)² is the difference from the average story points.
we add a negative sign before Y in the cost function X because we are maximizing X and Y should be minimized.
We cannot solve this problem with PULP because we have non-linear terms in the objective. We can use NLOPT library but the library does not deal with binary indicator variables.
One workaround is to constrain the indicator variables between 0 and 1 and then when value is < 0.5 we can consider 0 else 1. But this is not optimal and could be way off than the true optimal value.
- Minimum-cost flow — Algorithms for Competitive Programming (cp-algorithms.com)