This week’s blogger is Shefali Kulkarni-Thaker, a graduate student working at morLab and is one of the moderators for this blog. You can write to her at shefali [at] mie [dot] utoronto [dot] ca.
Operations Research (OR) traces its roots around world war II and started out with the necessity to win the war. One of the first applications of OR was predicting the location of German submarines. Since then OR has evolved and is practically applicable to any field that is seeking for the “best” in a given situation. It could the least risky investment or the highest return value investment. OR has plenty of applications ranging from airline scheduling to farming. A typical OR problem will try to minimize or maximize a function under some constraints. It will try to answer question like: What is the best way to allocate operation theatres ? As you can imagine this has several dependencies like availability of surgeons, probability of ad-hoc surgeries, time required for a single surgery, patient priority etc.
Linear programming (LP) is an OR technique which solves an OR-problem with linear objective and constraints. LP is the most well defined optimization technique known to the OR-community. Most OR-specialists will try to reformulate their problem into LP if they can. Any LP course in undergraduate or graduate-level will start with the classic diet problem. Solving this problem will help you choose portions of food products that satisfy the %DV of desired nutrients while minimizing the purchase cost. The diet problem, as we know it is the very first documented OR-problem and makes a thematic start to this blog.
The diet problem is only the first documented OR problem but not the very first application. It was in 1939 that Russian mathematician Leonid Kantorovich first thought of an application of linear programming (LP) while working as consultant for the Laboratory of the Plywood Trust. The problem was of “distributing initial raw materials in order to maximize equipment productivity under certain restrictions”. It is also believed that he helped the Russian military to maximize enemy losses during the second world war. Unfortunately his work remained unnoticed for a long time.
At the same time, here in the west, George Stigler sought out to answer the question: what is the cheapest possible diet that would meet the recommended dietary allowances of nine nutrients as given by the National Research Council? The objective in this problem is to minimize the cost of the foods while constraints would meet the dietary requirements for nutrients like fat, carbohydrates, calories, minerals, vitamins, cholesterol etc. Using heuristics, Stigler came up with the approximate solution of 0.11$/day or 39.93 $/year (1939 dollar value). Eventually we will find that his solution was only few cents off.
Incidently, both Kantorovich and Stigler would win the Nobel Prize for their contribution to Economic Sciences.
Almost a decade later in 1947, George Dantzig, an American mathemetician, independently published the simplex method which would eventually become one of the top ten algorithms of twentienth century. Using this newly published method, nine clerks, and 120 man hours Jack Laderman from Mathematical Tables Project of the National Bureau of Standards solved the same problem, as a test of Dantzig’s Simplex, with an optimum cost of 39.69 $/year. Laderman listed the same 77 foods (decision variables) and 9 nutrients(equations) and handed in 8 or 9 columns to each of the clerks. It was the first large-scale optimization problem ever solved thereby beginning the saga of Operations Research.
In early 1950s, George Dantzig went on to use this model to lose weight. This time instead of minimizing the cost, Dantzig sought to maximize the feeling of fullness – weight of the food minus the weight of water content in that food. Unfortunately, the initial solution required Dantzig to consume 500 gallons of vinegar. He found that the listed vinegar had zero content water and declared that vinegar was not a food. He solved the model again only to determine that he needed to eat 200 bouillon cubes per day. With the new solution and the hopes of losing weight, Dantzig tried 4 cubes for breakfast and could not deal with the saltiness. He decided to not try more than three of these cubes on a given day. And for the first time bounds were introduced on variables in the model. The new diet called for eating two pounds of bran but his wife disagreed and Dantzig placed an upper bound on bran. Eventually, Dantzig just decided to go with what his wife had to offer and lost 22 pounds!
If you have a spicy palate like me, you are probably not going to like Stigler’s solution. With the knowledge of OR, availability of tools and technologies and information at our disposal we can come up with a customised diet in few minutes. If, like every other year, your new year’s resolution is to lose those extra pounds it is time that you give LP a chance. You can find the database of nutrients from Nutrient Data Laboratory and use NEOS to solve it. Feel free to leave a comment whether or not you come up with a palatable diet.
Interesting reads:
Who was George Dantzig?
Dantzig, George
The Diet Problem
Kantorovich