All of us who are more or less aware of the advances in science in general and mathematics in particular, agree that we are living (or we may have to say we were living in the case of Spain: crises, cuts… I already know know) a golden age: every day more research is carried out, the methods used are refined, the information reaches us all almost instantaneously and with this access to research has been democratized since, not so long ago, the true Quality research was off-limits to those outside official circles, who were the only ones who enjoyed up-to-date information long before those outside those circles.
Of course, in experimental sciences progress can be limited by the enormous amounts of money required to make certain equipment available, but the most expensive equipment has been built among various nations and agencies, and access to it is often determined by the quality of the equipment. the research proposed more than by other factors (naturally, there would be a lot to qualify in everything said above, but let’s say that, in general terms, progress is being made in that direction). But math is a very, very cheap science, so all you need is to be informed about what’s going on in the rest of the world, and someone who knows the right tools to have a good idea. In conclusion, let’s say that the chances of someone at a “province” university in a country in crisis producing something of quality, with global repercussions in mathematics, are infinitely higher today than they were a century (or half a century) ago. . In fact, some “provincial” mathematicians from a country in crisis had some international repercussion a few years ago: I mean Paco Santos from Cantabria already Isabel Fernandez (Seville) and paul mira (Murcia). The latter two were invited to give a lecture at the 2012 World Mathematics Congress held in India, and Paco proved the Hirsch conjecture false, a question that had racked mathematical brains around the world for ages. last fifty years. One may wonder why such a conjecture is important. In reality, it would have been more important for the conjecture to be true, but things are as they are and Paco did nothing but show the reality.
Dantzig and the unreasonable effectiveness of the simplex method
Hirsch’s conjecture is related to what is known as the simplex method (or simplex): in the year 2000, a prestigious computing and engineering journal asked two renowned researchers to choose the “ten algorithms of the 20th century”, that is, that is, the most influential algorithms in the development of science and engineering of the last century. One of the ten chosen was said simplex method in linear programming.
Linear programming (technically: finding the optimum of a function in a region defined by a system not of linear equations but of inequations —where inequalities appear—) tries to minimize the resources necessary to achieve certain objectives and it emerged secretly during World War II. World War. In a war, it is already known, each army tries to achieve the maximum enemy losses with the minimum cost for its part. As soon as the war ended, it was found that those ideas that were more or less used by all armies in order to optimize their resources could be recycled to improve industrial production and the economy of companies. The “father” of linear programming is usually considered to be the American George B. Dantzig (1914-2005), who, in 1947, published an article where one of the protagonists of our history was presented: the simplex method to solve linear programming problems computationally.
I am not going to go into details of how this algorithm works, but as has been said, many experts consider this method to be one of the fundamentals of the 20th century. What I cannot resist telling is an anecdote that involves Dantzig himself: in 1939, as a doctoral student at the prestigious University of California at Berkeley (there is also a more recent “curious” anecdote that involves this and many other universities Californians and the former Minister of Education Jose Ignacio Wertbut better not to go into those topics), as I said: Dantzig arrived late for one of the professor’s classes Neyman (a renowned statistician) and came across two problems listed on the blackboard. At night he began to solve them and it took him a few days because he found them quite difficult, so he gave them to Professor Neyman and he forgot about them, after a few weeks, he showed up at the door of his apartment to tell him, very excited, that the two problems he had just solved were two of the most famous open problems (to which no solution is known up to that moment) in statistics. When Dantzig approached Neyman a little later to ask him to assign him a thesis topic, the latter merely shrugged his shoulders and told him that all he had to do was put the two problems he had solved in a folder.
The anecdote that I have just related seems to me, moreover, significant for my thesis: in the first half of the 20th century it was impossible for that to happen in Spain: there may have been some hidden Dantzigs, potential Dantzigs, but what did not exist were professors Neymans , who knew what were the important problems that should be attacked, who were aware of what was happening worldwide (which was a very restricted world at that time). However, in this century we have Paco Santos, Isabel Fernández, Pablo Mira who know what problems are important and how to try to solve them; but I’m getting ahead of myself in my story: let’s go back to Dantzig.
As I was saying, Dantzig published his algorithm to solve linear programming problems in 1947 and from the outset it was found that this method solved these problems very efficiently. But it is one thing to verify that a method works to solve the problems that are proposed and quite another to guarantee that this will always happen, to be one hundred percent sure that any linear programming problem can be solved in a short time. by the simplex method (of course, the more inequalities we try, the longer the method will take to find the solution, but that is assumed). This, guaranteeing that a method is efficient, has been achieved for many known algorithms, but not for the simplex one. So we can say, paraphrasing the Nobel Prize in Physics Eugene Wigner that the simplex is an algorithm that is unreasonably efficient: no one has been able to show that it is indeed efficient in all cases. Furthermore, there are many variants of the simplex method, and no one has been able to show that any of these variants is efficient. Rather the opposite, as we will see in the following article.
(continued here)