.

Los siguientes párrafos están extraídos de este informe de la Oficina Ejecutiva del Presidente de los Estados Unidos: Report to the President and Congress. Designing a digital future: Federally funded research and development in networking and information technology (página 71, diciembre, 2010).

Progress in Algorithms Beats Moore’s Law

Everyone knows Moore’s Law –a prediction made in 1965 by Intel co-founder Gordon Moore that the density of transistors in integrated circuits would continue to double every 1 to 2 years.

Fewer people appreciate the extraordinary innovation that is needed to translate increased transistor density into improved system performance. This effort requires new approaches to integrated circuit design, and new supporting design tools, that allow the design of integrated circuits with hundreds of millions or even billions of transistors, compared to the tens of thousands that were the norm 30 years ago. It requires new processor architectures that take advantage of these transistors, and new system architectures that take advantage of these processors. It requires new approaches for the system software, programming languages, and applications that run on top of this hardware. All of this is the work of computer scientists and computer engineers.

Even more remarkable –and even less widely understood– is that in many areas, performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed.

The algorithms that we use today for speech recognition, for natural language translation, for chess playing, for logistics planning, have evolved remarkably in the past decade. It’s difficult to quantify the improvement, though, because it is as much in the realm of quality as of execution time.

In the field of numerical algorithms, however, the improvement can be quantified. Here is just one example, provided by Professor Martin Grötschel of Konrad-Zuse-Zentrum für Informationstechnik Berlin. Grötschel, an expert in optimization, observes that a benchmark production planning model solved using linear programming would have taken 82 years to solve in 1988, using the computers and the linear programming algorithms of the day. Fifteen years later –in 2003– this same model could be solved in roughly 1 minute, an improvement by a factor of roughly 43 million. Of this, a factor of roughly 1,000 was due to increased processor speed, whereas a factor of roughly 43,000 was due to improvements in algorithms! Grötschel also cites an algorithmic improvement of roughly 30,000 for mixed integer programming between 1991 and 2008.

The design and analysis of algorithms, and the study of the inherent computational complexity of problems, are fundamental subfields of computer science.

Veremos en clase alguna de las ideas básicas del algoritmo del simplex (ver transparencias 54 a 70 de la asignatura, o transparencias 16 a 36 de estas otras del material adicional).

No obstante, su implementación detallada dista de ser sencilla. Por ejemplo, en esta anotación del blog de Jeremy Kun puede encontrarse una descripción más detallada, con enlaces a temas relacionados y al código escrito por el autor del blog:

Linear Programming and the Simplex Algorithm

En cuanto a la solución en tiempo polinómico de los problemas de programación lineal, en esta anotación puede leerse algún párrafo extraído del libro de Dasgupta, Papadimitriou y Vazirani sobre los algoritmos de Khachiyan y Karmarkar:

Linear programming in polynomial time

“Simplex is not a polynomial time algorithm. Certain rare kinds of linear programs cause it to go from one corner of the feasible region to a better corner and then to a still better one, and so on for an exponential number of steps. For a long time, linear programming was considered a paradox, a problem that can be solved in practice, but not in theory!

Then, in 1979, a young Soviet mathematician called Leonid Khachiyan came up with the ellipsoid algorithm, one that is very different from simplex, extremely simple in its conception (but sophisticated in its proof) and yet one that solves any linear program in polynomial time. Instead of chasing the solution from one corner of the polyhedron to the next, Khachiyan’s algorithm confines it to smaller and smaller ellipsoids (skewed highdimensional balls). When this algorithm was announced, it became a kind of “"mathematical Sputnik", a splashy achievement that had the U.S. establishment worried, in the height of the Cold War, about the possible scientific superiority of the Soviet Union. The ellipsoid algorithm turned out to be an important theoretical advance, but did not compete well with simplex in practice. The paradox of linear programming deepened: A problem with two algorithms, one that is efficient in theory, and one that is efficient in practice!

A few years later Narendra Karmarkar, a graduate student at University of California, Berkeley, came up with a completely different idea, which led to another provably polynomial algorithm for linear programming. Karmarkar’s algorithm is known as the interior point method, because it does just that: it dashes to the optimum corner not by hopping from corner to corner on the surface of the polyhedron like simplex does, but by cutting a clever path in the interior of the polyhedron. And it does perform well in practice.

But perhaps the greatest advance in linear programming algorithms was not Khachiyan’s theoretical break through or Karmarkar’s novel approach, but an unexpected consequence of the latter: the fierce competition between the two approaches, simplex and interior point, resulted in the development of very fast code for linear programming.”

(Credit: S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, McGraw-Hill, 2008.)

o hacer algo de trampa:

En cualquier otro caso, no será posible diseñar una estrategia ganadora. Formalicemos un poco el juego: Mediante matrices se pueden representar diversos juegos como el que inventaron Bob y Alice (ver entrada) o como ‘Piedra, papel o tijera’. Supongamos que dos jugadores, llamados Row y Column, deciden jugar a ‘Piedra, papel o tijera’. La ganancia del jugador Row (y equivalentemente la pérdida del jugador Column) puede representarse con la siguiente matriz.

