How To Use Linear Programming In Your Next Data Science Project

As any beginner to data science knows, the field is full of complex problems. Complexity adds a lot more steps to any procedure, and this adds up exponentially when AI workloads are considered. Complexity is the bane of any data scientist's existence and throws a spanner in the works of many models and workflows. The lesser the number of 'moving parts' in the equation, the easier it is to debug and backpropagation through errors. One of the easiest ways to remove complexity from a problem is linear programming. While it is generally considered a difficult field to enter, a few rules of thumb allow for easy problem optimizations using LP.

What Is Linear Programming?

LP is a type of optimisation widely used in mathematics as a method to reduce complex problems into easier depictions. It is important to note that this is a simplification method and depends on equations, variables and value to allow for clarity in problem-solving. LP has been applied in a multitude of fields apart from data science and can be applied wherever a complex problem needs to be simplified. These include manufacturing (assigning labour to tasks), logistics (optimizing resources for delivery), and business operations (determining new business strategies). Linear programming mainly depends on the problem containing 3 factors, namely:

• All the relationships meant for simplification have to be linear.
• The values have to be subject to a constraint, either in number or in properties.
• The solution of the problem is to maximize the quantity of a given variable.

These factors define a linear programming problem and can help reduce any problem to its most basic components. An LPP can be formulated by following some basic steps.

• Identifying the variables
• Identifying the function of the problem
• Mentioning the constraints
• Stating the non-negativity property

Linear Programming Problem Example

Take the example of a furniture dealer who has the capability to make both chairs and tables. To make a table, it costs 2500 and to make a chair it costs him 500. His profit on them is 250 and 75 respectively. The caveat here is that he can only spend 50,000 and can only store 60 pieces at one time. In LPP, this can be represented as: Let x and y be the number of tables and chairs respectively. Let Z be the profit that has to be maximized. The total cost of manufacturing the tables and chairs must not exceed 50,000. This is our first constraint. 2500x + 500y < 50,000 Upon solving for this inequality, we get: 5x + y ≤ 100 We must also consider that he can only store 60 pieces at a time. This is our second constraint. This can be expressed as: x + y < 60 An assumption we have to make is that both x and y are greater than 0, as the dealer cannot simply buy no chairs. This can be represented as: x,y > 0 The variable to solve for here is profit, represented as Z. The profit is represented by the profit on each piece of furniture, multiplied by the number of pieces. This comes up to: Max. Z = 250x + 75y How does one go about solving these equations?

• 2500x + 500y < 50,000
• 5x + y ≤ 100
• x + y < 60
• Max. Z = 250x + 75y
• x,y > 0

We will discuss two methods to solve this. The first is the graphical method. After plotting the points on the graph, it is visible that the optimal solution lies in OABC. The blue shaded area contains the solution to the problem but still does not provide a single value. This area contains the optimal solution, with x and y values on the graph representing possible values of the solution. Here, it is visually apparent that point B provides the best solution to the problem, with the equation being: Max. Z = 25010 + 7550 = 6250. In another method, we can introduce slack variables to account for the inequality. This would make the equations

• 2500x + 500y + S1 = 50,000
• 5x + y + S2 = 100
• x + y + S3 = 60
• Max. Z = 250x + 75y

Solving for these equations using simultaneous equations method reveals the values for x and y are 10 and 50 respectively. This also falls in line with the result obtained using the graph method. This approach can be used to simplify many problems that commonly occur in data science settings. Using LPP allows for the simplification of the methodology required for this and will ensure a seamless result.