Basic Linear Programming in Python with PuLP
Tags: programming, python, tutorial, codenewbie
Published: 2021-04-05 04:22:48

<!-- wp:heading {"level":4} -->
<h4>PuLP is a python library which can be used to solve linear programming problems. Linear Programming is used to solve optimization problems and has uses in various industries such as Manufacturing, Transportation, Food Diets&nbsp;etc</h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>A basic Linear Programming problem is where we are given multiple equations. The value of one of the equations has to be maximized or minimized while the other equations are constraints. In high school, we used to plot the equations on a graph, shade the feasible region and find the value of the equation to be maximized or minimized by substituting the variables with the verticle values of the shaded region. I briefly go over this technique in the first part of the tutorial</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>I will be dividing the tutorial into two parts</p>
<!-- /wp:paragraph -->

<!-- wp:list -->
<ul><li>A brief overview of Linear Programming</li><li>Using PuLP to solve an optimization problem</li></ul>
<!-- /wp:list -->

<!-- wp:heading {"level":4} -->
<h4>Linear Programming</h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>Linear Programming is used to solve Optimization problems given a few constraints. An example problem is below:</p>
<!-- /wp:paragraph -->

<!-- wp:list -->
<ul><li>We have two models of a car, Car A and Car B.</li><li>Car A gives us a profit of 20k and Car B gives us a profit of 45k</li><li>The Designer takes 4 days to build Car A and 5 days to build Car B</li><li>The Engineer takes 3 days to build Car A and 6 days to build Car B</li><li>The Machine takes 2 days to build Car A and 7 days to build Car B</li><li>The Designer, Engineer and Machine can all work for 30 days</li></ul>
<!-- /wp:list -->

<!-- wp:quote -->
<blockquote class="wp-block-quote"><p>Getting High School Flashbacks?</p></blockquote>
<!-- /wp:quote -->

<!-- wp:paragraph -->
<p>We need to maximize our Profits 💵 💵</p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>The first point gives us our <strong>decision variables. T</strong>he following point gives us our <strong>Objective Function </strong>which we need to maximize and the rest of the points give us our <strong>constraints.</strong></p>
<!-- /wp:paragraph -->

<!-- wp:paragraph -->
<p>One way to solve it is to plot the equations on a graph, find the feasible area and then plug in the value of the vertices.</p>
<!-- /wp:paragraph -->

<!-- wp:image {"align":"center"} -->
<div class="wp-block-image"><figure class="aligncenter"><img src="https://cdn-images-1.medium.com/max/1200/1*fxmqXkB7kjeG6HEZ2OryxA.png" alt=""/><figcaption>Objective Function</figcaption></figure></div>
<!-- /wp:image -->

<!-- wp:image {"align":"center"} -->
<div class="wp-block-image"><figure class="aligncenter"><img src="https://cdn-images-1.medium.com/max/1200/1*ZkBqffRM9qZRTLKCt_JIsg.png" alt=""/><figcaption>Constraint 1</figcaption></figure></div>
<!-- /wp:image -->

<!-- wp:image {"align":"center"} -->
<div class="wp-block-image"><figure class="aligncenter"><img src="https://cdn-images-1.medium.com/max/1200/1*Eh3Yl6PDH8WshSNiVSEU4Q.png" alt=""/><figcaption>Constraint 2</figcaption></figure></div>
<!-- /wp:image -->

<!-- wp:image {"align":"center"} -->
<div class="wp-block-image"><figure class="aligncenter"><img src="https://cdn-images-1.medium.com/max/1200/1*LjnHqf-GqZS0yI4-as21ng.png" alt=""/><figcaption>Constraint 3</figcaption></figure></div>
<!-- /wp:image -->

<!-- wp:image {"align":"center"} -->
<div class="wp-block-image"><figure class="aligncenter"><img src="https://cdn-images-1.medium.com/max/1200/1*8Anp996ocm0hKP01KMzgjA.png" alt=""/><figcaption>Constraint 4</figcaption></figure></div>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p>Below is the feasible region shaded in green. The vertices are not necessarily integers and since we can not make cars in fractions, we can only accept integer solutions.</p>
<!-- /wp:paragraph -->

<!-- wp:image {"align":"center"} -->
<div class="wp-block-image"><figure class="aligncenter"><img src="https://cdn-images-1.medium.com/max/1200/1*YJqyz_9NWvMFC6WZ7eJcow.png" alt=""/><figcaption>Feasible Region</figcaption></figure></div>
<!-- /wp:image -->

<!-- wp:paragraph -->
<p>Finding the integer solutions is not so trivial, we can not round up the vertice values and consider it a solution since we may violate some constraints in doing so. Using PuLP, we will be able to easily find the integral solutions</p>
<!-- /wp:paragraph -->

<!-- wp:heading {"level":3} -->
<h3>PuLP</h3>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>PuLP is an open-source Python library used for Linear Programming. Documentation for the library can be <a href="https://coin-or.github.io/pulp/" rel="noreferrer noopener" target="_blank">found here</a>.</p>
<!-- /wp:paragraph -->

