{"id":149,"date":"2021-01-19T21:31:25","date_gmt":"2021-01-19T21:31:25","guid":{"rendered":"https:\/\/www.kindsonthegenius.com\/data-science\/?p=149"},"modified":"2021-01-20T12:23:02","modified_gmt":"2021-01-20T12:23:02","slug":"the-stigler-diet-linear-programming-problem-in-python","status":"publish","type":"post","link":"https:\/\/www.kindsonthegenius.com\/data-science\/the-stigler-diet-linear-programming-problem-in-python\/","title":{"rendered":"The Stigler Diet Linear Programming Problem in Python"},"content":{"rendered":"<p>The <a href=\"https:\/\/en.wikipedia.org\/wiki\/Stigler_diet\" target=\"_blank\" rel=\"noopener\">Stigler Diet<\/a> problem is similar to <a href=\"https:\/\/www.kindsonthegenius.com\/data-science\/2021\/01\/18\/linear-programming-tutorial-with-python-example\/\" target=\"_blank\" rel=\"noopener\">the diet problem we solved previously<\/a>. The difference is that we now have much more data to work with.<\/p>\n<p>The objective is to determine how many dollar to be spend of each foodstuff at a minimum white satisfying the minimum nutrition requirement. The table below provides the list of foodstuff(commodity) along with their cost per unit and the nutrient content.<\/p>\n<p>For example, Macaroni cost 14.1 cents and contains 418g of Protein, 0.7g of Calcium etc.<\/p>\n<table style=\"width:60%!important;  font-size:12px; height: 305px;\" cellspacing=\"0\", cellpadding=\"0\">\n<thead>\n<tr style=\"font-weight: bold; background-color: #f7f6f3;\">\n<td>Commodity<\/td>\n<td>Units<\/td>\n<td>Price (cents)<\/td>\n<td>Calories<\/td>\n<td>Protein (g)<\/td>\n<td>Calcium (g)<\/td>\n<td>Iron(mg)<\/td>\n<td>vitamin A(IU)<\/td>\n<td>Thiamine (mg)<\/td>\n<td>Riboflavin (mg)<\/td>\n<td>Niacin (mg)<\/td>\n<td>Ascorbic Acid (mg)<\/td>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>Wheat Flour<\/td>\n<td>10 lb.<\/td>\n<td>36<\/td>\n<td>44.7<\/td>\n<td>1411<\/td>\n<td>2<\/td>\n<td>365<\/td>\n<td>0<\/td>\n<td>55.4<\/td>\n<td>33.3<\/td>\n<td>441<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>Macaroni<\/td>\n<td>1 lb.<\/td>\n<td>14.1<\/td>\n<td>11.6<\/td>\n<td>418<\/td>\n<td>0.7<\/td>\n<td>54<\/td>\n<td>0<\/td>\n<td>3.2<\/td>\n<td>1.9<\/td>\n<td>68<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<\/tr>\n<tr>\n<td>Strawberry Preserves<\/td>\n<td>1 lb.<\/td>\n<td>20.5<\/td>\n<td>6.4<\/td>\n<td>11<\/td>\n<td>0.4<\/td>\n<td>7<\/td>\n<td>0.2<\/td>\n<td>0.2<\/td>\n<td>0.4<\/td>\n<td>3<\/td>\n<td>0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>We are also provided with the minimum daily requirements for the 8 nutrients. This is as given in the table below:<\/p>\n<p>&nbsp;<\/p>\n<table style=\"width: 50%;\">\n<thead>\n<tr style=\"background-color: #f7f6f3; font-weight: bold;\">\n<td><b>Nutrient<\/b><\/td>\n<td><b>Minimum daily requirement<\/b><\/td>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>Calories<\/td>\n<td>3,000 Calories<\/td>\n<\/tr>\n<tr>\n<td>Protein<\/td>\n<td>70 grams<\/td>\n<\/tr>\n<tr>\n<td>Calcium<\/td>\n<td>.8 grams<\/td>\n<\/tr>\n<tr>\n<td>Iron<\/td>\n<td>12 mg<\/td>\n<\/tr>\n<tr>\n<td>Vitamin A<\/td>\n<td>5,000 IU<\/td>\n<\/tr>\n<tr>\n<td>Thiamine (Vitamin B1)<\/td>\n<td>1.8 mg<\/td>\n<\/tr>\n<tr>\n<td>Riboflavin (Vitamin B2)<\/td>\n<td>2.7 mg<\/td>\n<\/tr>\n<tr>\n<td>Niacin<\/td>\n<td>18 mg<\/td>\n<\/tr>\n<tr>\n<td>Ascorbic Acid (Vitamin C)<\/td>\n<td>75 mg<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Since the nutrients have all been normalized by the price, the goal is now to minimize the sum of the foods, therefore,<\/p>\n<ul>\n<li>the variables will be the food items (Commodity column of the table)<\/li>\n<li>cost function will be the sum of all the foods, each food with coefficient of 1<\/li>\n<\/ul>\n<p>Note: the code for the above two tables can be found in here. You can also watch the video and see the link in the video description.<\/p>\n<p>&nbsp;<\/p>\n<h4><strong>Create the variables and define the cost function<\/strong><\/h4>\n<p>The code below creates the variables and stores them in a list called food. Then we create the objective function using the variables and assign the coefficient of each variable the value 1<\/p>\n<pre style=\"margin: 0; line-height: 125%;\">food <span style=\"color: #333333;\">=<\/span> [[]] <span style=\"color: #333333;\">*<\/span> <span style=\"color: #007020;\">len<\/span>(data) <span style=\"color: #888888;\"># list to hold the variables<\/span>\r\n\r\nobjective <span style=\"color: #333333;\">=<\/span> solver<span style=\"color: #333333;\">.<\/span>Objective() <span style=\"color: #888888;\"># define the objective<\/span>\r\n<span style=\"color: #008800; font-weight: bold;\">for<\/span> <span style=\"color: #000000; font-weight: bold;\">in<\/span> <span style=\"color: #007020;\">range<\/span>(<span style=\"color: #0000dd; font-weight: bold;\">0<\/span> to <span style=\"color: #007020;\">len<\/span>(data)):\r\n    food[i] <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(), data[i][<span style=\"color: #0000dd; font-weight: bold;\">0<\/span>])\r\n    objective<span style=\"color: #333333;\">.<\/span>SetCoefficient(food[i], <span style=\"color: #0000dd; font-weight: bold;\">1<\/span>)\r\nobjective<span style=\"color: #333333;\">.<\/span>SetMinimization()\r\n\r\n<span style=\"color: #888888;\"># food[i] is the normalized amount to be spent on foodstuff i<\/span>\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<h4><strong>Define the Constraints<\/strong><\/h4>\n<p>The constraints require that the total amount of nutrients provided by all the foods be at least the minimum daily nutrient requirement for each nutrient. The model the constraints, we consider the following:<\/p>\n<p>the amount of nutrient <em>i<\/em> provided by food j per dollar is <em>data[j][i+3]<\/em> (note that it&#8217;s j+3 because the nutrient data begins in the 4th column of the list)<\/p>\n<p>since the amount of to be spent on food j is <em>food[j],<\/em> therefore, the amount of nutrient provided by food j is <em>data[j][i+3] * food[j]<\/em><\/p>\n<p>the total nutrient provided by all the foods is then given by the sum of all the nutrients<\/p>\n<p><a href=\"https:\/\/www.kindsonthegenius.com\/data-science\/wp-content\/uploads\/sites\/12\/2021\/01\/Screenshot-2021-01-19-at-19.18.22.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-156 size-medium aligncenter\" src=\"https:\/\/www.kindsonthegenius.com\/data-science\/wp-content\/uploads\/sites\/12\/2021\/01\/Screenshot-2021-01-19-at-19.18.22-300x75.png\" alt=\"\" width=\"300\" height=\"75\" srcset=\"https:\/\/www.kindsonthegenius.com\/data-science\/wp-content\/uploads\/sites\/12\/2021\/01\/Screenshot-2021-01-19-at-19.18.22-300x75.png 300w, https:\/\/www.kindsonthegenius.com\/data-science\/wp-content\/uploads\/sites\/12\/2021\/01\/Screenshot-2021-01-19-at-19.18.22.png 354w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><\/p>\n<p>we can then write the constraint as<\/p>\n<p><a href=\"https:\/\/www.kindsonthegenius.com\/data-science\/wp-content\/uploads\/sites\/12\/2021\/01\/Screenshot-2021-01-19-at-20.23.04.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-157 size-full aligncenter\" src=\"https:\/\/www.kindsonthegenius.com\/data-science\/wp-content\/uploads\/sites\/12\/2021\/01\/Screenshot-2021-01-19-at-20.23.04.png\" alt=\"\" width=\"589\" height=\"89\" srcset=\"https:\/\/www.kindsonthegenius.com\/data-science\/wp-content\/uploads\/sites\/12\/2021\/01\/Screenshot-2021-01-19-at-20.23.04.png 589w, https:\/\/www.kindsonthegenius.com\/data-science\/wp-content\/uploads\/sites\/12\/2021\/01\/Screenshot-2021-01-19-at-20.23.04-300x45.png 300w\" sizes=\"auto, (max-width: 589px) 100vw, 589px\" \/><\/a><\/p>\n<p>The following code creates the constraints:<\/p>\n<pre style=\"margin: 0; line-height: 125%;\"><span style=\"color: #888888;\"># Setup the constraints<\/span>\r\n\r\nconstraints <span style=\"color: #333333;\">=<\/span> [<span style=\"color: #0000dd; font-weight: bold;\">0<\/span>] <span style=\"color: #333333;\">*<\/span> <span style=\"color: #007020;\">len<\/span>(nutrients) \r\n<span style=\"color: #008800; font-weight: bold;\">for<\/span> i <span style=\"color: #000000; font-weight: bold;\">in<\/span> <span style=\"color: #007020;\">range<\/span>(<span style=\"color: #0000dd; font-weight: bold;\">0<\/span>, <span style=\"color: #007020;\">len<\/span>(nutrients)):\r\n    constraints[i] <span style=\"color: #333333;\">=<\/span> solver<span style=\"color: #333333;\">.<\/span>Constraint(nutrients[i][<span style=\"color: #0000dd; font-weight: bold;\">1<\/span>], solver<span style=\"color: #333333;\">.<\/span>infinity())\r\n    <span style=\"color: #008800; font-weight: bold;\">for<\/span> j <span style=\"color: #000000; font-weight: bold;\">in<\/span> <span style=\"color: #007020;\">range<\/span>(<span style=\"color: #0000dd; font-weight: bold;\">0<\/span>, <span style=\"color: #007020;\">len<\/span>(data)):\r\n        constraints[i]<span style=\"color: #333333;\">.<\/span>SetCoefficient(food[j], data[j][i<span style=\"color: #333333;\">+<\/span><span style=\"color: #0000dd; font-weight: bold;\">3<\/span>])\r\n        \r\n<span style=\"color: #888888;\"># the outer loop i, moves across the columns, creating the constraints<\/span>\r\n<span style=\"color: #888888;\"># the inner loop j, moves down the rows, assigning one coefficient to each constraint<\/span>\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p>The following code calls the solver and displays the values of the solution:<\/p>\n<pre style=\"margin: 0; line-height: 125%;\"><span style=\"color: #888888;\"># Call the solver and print the results<\/span>\r\nstatus <span style=\"color: #333333;\">=<\/span> solver<span style=\"color: #333333;\">.<\/span>Solve()\r\n\r\n<span style=\"color: #008800; font-weight: bold;\">if<\/span> status <span style=\"color: #333333;\">==<\/span> solver<span style=\"color: #333333;\">.<\/span>OPTIMAL:\r\n    price <span style=\"color: #333333;\">=<\/span> <span style=\"color: #0000dd; font-weight: bold;\">0<\/span>\r\n    num_nutrients <span style=\"color: #333333;\">=<\/span> <span style=\"color: #007020;\">len<\/span>(data[i]) <span style=\"color: #333333;\">-<\/span> <span style=\"color: #0000dd; font-weight: bold;\">3<\/span>\r\n    nutrients <span style=\"color: #333333;\">=<\/span> [<span style=\"color: #0000dd; font-weight: bold;\">0<\/span>] <span style=\"color: #333333;\">*<\/span> (<span style=\"color: #007020;\">len<\/span>(data[i]) <span style=\"color: #333333;\">-<\/span> <span style=\"color: #0000dd; font-weight: bold;\">3<\/span>)\r\n    \r\n    <span style=\"color: #888888;\"># loop through the rows of data<\/span>\r\n    <span style=\"color: #008800; font-weight: bold;\">for<\/span> i <span style=\"color: #000000; font-weight: bold;\">in<\/span> <span style=\"color: #007020;\">range<\/span>(<span style=\"color: #0000dd; font-weight: bold;\">0<\/span>, <span style=\"color: #007020;\">len<\/span>(data)):\r\n        price <span style=\"color: #333333;\">+=<\/span> food[i]<span style=\"color: #333333;\">.<\/span>solution_value()\r\n        \r\n        <span style=\"color: #888888;\"># loop through the nutrients<\/span>\r\n        <span style=\"color: #008800; font-weight: bold;\">for<\/span> nutrient <span style=\"color: #000000; font-weight: bold;\">in<\/span> <span style=\"color: #007020;\">range<\/span>(<span style=\"color: #0000dd; font-weight: bold;\">0<\/span>, num_nutrients):\r\n            nutrients[nutrient] <span style=\"color: #333333;\">+=<\/span> data[i][nutrient<span style=\"color: #333333;\">+<\/span><span style=\"color: #0000dd; font-weight: bold;\">3<\/span>] <span style=\"color: #333333;\">*<\/span> food[i]<span style=\"color: #333333;\">.<\/span>solution_value()\r\n        \r\n        <span style=\"color: #888888;\"># print the cost of food if the value is not 0<\/span>\r\n        <span style=\"color: #008800; font-weight: bold;\">if<\/span> food[i]<span style=\"color: #333333;\">.<\/span>solution_value() <span style=\"color: #333333;\">&gt;<\/span> <span style=\"color: #0000dd; font-weight: bold;\">0<\/span>:\r\n            <span style=\"color: #008800; font-weight: bold;\">print<\/span>(<span style=\"background-color: #fff0f0;\">'<\/span><span style=\"background-color: #eeeeee;\">%s<\/span><span style=\"background-color: #fff0f0;\"> = <\/span><span style=\"background-color: #eeeeee;\">%f<\/span><span style=\"background-color: #fff0f0;\">'<\/span> <span style=\"color: #333333;\">%<\/span>(data[i][<span style=\"color: #0000dd; font-weight: bold;\">0<\/span>], food[i]<span style=\"color: #333333;\">.<\/span>solution_value()))\r\n            \r\n    <span style=\"color: #008800; font-weight: bold;\">print<\/span>(<span style=\"background-color: #fff0f0;\">'Optimal yearly price: $<\/span><span style=\"background-color: #eeeeee;\">%.2f<\/span><span style=\"background-color: #fff0f0;\">'<\/span> <span style=\"color: #333333;\">%<\/span>(<span style=\"color: #0000dd; font-weight: bold;\">365<\/span> <span style=\"color: #333333;\">*<\/span> price))\r\n<span style=\"color: #008800; font-weight: bold;\">else<\/span>:\r\n    <span style=\"color: #008800; font-weight: bold;\">if<\/span> status <span style=\"color: #333333;\">==<\/span> solver<span style=\"color: #333333;\">.<\/span>FEASIBLE:\r\n        <span style=\"color: #008800; font-weight: bold;\">print<\/span>(<span style=\"background-color: #fff0f0;\">'A potentially suboptimal solution was found.'<\/span>)\r\n    <span style=\"color: #008800; font-weight: bold;\">else<\/span>:\r\n        <span style=\"color: #008800; font-weight: bold;\">print<\/span>(<span style=\"background-color: #fff0f0;\">'The solver could not find a solution to the problem'<\/span>)\r\n<\/pre>\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>The Stigler Diet problem is similar to the diet problem we solved previously. The difference is that we now have much more data to work &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":[24],"class_list":["post-149","post","type-post","status-publish","format-standard","hentry","category-linear-programming","tag-stigler-diet"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/posts\/149","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=149"}],"version-history":[{"count":12,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/posts\/149\/revisions"}],"predecessor-version":[{"id":173,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/posts\/149\/revisions\/173"}],"wp:attachment":[{"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/media?parent=149"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/categories?post=149"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/data-science\/wp-json\/wp\/v2\/tags?post=149"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}