Algoritmos para el problema de los vales

(Esta entrada es continuación de ésta).

Recordatorio: el problema consiste en que queremos comprar unos productos de precios p_i y nos dan un vale de descuento por cada compra de C euros o mayor; así que tenemos que dividir los productos en varias compras, de forma que consigamos el mayor número posible de vales de descuento. En realidad, el planteamiento original era que el precio tenía que ser mayor que C.

Vale, ya sabemos que es imposible encontrar siempre rápidamente la mejor solución. ¿Pero cómo encontramos rápidamente una solución razonablemente buena?

Mi amigo sugirió este algoritmo:

Yo sugerí este otro. Tiene la pega de que hace falta suponer que todos los precios son múltiplos de un céntimo para poder calcular rápidamente la lista de todos los posibles precios.

• Mientras el precio de los artículos que quedan por pedir exceda C:
  • Averiguar el precio de pedido más pequeño que se puede hacer que exceda C
  • Encontrar un conjunto de artículos que tenga ese precio
  • Hacer un pedido con ese conjunto
• Añadir los artículos que sobran al último pedido, si se ha hecho algún pedido, o hacer con ellos el primer pedido.

Los dos algoritmos se ejecutan en tiempo polinómico, así que o bien P=NP y lo hemos resuelto, o bien estos algoritmos no siempre encuentran la solución óptima. He aquí dos ejemplos en los que fallan:

• C=20 y los precios son {6,6,6,7,8,9}. En este caso, el primer algoritmo falla, porque al meter los dos precios mayores en la misma compra se queda sin encontrar la solución óptima, que es {9,6,6}, {8,7,6}. El segundo algoritmo sí que acierta, porque es posible hacer una compra de 21, luego la otra también tiene que ser de 21.
• C=20 y los precios son {7,7,7,15,15,15}. Ahora el primer algoritmo acierta, porque encuentra la solución {7,15}, {7,15}, {7,15}, pero el segundo algoritmo falla, porque el precio más bajo superior a 20 es 21, así que empieza haciendo la compra {7,7,7}, y luego no puede conseguir dos vales más.

El problema de los vales

He estado pensando con un amigo sobre el siguiente problema.

Quiero comprar en un supermercado n productos de precios estrictamente positivos {p_i}. Por cada compra que haga de más de C euros me dan un vale de descuento. ¿Cómo tengo que particionar los productos que quiero comprar en varias compras, de forma que el número de vales de descuento que consiga sea máximo?

Este problema tiene toda la pinta de ser NP-completo, y tras darle varias vueltas, hemos conseguido una demostración bastante fea, reduciendo a él el problema del bin packing, que sabemos que es NP-completo.

Empezaremos formulando los dos problemas formalmente:

1. Vales. Dados un número de productos n, sus precios {p_i>0}_i=1ⁿ, y la cantidad mínima C con la que obtener un vale, encontrar una partición {S_i} de {p_i} con el número máximo de conjuntos tales que Σ_Sip_i > C. Dada una solución, llamaré p_ki a los precios de los productos de la compra k.
2. Bin packing. Dada una colección ilimitada de contenedores de volumen V, un número de objetos n, y sus volúmenes {a_i<V}_i=1ⁿ, encontrar una partición {S_i} de {a_i} con el número mínimo de conjuntos tales que Σ_Sia_i ≤ V. Dada una solución, llamaré a_ki a los volúmenes de los objetos del contenedor k. (Estos objetos sólo tienen tamaño, no forma; por ejemplo, como al guardar ficheros en un disco duro.) (Podría haber objetos de volumen a_i=V, pero como ellos solos llenarían un contenedor, los quitaría del problema.)

La idea de la demostración es sencilla, consiste simplemente en tomar p_i = V-a_i, pero se complica bastante por el camino.

Vamos al grano. Supongamos que puedo resolver los problemas de vales en tiempo polinómico, y que tengo un problema de bin packing.

Para este problema de bin packing tendré un ε>0 definido de la siguiente manera:

ε < min( min{a_i}, (min{Σs_i : {s_i}⊂{a_i}, Σs_i>V} - V) / n)

