{"id":10,"date":"2021-01-18T21:55:29","date_gmt":"2021-01-18T21:55:29","guid":{"rendered":"https:\/\/www.kindsonthegenius.com\/data-science\/?p=10"},"modified":"2021-01-18T21:57:49","modified_gmt":"2021-01-18T21:57:49","slug":"linear-programming-tutorial-with-python-example","status":"publish","type":"post","link":"https:\/\/www.kindsonthegenius.com\/data-science\/linear-programming-tutorial-with-python-example\/","title":{"rendered":"Linear Programming Tutorial With Python Example"},"content":{"rendered":"<p>This would be a practical tutorial providing a step by step way to solve a given linear programming program using Python. So normally, you will be expected to find the values of certain variables that would maximize or minimize a function called the cost function (objective function).<\/p>\n<p>Let&#8217;s take a typical example:<\/p>\n<ol>\n<li><a href=\"#t1\">Example &#8211; Simplified Diet Problem<\/a><\/li>\n<li><a href=\"#t2\">Solution Using Python<\/a><\/li>\n<\/ol>\n<p>&nbsp;<\/p>\n<h4><strong id=\"t1\">1. Example &#8211; Simplified Diet Problem<\/strong><\/h4>\n<p>Find the number of units of each category of food that would minimize the total cost of the food but meet the daily nutrient requirements.<\/p>\n<ul>\n<li>The five foods are: Apples, Bananas, Carrots, Dates and Eggs<\/li>\n<li>The nutrients are: Protein, Vitamin C, Iron<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<table style=\"width: 90%;\">\n<thead>\n<tr style=\"font-weight: bold; background-color: #f7f6f3;\">\n<td align=\"center\">Food<\/td>\n<td colspan=\"5\" align=\"center\">Nutrients<\/td>\n<\/tr>\n<tr style=\"font-weight: bold; background-color: #f7f6f3;\">\n<td><\/td>\n<td>Units<\/td>\n<td>Protein<\/td>\n<td>Vitamin C<\/td>\n<td>Iron<\/td>\n<td>Price(cents\/unit)<\/td>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>Apples<\/td>\n<td>1 median<\/td>\n<td>0.4<\/td>\n<td>6<\/td>\n<td>0.4<\/td>\n<td>8<\/td>\n<\/tr>\n<tr>\n<td>Banana<\/td>\n<td>1 median<\/td>\n<td>1.2<\/td>\n<td>10<\/td>\n<td>0.6<\/td>\n<td>10<\/td>\n<\/tr>\n<tr>\n<td>Carrots<\/td>\n<td>1 median<\/td>\n<td>0.6<\/td>\n<td>3<\/td>\n<td>0.4<\/td>\n<td>3<\/td>\n<\/tr>\n<tr>\n<td>Dates<\/td>\n<td>1\/2 cup<\/td>\n<td>0.6<\/td>\n<td>1<\/td>\n<td>0.2<\/td>\n<td>20<\/td>\n<\/tr>\n<tr>\n<td>Eggs<\/td>\n<td>2 median<\/td>\n<td>12.2<\/td>\n<td>0<\/td>\n<td>2.6<\/td>\n<td>15<\/td>\n<\/tr>\n<tr style=\"font-weight: bold;\">\n<td>Min. Daily Req.<\/td>\n<td><\/td>\n<td>70<\/td>\n<td>50<\/td>\n<td>12<\/td>\n<td><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>According to <a href=\"https:\/\/www.youtube.com\/watch?v=x5QOSXhvM5U&amp;t=322s\" target=\"_blank\" rel=\"noopener\">Kindson in this video<\/a>, to be to model this problem you need to determine 4 things, namely:<\/p>\n<ol>\n<li>the variables<\/li>\n<li>the goal of the problem (either minimization or maximization)<\/li>\n<li>the cost function<\/li>\n<li>the constraints<\/li>\n<\/ol>\n<p>So let&#8217;s determine these things:<\/p>\n<p><strong>the variables (or unknowns)<\/strong><\/p>\n<p>Since we need to find quantity of each food, we can represent the variables as the first letter of each food. So let&#8217;s call them <em>A, B, C, D, E<\/em><\/p>\n<p><strong>the goal of the problem (either minimization or maximization)<\/strong><\/p>\n<p>This is clearly indicated in the problem we want to minimize the cost. Therefor the goal is <em>minimization<\/em><\/p>\n<p><strong>the cost function<\/strong><\/p>\n<p>Since we know the variables, the cost function is a function of the variables ie<em> f(A, B, C, D, E). <\/em>Since we know the cost per unit(the last column, we simply multiply each food by the unit cost. Therefore we have<\/p>\n<p><em>f(A, B, C, D, E) = 8A + 10B + 3C + 20D + 15E<\/em><\/p>\n<p><strong>the constraints<\/strong><\/p>\n<p>We are given the minimum daily requirement (the last row), so we multiply the nutrient per unit with the each food and make sure it is greater than or equal to the min. daily requirement. So we have 3 constraints:<\/p>\n<ul>\n<li><em>Protein:\u00a0 \u00a0 \u00a0 \u00a0 0.4A + 1.2B + 0.6C + 0.6D + 12.2E &gt;= 70<\/em><\/li>\n<li><em>Vitamin C:\u00a0 \u00a06A + 10B + 3C + D &gt;= 50<\/em><\/li>\n<li><em>Iron:\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a00.4A + 0.6B + 0.4C + 0.2D + 2.6E &gt;= 12<\/em><\/li>\n<li>A, B, C, D, E &gt;= 0<\/li>\n<\/ul>\n<p>In summary, we are expected to find minimum of f(A, B, C, D, E) subject to the 4 constraints.<\/p>\n<p>&nbsp;<\/p>\n<h4><strong id=\"t2\">2. Solution with Python<\/strong><\/h4>\n<p>We can easily solve this problem in Python following 6 simple steps. Also note that to be able to use the linear_solver, you must have ortools installed (using pip install ortools)<\/p>\n<p>1. import the necessary modules<\/p>\n<p><!-- HTML generated using hilite.me --><\/p>\n<pre style=\"margin: 0; line-height: 125%;\"><span style=\"color: #888888;\"># import modules<\/span>\r\n<span style=\"color: #008800; font-weight: bold;\">from<\/span> <span style=\"color: #0e84b5; font-weight: bold;\">ortools.linear_solver<\/span> <span style=\"color: #008800; font-weight: bold;\">import<\/span> pywraplp\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p>2. declare a linear programming solver<br \/>\n<!-- HTML generated using hilite.me --><\/p>\n<pre style=\"margin: 0; line-height: 125%;\"><span style=\"color: #888888;\"># create solver<\/span>\r\nsolver <span style=\"color: #333333;\">=<\/span> pywraplp<span style=\"color: #333333;\">.<\/span>Solver<span style=\"color: #333333;\">.<\/span>CreateSolver(<span style=\"background-color: #fff0f0;\">'GLOP'<\/span>)\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p>3. create the variables<br \/>\n<!-- HTML generated using hilite.me --><\/p>\n<pre style=\"margin: 0; line-height: 125%;\"><span style=\"color: #888888;\"># Create your variables<\/span>\r\na <span style=\"color: #333333;\">=<\/span> solver<span style=\"color: #333333;\">.<\/span>NumVar(<span style=\"color: #0000dd; font-weight: bold;\">0<\/span>, solver<span style=\"color: #333333;\">.<\/span>infinity(), <span style=\"background-color: #fff0f0;\">'a'<\/span>)\r\nb <span style=\"color: #333333;\">=<\/span> solver<span style=\"color: #333333;\">.<\/span>NumVar(<span style=\"color: #0000dd; font-weight: bold;\">0<\/span>, solver<span style=\"color: #333333;\">.<\/span>infinity(), <span style=\"background-color: #fff0f0;\">'b'<\/span>)\r\nc <span style=\"color: #333333;\">=<\/span> solver<span style=\"color: #333333;\">.<\/span>NumVar(<span style=\"color: #0000dd; font-weight: bold;\">0<\/span>, solver<span style=\"color: #333333;\">.<\/span>infinity(), <span style=\"background-color: #fff0f0;\">'c'<\/span>)\r\nd <span style=\"color: #333333;\">=<\/span> solver<span style=\"color: #333333;\">.<\/span>NumVar(<span style=\"color: #0000dd; font-weight: bold;\">0<\/span>, solver<span style=\"color: #333333;\">.<\/span>infinity(), <span style=\"background-color: #fff0f0;\">'d'<\/span>)\r\ne <span style=\"color: #333333;\">=<\/span> solver<span style=\"color: #333333;\">.<\/span>NumVar(<span style=\"color: #0000dd; font-weight: bold;\">0<\/span>, solver<span style=\"color: #333333;\">.<\/span>infinity(), <span style=\"background-color: #fff0f0;\">'e'<\/span>)\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p>4. define the constraints<br \/>\n<!-- HTML generated using hilite.me --><\/p>\n<pre style=\"margin: 0; line-height: 125%;\"><span style=\"color: #888888;\"># Create your constraints<\/span>\r\nsolver<span style=\"color: #333333;\">.<\/span>Add(<span style=\"color: #6600ee; font-weight: bold;\">0.4<\/span><span style=\"color: #333333;\">*<\/span>a <span style=\"color: #333333;\">+<\/span> <span style=\"color: #6600ee; font-weight: bold;\">1.2<\/span><span style=\"color: #333333;\">*<\/span>b <span style=\"color: #333333;\">+<\/span> <span style=\"color: #6600ee; font-weight: bold;\">0.6<\/span><span style=\"color: #333333;\">*<\/span>c <span style=\"color: #333333;\">+<\/span> <span style=\"color: #6600ee; font-weight: bold;\">0.6<\/span><span style=\"color: #333333;\">*<\/span>d <span style=\"color: #333333;\">+<\/span> <span style=\"color: #6600ee; font-weight: bold;\">12.2<\/span><span style=\"color: #333333;\">*<\/span>e <span style=\"color: #333333;\">&gt;=<\/span> <span style=\"color: #0000dd; font-weight: bold;\">70<\/span>)\r\nsolver<span style=\"color: #333333;\">.<\/span>Add(<span style=\"color: #0000dd; font-weight: bold;\">6<\/span><span style=\"color: #333333;\">*<\/span>a <span style=\"color: #333333;\">+<\/span> <span style=\"color: #0000dd; font-weight: bold;\">10<\/span><span style=\"color: #333333;\">*<\/span>b <span style=\"color: #333333;\">+<\/span> <span style=\"color: #0000dd; font-weight: bold;\">3<\/span><span style=\"color: #333333;\">*<\/span>c <span style=\"color: #333333;\">+<\/span> d <span style=\"color: #333333;\">&gt;=<\/span> <span style=\"color: #0000dd; font-weight: bold;\">50<\/span>)\r\nsolver<span style=\"color: #333333;\">.<\/span>Add(<span style=\"color: #6600ee; font-weight: bold;\">0.4<\/span><span style=\"color: #333333;\">*<\/span>a <span style=\"color: #333333;\">+<\/span> <span style=\"color: #6600ee; font-weight: bold;\">0.6<\/span><span style=\"color: #333333;\">*<\/span>b <span style=\"color: #333333;\">+<\/span> <span style=\"color: #6600ee; font-weight: bold;\">0.4<\/span><span style=\"color: #333333;\">*<\/span>c <span style=\"color: #333333;\">+<\/span> <span style=\"color: #6600ee; font-weight: bold;\">0.2<\/span><span style=\"color: #333333;\">*<\/span>d <span style=\"color: #333333;\">+<\/span> <span style=\"color: #6600ee; font-weight: bold;\">2.6<\/span><span style=\"color: #333333;\">*<\/span>e <span style=\"color: #333333;\">&gt;=<\/span> <span style=\"color: #0000dd; font-weight: bold;\">12<\/span>)\r\n<span style=\"color: #008800; font-weight: bold;\">print<\/span>(<span style=\"background-color: #fff0f0;\">'Constraints ='<\/span>, solver<span style=\"color: #333333;\">.<\/span>NumConstraints())\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p>5. define your cost function (objective function)<br \/>\n<!-- HTML generated using hilite.me --><\/p>\n<pre style=\"margin: 0; line-height: 125%;\"><span style=\"color: #888888;\"># Pass the cost function<\/span>\r\nsolver<span style=\"color: #333333;\">.<\/span>Minimize(<span style=\"color: #0000dd; font-weight: bold;\">8<\/span><span style=\"color: #333333;\">*<\/span>a <span style=\"color: #333333;\">+<\/span> <span style=\"color: #0000dd; font-weight: bold;\">10<\/span><span style=\"color: #333333;\">*<\/span>b <span style=\"color: #333333;\">+<\/span> <span style=\"color: #0000dd; font-weight: bold;\">3<\/span><span style=\"color: #333333;\">*<\/span>c <span style=\"color: #333333;\">+<\/span> <span style=\"color: #0000dd; font-weight: bold;\">20<\/span><span style=\"color: #333333;\">*<\/span>d <span style=\"color: #333333;\">+<\/span> <span style=\"color: #0000dd; font-weight: bold;\">15<\/span><span style=\"color: #333333;\">*<\/span>e)\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p>6. call the solver and print out your results<br \/>\n<!-- HTML generated using hilite.me --><\/p>\n<pre style=\"margin: 0; line-height: 125%;\"><span style=\"color: #888888;\">#Call the Solver<\/span>\r\nsolver<span style=\"color: #333333;\">.<\/span>Solve()\r\n\r\n<span style=\"color: #888888;\"># print out the values<\/span>\r\n<span style=\"color: #008800; font-weight: bold;\">print<\/span>(<span style=\"background-color: #fff0f0;\">'Objective value ='<\/span>, solver<span style=\"color: #333333;\">.<\/span>Objective()<span style=\"color: #333333;\">.<\/span>Value())\r\n<span style=\"color: #008800; font-weight: bold;\">print<\/span>(<span style=\"background-color: #fff0f0;\">'A = '<\/span>, a<span style=\"color: #333333;\">.<\/span>solution_value())\r\n<span style=\"color: #008800; font-weight: bold;\">print<\/span>(<span style=\"background-color: #fff0f0;\">'B = '<\/span>, b<span style=\"color: #333333;\">.<\/span>solution_value())\r\n<span style=\"color: #008800; font-weight: bold;\">print<\/span>(<span style=\"background-color: #fff0f0;\">'C = '<\/span>, c<span style=\"color: #333333;\">.<\/span>solution_value())\r\n<span style=\"color: #008800; font-weight: bold;\">print<\/span>(<span style=\"background-color: #fff0f0;\">'D = '<\/span>, d<span style=\"color: #333333;\">.<\/span>solution_value())\r\n<span style=\"color: #008800; font-weight: bold;\">print<\/span>(<span style=\"background-color: #fff0f0;\">'E = '<\/span>, e<span style=\"color: #333333;\">.<\/span>solution_value())\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p><a href=\"https:\/\/youtu.be\/Es4hNO7C5Lk\" target=\"_blank\" rel=\"noopener\">Watch the Linear Programming Video<\/a><\/p>\n<p>&nbsp;<\/p>\n<!-- AddThis Advanced Settings generic via filter on the_content --><!-- AddThis Share Buttons generic via filter on the_content -->","protected":false},"excerpt":{"rendered":"<p>This would be a practical tutorial providing a step by step way to solve a given linear programming program using Python. So normally, you will &hellip; <!-- AddThis Advanced Settings generic via filter on get_the_excerpt --><!-- AddThis Share Buttons generic via filter on get_the_excerpt --><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-10","post","type-post","status-publish","format-standard","hentry","category-linear-programming"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/posts\/10","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/comments?post=10"}],"version-history":[{"count":5,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/posts\/10\/revisions"}],"predecessor-version":[{"id":15,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/posts\/10\/revisions\/15"}],"wp:attachment":[{"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/media?parent=10"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/categories?post=10"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/tags?post=10"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}