Karmarkar - Revolution in optimization!
by Sean Thomas Grogan and Orestes Gonzalo Manzanilla Salazar
Today companies, institutions and organizations face extremely complex decisions, involving millions of simultaneous and intricate decisions. Companies' profit depends on a multitude of choices such as stocks, production, logistics, transportation, investment, scheduling, staffing, and others. The problem can be more complex when the goals involve taking into consideration complex constraints such as time, risks, quality of service, policies, and rules.
There is a mathematical technique that is called linear programming that is being used in an unthinkable range of places; from the military to the hospitals, from machine learning/pattern recognition to the planning of the rotations of vegetables to crop, from planning the recruitment and training of staff to selecting the best combination of advertisement media for a product.
The first algorithm that made linear programming models something useful, was developed during the World War II, when the military asked some researchers to use mathematics to improve their operations (specifically the distribution of RADAR installations in the UK and search patterns for submarine hunting North Atlantic). It was called SIMPLEX , but in some cases it was not so "simple" - or practical. The computers used in the 1940’s could not solve the problems in a time short enough to be practical. Once the war ended, companies, governments, and other institutions began to make use of the research conducted by the government in WWII. .
But how does the not-so-simple SIMPLEX work? Essentially it can be imagined as a blind person inside of a room with many walls. Where he is standing in the room, represents a particular way to solve the problem (not necessarily the best, where the “best” is the most efficient!). Because of the nature of the mathematical problem, this person knows that the best place in the room (the best solution, or optimum) is known to be a corner. He develops superpowers that he can use when he is in a corner. He can knows which of the adjacent corners is better than the one where he is and he can instantaneously teleport to that corner. When will the blind super-hero finish his job? Easy: when he uses his superpower in one corner, and sees that none of the adjacent corners is better than the one he is at. Then, the place where he is standing can be interpreted and the best combination of the thousands decisions are prescribed to the decision maker.
This was a wonderful tool. But there was a young indian mathematician name Karmarkar saw a flaw . It is a common feeling when we are frantically looking for something and finally find it in the last place we search. Karmarkar proved that this could happen with the not-so-simple SIMPLEX: the blind superhero would have to travel to all the corners, to find the optimum just when he ran out of corners to try. That meant that the linear programming models were difficult to solve for big problems or if certain conditions in a problem.
After only one year of research as a mathematician at Bell Laboratories, he conceived an original and creative way to solve the same problem. It was so good it appeared in the Time magazine and the newspapers in 1984. Imagine people writing in newspapers and the Time magazine about an obscure mathematical algorithm. The only thing that could justify such publicity; it was really amazing. His name became a buzzword in the 80’s .
What did he do?
There are two ways in which it can be seen. In our superhero example, he placed our blind super-hero in the middle of the walled room, with a different superpower: having a device in his utility belt that indicates how good is the place he has in front of him. He can spin around and know in which direction is the most promising to walk to, even across the middle of the room. The best direction can lead him to bump in the middle of a wall, so another device says how close he is to bumping, so he can walk in a direction that is suboptimal, but at least he does not crash in the middle of a wall (remember: he knows the optimum is in a corner).
He will make a zig-zag until he arrives at, or close to, the corner. So, instead of going from corner to corner of the walls, he avoided the walls, arriving directly to the one he wants.
Nowadays, we know that for some problems SIMPLEX is best, and for others, Karmarkar's algorithm is best. We have grown up and know that there is no tool that is best for all. However, his advances allowed us to cope with big-scale problems.
We will always benefit from having mathematicians and institutions that make a living thinking on how to fold the space, and look in totally new ways to old problems. We know for sure we are having more and more new, bigger and more complex problems!
Dantzig, George B., Alex Orden, and Philip Wolfe. "The generalized simplex method for minimizing a linear form under linear inequality restraints." Pacific Journal of Mathematics 5.2 (1955): 183-195.
Karmarkar, N. (1984, December). A new polynomial-time algorithm for linear programming. In Proceedings of the sixteenth annual ACM symposium on Theory of computing (pp. 302-311). ACM.
ACM Paris Kanellakis Theory and Practice Award. Acessed Feb 9, 2017 from: http://awards.acm.org/award_winners/karmarkar_0424282.cfm
Angier, Natalie (1984-12-03). "Folding the Perfect Corner". Time Magazine. Retrieved 2008-07-12.