Es decir, ε es menor que cualquier a_i, y de todas las sumas de volúmenes mayores que V, me quedo con la menor, resto V, y divido entre n. Este ε tiene la propiedad de que si Σ(a_ki-ε)<V, entonces Σa_ki≤V; porque, de lo contrario, Σa_ki>V y estaría dentro del conjunto de la definición de ε, luego ε≤(Σa_ki-V)/n, y por tanto V≤Σa_ki-n·ε; pero, dado que como mucho hay n términos en la suma, V≤Σ(a_ki-n), y de aquí la contradicción.

Claro, esta definición plantea un problema filosófico; dado que en principio hay un número exponencial de posibles sumas, ¿cómo calcular ε en tiempo polinómico? Es una buena pregunta, que afea esta demostración. En realidad, no hay que calcular ése epsilon, vale cualquier número menor. Por ejemplo, si los volúmenes de todos los objetos fuesen múltiplos de 1 centímetro cúbico, entonces podría tomar ε = 1cc / n, sin preocuparme de si el mínimo es 1cc o 2cc o 3cc o lo que sea.

Sigamos. Para un m arbitrario (que no tiene por qué ser el número mínimo de contenedores, es simplemente un número) puedo considerar el siguiente problema de vales (nótese que ε no depende de m):

1. Hay n·m productos;
2. el precio de los n primeros productos es V-a_i+ε;
3. el precio de los siguientes n·(m-1) productos, que llamaré comodines, es V;
4. para conseguir un vale tengo que hacer una compra de más de C = (n-1)·V.

A continuación demostraré cuatro proposiciones sobre este problema que depende de m.

Primera, todos los productos en este problema tienen un precio p_i≤V, y los únicos que tienen precio V son los comodines. Porque si V-a_i+ε>V, entonces ε>a_i.

Segunda, si el problema de vales con m tiene soluciones con m compras, entonces todas sus compras tienen exactamente n productos. Porque si una compra tuviese n-1 productos, la suma de sus precios sería como mucho (n-1)·V = C, de forma que no conseguiría un vale, así que cada compra contiene al menos n productos. Pero en total hay m compras y n·m productos, así que cada compra tiene que contener exactamente n productos.

Tercera, si el problema de bin packing tiene una solución con m contenedores en la que ningún contenedor está vacío, entonces el problema de vales tiene al menos una solución con m vales, en la que ninguna compra consiste sólo en comodines. Esta solución se obtiene a partir de la solución del problema de bin packing, convirtiendo cada contenedor en una compra, mandando los j_k objetos del contenedor k con volumen a_ki a productos de la compra k con precio V-a_ki+ε, y luego añadiendo n-j_k comodines de precio V hasta tener n productos; se consigue un vale por cada compra porque, como Σa_ki≤V, entonces

Σp_ki = Σ(V-a_ki+ε) + (n-j_k)·V
= j_k·V - Σa_ki + j_k·ε + n·V - j_k·V
= n·V + j_k·ε - Σa_ki
≥ n·V + ε - V = C + ε > C

donde sabemos que j_k≥1 por la condición de que hay al menos un objeto en cada contenedor, que se traduce en que en la compra k hay al menos un producto que no es un comodín.

Cuarta, si el problema de vales tiene una solución con m vales, entonces el problema de bin packing tiene una solución con m contenedores (a diferencia de la tercera proposición, aquí se permiten contenedores vacíos y compras de sólo comodines). Como antes, generamos la solución del problema de bin packing a partir de la solución del problema de vales, mandando la compra k al contenedor k; como Σp_ki>C=(n-1)·V, y en esa suma hay n-j_k comodines,

Σ(V-a_ki+ε) + (n-j_k)·V > (n-1)·V

j_k·V - Σ(a_ki-ε) + (n-j_k)·V > (n-1)·V

V > Σ(a_ki-ε)

Al definir ε se demostró que esa última desigualdad implica Σa_ki ≤ V, y por tanto se satisfacen las condiciones para ser una solución del problema de bin packing; además, como había al menos un producto que no era un comodín, tiene que haber al menos un objeto de volumen >0 en el contenedor k, que por tanto no está vacío.

