Un buen programador, combina de forma inteligente las herramientas de las que dispone para alcanzar su objetivo. Por eso, es muy importante conocer, aunque sea “de oídas”, el mayor número de herramientas que puedan sernos útiles en el futuro (tiempo habrá de desarrollarlas llegado el momento).
Para los que no la conozcáis, hoy os presento una auténtica joya, la programación lineal y su “alter ego”, la todavía indómita, programación lineal entera.
Programación lineal
Sin entrar en muchos detalles ni pompa matemática, la programación lineal “consiste en modelar un problema de optimización utilizando, únicamente, inecuaciones lineales”. ¡No te asustes! es más fácil de lo que parece.
Desgranemos la definición anterior:
Modelar: consiste en transformar el problema a resolver en un conjunto de ecuaciones o fórmulas que lo definen exactamente o lo aproximan. Por ejemplo, podemos modelar la aguja de una balanza con la ecuación “aguja = plato1 – plato2” donde platoN es el peso que soporta cada plato.
Problema de optimización: son aquellos en los que se barajan varias soluciones y la forma de optar entre una u otra solución es indicando que queremos optimizar algún recurso. Por ejemplo, un coche puede hacerse rápido, potente o de bajo consumo, sin embargo, aumentar uno de los tres supone reducir los otros dos (eg. más veloz implica menos potente y con más consumo).
Inecuación: como cualquier ecuación, pero además de la identidad (igualdad o equivalencia), pueden aparecer las relaciones “mayor y menor que”, es decir cualquiera de: =, <, >, <= y >=. Por ejemplo, una inecuación es 3 x < 1 + yx.
Lineal: informalmente, existe una relación lineal entre dos elementos cuando hay una constante que multiplicada a uno da como resultado el otro. Toscamente podríamos decir que son las ecuaciones más simples que podemos encontrarnos. Por ejemplo, la siguiente es un ejemplo de ecuación lineal: 3 x + 2 y = 1 + 4z.
Lo fantástico del caso es que no hace falta saber nada más, sólo con estos ingredientes podemos utilizar toda la potencia de la programación lineal.
Programación lineal entera
La programación lineal entera es aquella en la que alguna de las incógnitas sólo puede tomar valores enteros.
Aunque pueda parecer una pequeña diferencia sin importancia, en realidad lo cambia todo. Mientras que para la programación lineal existen algoritmos que corren en tiempo polinómico, la programación lineal entera es NP-completo y por tanto, nadie ha sido capaz (ni se cree que se pueda) de encontrar ninguna forma eficiente de resolverlos.
En la práctica, existen muy buenos algoritmos que encuentran soluciones muy rápidamente. De hecho, el probablemente más usado algoritmo para programación lineal (el Simplex de Danzig) tiene coste exponencial (como en LPI) sin embargo en la práctica da muy buenos resultados.
Modelando problemas
Hay problemas en los que, aplicar programación lineal, es directo, puesto que el propio problema está planteado en términos de inecuaciones y alguna condición de optimización. Un ejemplo típico sería “hacer un programa que maximice el número de prendas de vestir que podemos hacer en una fábrica”, nos dirían cuanta tela, botones, etc… precisa cada prenda y listo.
Lo realmente interesante de la programación lineal es que podemos aplicarla en situaciones en las que, aparentemente, es preciso codificar el típico algoritmo a medida.
Suma de bits (ejemplo 1)
El otro día comentábamos el problema de la suma de bits, que consistía en que, dado un número X, había que encontrar otros dos Y y Z tales que, sumándolos den X, pero a la vez la cantidad de bits a 1 que tengan sea máxima. ¿Se puede aplicar aquí programación lineal?, veamos como.
Aunque ésto es obvio para cualquier programador, la representación en base 10 de un número binario es la siguiente:
Y = 20 y0 + 21 y1 + … = ∑b 2b yb
Donde cada yb es el bit b-ésimo.
Como se trata de maximizar el número de bits de Y y Z es obvio entonces que tenemos que maximizar la expresión:
∑b (yb + zb)
Sujeto a una única restricción, que la suma de estos dos números debe dar X, es decir:
∑b 2b (yb + zb) = X
Siendo, claro está, binarias las variables yb y zb.
Es mucho más sencillo de lo que parece. Una implementación casi literal de lo comentado sería, usando Microsoft Solver Foundation:
Por supuesto en este caso es mucho mejor usar la otra solución que dimos (con coste constante), pero hemos visto como transformar un problema.
Kata Potter (ejemplo 2)
El Kata Potter es un problema de aplicación de descuentos. Hay 5 libros diferentes en una colección, según los libros que compres te dan más o menos descuento, pero los libros tienen que ser diferentes, si los compras iguales no hay descuento. Así, si compras tres libros pero dos son iguales, te harían descuento sólo por dos diferentes, el tercero lo pagas entero.
En este caso, hay una forma sencilla de modelar el problema como un sistema de programación lineal. Creamos unas variable para los libros del mismo tipo r1, r2, r4, r8 y r16. Luego otras variables para cualquier pareja de libros r3, r5, r9, … y así sucesivamente. Basta enumerar las máscaras de bits desde 0 hasta 25-1 para obtener todos los grupos de descuento posibles.
El resultado, es que Kata Potter tiene una solución directa usando programación lineal, y es ésta:
Puzzle (ejemplo 4)
Otro ejemplo muy curioso y muy útil es cuando tenemos un problema en el que debemos encajar los recursos de forma que no se solapen (o con limitaciones), con formas diversas (eg. piezas del Tetris), con costes diferentes (eg. ciertas piezas son más caras que otras), etc…
La forma de transformar este tipo de problemas, consiste en asignar a cada posible posición de una pieza una variable booleana. Si dos piezas tienen intersección no vacía, significa que sus variables son incompatibles, y generarían una restricción como:
pieza1 + pieza2 <= 1
Claro que lo normal es que las intersecciones sean entre muchas piezas, por lo que las restricciones son de la forma:
pieza1 + pieza2 + … + pieza10 <= 1
pieza1 + pieza3 + … + pieza9 <= 1
pieza2 + pieza4 + … + pieza8 <= 1
¿Podrías resolver el siguiente problema?: “asignado un coste a cada pieza del Tetris, obtener la forma más barata de llenar un tablero de ajedrez siempre que esté lo más lleno que sea posible”. ¡Ánimo!.
Cuando no usar programación lineal
Si quieres tener una versión muy optimizada, que sea muy eficiente, antes de usar la solución de programación lineal (sobre todo si es entera), deberías intentar aprovechar posibles datos adicionales que permitan contextualizar tu problema. Quizás puedas reducir la complejidad de tu problema encontrando estrategias que te permitan desarrollar una implementación rápida y eficiente.
Dedicarás muchísimo más tiempo que con programación lineal, pero te lo habrás pasado en grande codificando.
Ventajas de usar programación lineal
Si nuestro problema es apto para ser resuelto con programación lineal, sin duda una forma de ahorrar muchas horas de codificación, testeo y manteniendo de código es aplicar y usar las librerías que tenemos a nuestro alcance. Por ejemplo, es probable que las librerías puedan hacer uso de GPGPU para paralelizar masivamente el cálculo de soluciones.
Además, cualquier avance que se realice en la resolución de estos problemas conllevará automáticamente una mejora en nuestras soluciones.
Transformar un problema a otro de programación lineal suele ser mucho más sencillo que afrontar directamente el problema inicial, además, si nuestro problema está en NP, los algoritmos desarrollados nos darán toda la eficiencia que actualmente está disponible.
Así que ya sabes, si tienes delante de ti un problema difícil, considera la posibilidad de usar programación lineal.
Más información | Kata Potter.
Más información | lp_solve Open Source, Microsoft Solver Foundation
Más información | Wikipedia, Wolfram