[teaser] optimal eating
![[teaser] optimal eating](https://images.unsplash.com/photo-1546069901-ba9599a7e63c?crop=entropy&cs=tinysrgb&fit=max&fm=jpg&ixid=M3wxMTc3M3wwfDF8c2VhcmNofDJ8fGZvb2R8ZW58MHx8fHwxNjg4NzQwMTk2fDA&ixlib=rb-4.0.3&q=80&w=960)
Linear Programming, Simplex-ly Fantastic
Friends, i.e., you the reader, of a mutual friend, i.e, Tate,
My name is Casey, and I have been given the honor, nay, the privilege of being a guest writer. Tate and I got to share a fun applied mathematical adventure, and I am here to provide some historical background to this minor mathematical escapade.
What do Domino's drivers, MLB baseball teams, Delta Air Lines, the U.S. military and traveling salesmen all have in common? They all benefit from a branch of mathematical optimization known as linear programming. Linear programs (LPs) are optimization models which are commonplace in our lives. They play crucial roles in solving scheduling, logistics, and even culinary problems; we shall return to the last one shortly. Sure, unless you specialize in mathematical optimization, you might be unaware of the constant solving of LPs occurring in the background of your life, like when your flight to Texas is scheduled or your pizza is delivered, but, rest assured, they are being solved.
Mathematical optimization at its essence is the science of best, and mathematical optimizers, such as myself, work to develop algorithms and theory to determine what is best, is best achievable, and how difficult is best to locate. LPs are a special class of problems with many important applications, as mentioned above, and they have a special history that revolves around how they are solved.
The first method to solve LPs was the simplex method, arguably the greatest algorithm of the last hundred years. This might sound like a dogmatic, brash and hastily made claim, but, trust me, I am almost a doctor…of mathematics…and I am joined by a large contingent of individuals who are of a like mind. The simplex method was developed in 1947 by George Dantzig, one of my favorite mathematicians. Born 1914, died 2005, he was “The Father of Linear Programming”, and one of the best classroom stories of all-time comes from his life. I let Dantzig tell the story in his own words.
During my first year at Berkeley, I arrived late one day to one of Neyman's classes. On the blackboard were two problems which I assumed had been assigned for homework. I copied them down. A few days later, I apologized to Neyman for taking so long to do the homework—the problems seemed to be a little harder to do than usual. I asked him if he still wanted the work. He told me to throw it on his desk. I did so reluctantly because his desk was covered with such a heap of papers that I feared my homework would be lost there forever.
About six weeks later, one Sunday morning about eight o'clock, Anne and I were awakened by someone banging on our front door. It was Neyman. He rushed in with papers in hand, all excited: “I've just written an introduction to one of your papers. Read it so I can send it out right away for publication.” For a minute, I had no idea what he was talking about. To make a long story short, the problems on the blackboard which I had solved thinking they were homework were in fact two famous unsolved problems in statistics. That was the first inkling I had that there was anything special about them.
One of the problems Dantzig solved that day, thinking he was late to class, led him to develop the simplex method. This algorithm is still a leading solver of LPs with few competitors. Actually, it took nearly 40 years before a method was devised which could compete with the method. The simplex algorithm has been improved over the last 75 years, but the core ideas remain Dantzig’s.
Why did Dantzig develop the algorithm? Well, Dantzig developed the simplex method to solve problems for the U.S. Air Force during World War II such as planning, scheduling, resource allocation tasks. One of the first applications of the simplex method, the application which gave rise to this blog post, was the problem of eating at minimum cost. Imagine trying to feed thousands of soldiers so that their nutritional requirements are satisfied and you want to do this as cheaply as possible. Simply speaking, this is the diet problem: minimize the cost of food per day such that all dietary needs are satisfied. If you think this sounds near impossible, I understand, but it is possible, it has been done, and it has been done with the simplex method. Dantzig himself tested the simplex method on his own diet with a database of 50 foods in 1947. A short history of the diet problem can be found in a recent 2018 article.
It is amazing Dantzig was able to solve the diet problem, and 50 foods would have been large back then given the lack of computing power available. Today, we can solve diet problems with hundreds of thousands of food options, and we can do so without hundreds of man-hours of computation. Remember, back in the 40s man-hours was an appropriate unit of measure for computing tasks. Today, we can eat our cake and let our laptop do all the work solving our diet problem, which will tell us cake is too expensive and is of limited nutritional benefit and therefore should not be included in our diet. Well, just shut your laptop before the code finishes running and make sure you do it fast; the code won’t run long. You could also place a minimum on the number of servings of cake per day, say 0.5 servings per day, but I will let Tate tell you about that fun feature.
This gives you a sample of the power of LPs, and we did not even have time to talk about the ins and outs of the simplex method and its elegant geometric interpretation and insane efficiency. Well, I guess I will have to save my fun figures and analogies of ants walking around on dodecahedrons for a later date. Maybe Tate will let me write another short piece which is less historical and more about the math of the simplex method, but, hey, I will let him optimize his blog.
I hope you enjoyed this guest post by Casey! Look forward to the next installment of Optimal Eating!