<!-- wp:heading {"level":4} -->
<h4>Install and Import&nbsp;pulp</h4>
<!-- /wp:heading -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted">pip install pulp
from pulp import *</pre>
<!-- /wp:preformatted -->

<!-- wp:heading {"level":4} -->
<h4>Create an Instance of LpProblem</h4>
<!-- /wp:heading -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted">problem = LpProblem('Car Factory', LpMaximize)</pre>
<!-- /wp:preformatted -->

<!-- wp:paragraph -->
<p>The first parameter is the name of our problem and the second parameter is the type of the Problem. We need to maximize our profits, therefore we use LpMaximize</p>
<!-- /wp:paragraph -->

<!-- wp:heading {"level":4} -->
<h4>Create Decision Variables</h4>
<!-- /wp:heading -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted">A = LpVariable('Car A', lowBound=0 , cat=LpInteger)<br>B = LpVariable('Car B', lowBound=0 , cat=LpInteger)</pre>
<!-- /wp:preformatted -->

<!-- wp:paragraph -->
<p>The first parameter is the name of the variable, the second parameter specifies the lower bound and third parameter specifies the type of the variable. The type can also be LpContinuous or LpBinary.</p>
<!-- /wp:paragraph -->

<!-- wp:heading {"level":4} -->
<h4>Objective Function and Constraints</h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>We add the objective function and constraints to the instance of the LpProblem we created earlier.</p>
<!-- /wp:paragraph -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted">#Objective Function<br>problem += 20000*A + 45000*B , 'Objective Function'<br>#Constraints<br>problem += 4*A + 5*B &lt;= 30 , 'Designer Constraint'<br>problem += 3*A + 6*B &lt;=30, 'Engineer Constraint'<br>problem += 2*A + 7*B &lt;=30, 'Machine Constraint</pre>
<!-- /wp:preformatted -->

<!-- wp:paragraph -->
<p>Upon printing the problem variable to the terminal we get the following output</p>
<!-- /wp:paragraph -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted">Car_Profit:
MAXIMIZE
20000*Car_A + 45000*Car_B + 0
SUBJECT TO
Designer_Constraint: 4 Car_A + 5 Car_B &lt;= 30
Engineer_Constraint: 3 Car_A + 6 Car_B &lt;= 30
Machine_Constraint: 2 Car_A + 7 Car_B &lt;= 30
VARIABLES
0 &lt;= Car_A Integer
0 &lt;= Car_B Integer</pre>
<!-- /wp:preformatted -->

<!-- wp:paragraph -->
<p>We can also use the <strong>status</strong> attribute to check the current Status of our problem. It is an integer value and we will need to use LpStatus to map it to a meaningful message</p>
<!-- /wp:paragraph -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted">print("Current Status: ", LpStatus[problem.status])
Current Status:  Not Solved</pre>
<!-- /wp:preformatted -->

<!-- wp:heading {"level":4} -->
<h4>Solve the&nbsp;Problem</h4>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>We will use the solve method to solve the problem.</p>
<!-- /wp:paragraph -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted">problem.solve()<br>print("Number of Car A Made: ", A.varValue)<br>print("Number of Car B Made: ", B.varValue)<br>print("Total Profit: ", value(problem.objective))</pre>
<!-- /wp:preformatted -->

<!-- wp:paragraph -->
<p>The output is the following</p>
<!-- /wp:paragraph -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted">Number of Car A Made:  1.0<br>Number of Car B Made:  4.0<br>Total Profit:  200000.0</pre>
<!-- /wp:preformatted -->

<!-- wp:paragraph -->
<p>If you print the status now, you should get the following output</p>
<!-- /wp:paragraph -->

<!-- wp:preformatted -->
<pre class="wp-block-preformatted">Current Status:  Optimal</pre>
<!-- /wp:preformatted -->

<!-- wp:heading {"level":3} -->
<h3>Conclusion&nbsp;</h3>
<!-- /wp:heading -->

<!-- wp:paragraph -->
<p>In just a few lines of code, we were able to maximize the profits by making more or Car B as compared to Car A. PuLP has many other interesting applications as well. A couple of them are listed below&nbsp;</p>
<!-- /wp:paragraph -->

<!-- wp:list -->
<ul><li><a href="https://coin-or.github.io/pulp/CaseStudies/a_sudoku_problem.html" rel="noreferrer noopener" target="_blank">S</a><a href="https://www.realpythonproject.com/how-to-solve-a-sudoku-puzzle-using-python-and-linear-programming/" target="_blank" rel="noreferrer noopener">udoku Solver</a>: Use Linear Programming to solve the famous Sudoku Puzzles </li><li><a href="https://towardsdatascience.com/linear-programming-and-discrete-optimization-with-python-using-pulp-449f3c5f6e99" rel="noreferrer noopener" target="_blank">Diet Plan</a>: Create a diet plan such that various constraints on calorie and nutrition intake are met while minimizing the cost   </li></ul>
<!-- /wp:list -->

<!-- wp:paragraph -->
<p></p>
<!-- /wp:paragraph -->