Juntando todo esto, el siguiente algoritmo encuentra la solución del problema de bin packing en tiempo polinómico:

• Si no hay objetos, devolver m = 0.
• Para m = 1, 2, ...
•     Si el problema de vales con m tiene una solución, devolver m.

Para empezar, mientras m sea tan pequeño que el problema de bin packing no tenga soluciones porque m contenedores no bastan, el problema de vales tampoco la tendrá, por la cuarta proposición. Pero justo cuando alcancemos el m mínimo para que bin packing tenga una solución sin contenedores vacíos, entonces el problema de vales tendrá una solución, con m compras donde ninguna compra consistirá sólo en comodines, por la tercera proposición. Aquí hay que hacer la observación de que con el m mínimo no puede haber soluciones con contenedores vacíos... porque entonces eliminaríamos un contenedor vacío y tendríamos una solución con m-1 contenedores, de forma que m no sería mínimo.

Finalmente, ese algoritmo se ejecuta en tiempo polinómico porque el problema de bin packing contiene al menos n datos (los volúmenes de los n objetos), de forma que repetir algo n veces es polinómico en el tamaño del problema. Pero metiendo cada objeto en un contenedor diferente obtengo una solución trivial con n contenedores, así que el m mínimo tiene que ser menor o igual que n. Como cada ejecución del bucle se hace en tiempo polinómico, el tiempo total también lo es.

Quizás todo quede más claro con un ejemplo. Quisiera resolver el problema de bin packing consistente en guardar n=3 objetos de volúmenes 4, 6 y 7 en contenedores de volumen V=10. Como todos los volúmenes son múltiplos de 1, puedo tomar ε = 1/n = 1/3. Hay más de 0 objetos, luego no me basta con 0 contenedores. Pruebo m=1; es decir, resuelvo el problema de los vales con precios 10-a_i+ε = 6.33, 4.33 y 3.33, y me dan un vale por compras de más de (n-1)·V = 20; obviamente no hay solución, porque el precio de todos los productos juntos, 6.33+4.33+3.33=18, no llega a 20. Pruebo ahora con m=2; a los productos de antes añado tres comodines de precio V=10, así que tengo 6 productos de precios 6.33, 4.33, 3.33, 10, 10 y 10. Ahora sí que hay soluciones, en concreto una: las dos compras son {6.33, 4.33, 10}>20 y {10, 10, 3.33}>20; por tanto, hay soluciones del problema de bin packing, que obtengo eliminando los comodines y restando del volumen y ε, para quedarme con {4,6}≤10 y {7}≤10. También puedo mirar qué habría ocurrido para m=3; en este caso podría encontrar una solución como {6.33, 4.33, 10}>20, {10, 10, 3.33}>20 y {10, 10, 10}>20, que me indicaría que m es demasiado grande porque contiene una solución con n=3 comodines; pero también podría encontrar una solución como {10, 10, 3.33}>20, {10, 10, 4.33}>20 y {10, 10, 7.33}>20, que me indicaría que 3 contenedores son suficientes, pero me dejaría con la duda de si hay soluciones con menos contenedores (como el algoritmo prueba todos los m en orden creciente, nunca llego a tener la duda, siempre habré probado m=2 antes de probar m=3).

Ahora un ejemplo en el que el truco con ε resulta crucial. Tendremos n=2, volúmenes 4 y 6, y C=10. La solución es, obviamente, {4, 6}≤10. Pero si no fuese por el ε, el problema de vales no tendría solución, ya que los precios serían 10-4=6 y 10-6=4, pero claro, 6+4≯C=(n-1)·V=10. En este caso ε tiene que ser menor que 4 (no hay sumas mayores que 10), así que si tomo ε=3, los precios son 10-4+ε=9 y 10-6+ε=7. Ahora sí que existe una solución para m=1, {9, 7}>10, y por tanto {10-9+ε, 10-7+ε} = {4, 6} ≤ 10 es una solución del problema de bin packing.

Es una reducción muy fea, lo admito...