NP-integridad para el programa lineal entero

Question

Este es un problema de tarea, así que no quiero la solución.Necesito un indicio de que problema para reducir a los siguientes y / o cómo empezar.Estábamos pensando en la TSP o en un conjunto independiente, pero no pudimos encontrar una solución.

Tenemos $ i \ ldots j $ tiendas y $ i \ ldots n $ Posibles lugares paraconstruir un nuevo almacén.Los costos para construir un nuevo almacén son $ c_j $ .Entre cada tienda y el almacén es un camino de costo $ d_ {i, j} $ .Cada tienda necesita estar conectada a al menos un almacén.

El problema de la decisión es: hay un conjunto de almacenes y caminos para que la suma sea más pequeña que un número dado $ k $ .

Answer 1

Este es un clásico problema de ubicación de la instalación . Que el artículo de Wikipedia sugiere que la dureza de NP se puede probar mediante la reducción de cubierta de ajuste .

---

Dado que el Asker ahora ha declarado que ha encontrado una solución al reducir la cubierta VERTEX , continuaré adelante y revelaré la reducción de la cubierta establecida :

Por cada valor, cree una tienda; Para cada conjunto, cree un almacén. Asigne el costo de cada almacén a ser 1. Asignar el costo de la ruta desde un almacén a una tienda para ser un valor arbitrariamente pequeño si ese conjunto de almacén contiene el valor de esa tienda, o un valor arbitrariamente grande de otra manera. Luego, la solución de costo mínimo al problema de la instalación se basa con precisión el conjunto de almacenes correspondientes a la cubierta establecida mínima en el problema original.

El $ k $ el valor se utiliza para convertir el problema de optimización (minimizar los conjuntos / costo) en un problema de decisión (¿hay una solución con no más de $ k $ conjuntos / costo?). El $ k $ de la instancia de la cubierta establecida será la misma que la $ k $ en el problema de la instalación Instancia Si se le permite configurar los valores "arbitrariamente pequeños" a 0, de lo contrario, es posible que tenga que fudir el valor por alguna cantidad, pero menos de 1 siempre que elija los pesos "arbitrariamente pequeños" para ser lo suficientemente pequeños. Solo necesita que el total de cada costo "arbitrariamente pequeño" sea inferior a 1, y cada costo "arbitrariamente grande" para ser mayor que la suma de los costos de todos los almacenes y todas las rutas "arbitrariamente pequeñas".
Tenga en cuenta que, si solo se permiten los costos de enteros en el problema de las instalaciones, aún puede lograr el mismo resultado al escalar todos los costos por su mínimo múltiple común.