Las letras ‘r’, ‘p’ y ‘s’, se corresponden con las jugadas piedra (rock), papel (paper), tijera (scissors). Así, la entrada 1 de la fila ‘p’ y columna ‘r’ indica que si Row elige papel y Column piedra, entonces Row gana un punto.

¿Existe alguna estrategia ganadora para este juego? Es decir, ¿puede alguno de los jugadores asegurarse la victoria a la larga si juega óptimamente? Obviamente, si Row siempre elige la misma jugada, por ejemplo piedra, Column se percatará de su inocente estrategia, acabará sacando siempre papel y ganándole. Conviene por tanto despistar lo máximo posible al oponente eligiendo las jugadas de manera aleatoria. En clase confirmaremos el pensamiento intuitivo que nos dice que si los dos juegan lo mejor posible, es decir maximimizan el valor esperado de su ganancia (en este caso eligiendo al azar entre las tres jugadas), a la larga terminarán en empate. Lo mismo ocurrirá si introducimos dos jugadas más, ‘lagarto’ y ‘Spock’:

Imagina ahora que se obliga a Row a anunciar públicamente su estrategia (es decir la probabilidad con que elegirá piedra, papel y tijera) y Column puede elegir la suya en función de la de Row. ¿Se verá Row perjudicado por esta nueva regla del juego?

Y, ¿qué pasaría si en vez de ‘Piedra, papel o tijera’ o ‘Piedra, papel, tijera, lagarto o Spock’ , consideráramos un juego con la siguiente matriz?

¿Existe ahora una estrategia ganadora para alguno de los jugadores?

Trataremos este tipo de juegos en clase y veremos que se pueden obtener respuestas a estas preguntas mediante programación lineal.

Compartimento  Peso (Tm)  Volumen (m3)
Frontal              10          6800
Central              16          8700
Trasero               8          5300

Además, para mantener el balance adecuado del avión, el peso de la carga en los tres compartimentos debe mantener la misma proporción que sus límites de capacidad de carga en peso.

Para el siguiente vuelo, se dispone de las siguientes mercancías a embarcar:

Mercancía   Peso (Tm)   Volumen (m3/Tm)  Valor (€/Tm)
M1                18              480            310
M2                15              650            380
M3                23              580            350
M4                12              390            285

El objetivo es determinar qué cantidad de cada mercancía debe embarcarse y cómo distribuirla en los compartimentos de forma que el valor total de la mercancía embarcada sea máximo.

Puede suponerse que cada mercancía puede fraccionarse, si se precisa, en cualquier proporción y que puede repartirse entre dos o más compartimentos, si se desea.

Nuestro avión

Solución

• Hay que decidir qué cantidad de cada mercancía debe ponerse en cada compartimento. Sea:

x_ij el número de toneladas de mercancía Mi (i=1,2,3,4) que va a ponerse en el compartimento j (j=1 para Frontal, j=2 para Central y j=3 para Trasero), con x_ij ≥ 0 para i=1,2,3,4; j=1,2,3.

• No puede cargarse más cantidad de cada mercancía que la disponible:

x₁₁ + x₁₂ + x₁₃ <= 18
x₂₁ + x₂₂ + x₂₃ <= 15
x₃₁ + x₃₂ + x₃₃ <= 23
x₄₁ + x₄₂ + x₄₃ <= 12

• Hay que respetar la capacidad en peso de cada compartimento:

x₁₁ + x₂₁ + x₃₁ + x₄₁ <= 10
x₁₂ + x₂₂ + x₃₂ + x₄₂ <= 16
x₁₃ + x₂₃ + x₃₃ + x₄₃ <= 8

• Hay que respetar la capacidad en volumen de cada compartimento:

480 x₁₁ + 650 x₂₁ + 580 x₃₁ + 390 x₄₁ <= 6800
480 x₁₂ + 650 x₂₂ + 580 x₃₂ + 390 x₄₂ <= 8700
480 x₁₃ + 650 x₂₃ + 580 x₃₃ + 390 x₄₃ <= 5300

• El peso de la carga en los tres compartimentos debe mantener la misma proporción que sus límites de capacidad de carga en peso:

(x₁₁ + x₂₁ + x₃₁ + x₄₁)/10 =

= (x₁₂ + x₂₂ + x₃₂ + x₄₂)/16 =

= (x₁₃ + x₂₃ + x₃₃ + x₄₃)/8

• El objetivo es maximizar el valor total de la carga:

maximizar 310 (x₁₁+ x₁₂+ x₁₃) +

+ 380 (x₂₁+ x₂₂+ x₂₃) +

+ 350 (x₃₁+ x₃₂+ x₃₃) +

+ 285 (x₄₁+ x₄₂+ x₄₃)

En esta asignatura veremos cómo resolver este tipo de problemas para, en el caso que nos ocupa, llegar a obtener la siguiente solución óptima (calculada con esta herramienta en línea) (nueva versión):

x₁₁ = 0, x₁₂ = 0, x₁₃ = 0, x₂₁ = 7, x₂₂ = 0, x₂₃ = 8, x₃₁ = 3, x₃₂ = 12.9474, x₃₃ = 0, x₄₁ = 0, x₄₂ = 3.05263, x₄₃ = 0

Valor total óptimo de la carga: 12151.6 €