NP completo o problemas NP difíciles en la vida real

¿Alguien tiene ejemplos de la vida real en los que regularmente resuelven problemas NP completos o NP difíciles (por heurística, o persiguiendo una solución subóptima o lo que sea) en su trabajo? Sé que ocurren en la programación, la planificación, el diseño de VLSI, etc., pero estoy tratando de tener una idea de las principales industrias que emplean programadores o ingenieros hoy en día que regularmente hacen esto. Si uno desarrollara experiencia o una biblioteca, por ejemplo, optimización combinatoria, ¿dónde podría usar eso como parte de un trabajo de programación?

¿Alguna cuenta personal?

Algunas de las cosas en las que puedo pensar (la mayoría de ellas he estado involucrado más o menos):

• Entornos de desarrollo para lenguajes y compiladores. Preguntas como: ¿esta gramática genera un lenguaje ambiguo? (¡Este problema es realmente indecidible!)
• Recuperación de datos. Reensamblaje de paquetes de datos parcialmente perdidos o recuperación de archivos fragmentados. (Complejidad factorial)
• Seguridad de software. Evaluación de todas las posibles rutas de ejecución a través de un software para determinar si se le puede atribuir algún comportamiento observado. (¿Problema de detención?)
• Logística. Optimización del uso de transportes basados ​​en paquetes para transportar, su tamaño y hacia dónde deben ir. (Al menos exponencial)

Hay muchos ejemplos estándar, como encontrar la ruta más corta, la programación de enfermeras, etc., pero si te gusta la optimización combinatoria, ya sabes todo sobre ellos :)

He utilizado recocido simulado con restricción de tiempo para resolver un problema similar a un vendedor ambulante en la fabricación de paneles táctiles. Cada milisegundo que pudiéramos eliminar del tiempo de ciclo del grabado láser de cada panel aumentaría el rendimiento, la utilización y, por lo tanto, la rentabilidad de la máquina, por lo que puse mucho esfuerzo en minimizar el tiempo muerto (rutas de no trazado) entre las rutas de trazado (que obviamente no se pudo optimizar).

Utilicé un algoritmo limitado en el tiempo para sortear la dureza NP del problema, ya que no podíamos correr el riesgo de que el cálculo de la optimización demorara más que el tiempo ahorrado por la ruta más óptima. Mientras la máquina movía el panel de la posición de carga a la posición donde la cabeza del láser estaba sobre la esquina más cercana, tuve tiempo de ejecutar algunas simulaciones. El algoritmo casi nunca se completó en unos pocos cientos de milisegundos del movimiento, pero casi siempre devolvió una mejor ruta de escritura que cualquiera de los modelos simples y no adaptativos que siempre habíamos usado antes (como las rutas en espiral o de serpiente).

Estoy trabajando (en este momento, en realidad) en el problema bioinformático de la alineación de secuencias de ADN locales múltiples. El punto de esto es que si muchas secuencias de genes con alguna propiedad común (perfil de expresión similar o la misma unión del factor de transcripción en un experimento con chip ChIP) se alinean fuertemente en algún momento, entonces probablemente haya encontrado la razón de su común propiedad. Por otra parte, estoy más interesado en los aspectos estadísticos del problema. A pesar de que es NP-hard, no pierdes mucho al usar la heurística en la práctica. La parte interesante del problema, en mi humilde opinión, es un problema de relación señal / ruido.

Realmente no sé qué significa NP completo / difícil, pero creo que la planificación automática de suministros es algo así.

Tiene un plan de demanda de 90 días en adelante para 100 SKU de producto: ¡cerveza! Los 100 productos SKU provienen de:

• hay de 10 a 15 tipos de materia prima cruda base de nivel 1, se elaboran en latas grandes de mil litros y lleva un día;
• después de la preparación, se deben agregar algunos materiales (¿levadura?), y debe descansar durante 10-15 días, luego se obtienen 15-20 tipo de material de nivel 2;
• Finalmente, cuando esté listo, se deben agregar algunos materiales, es el material de nivel 3, llamado cerveza potable, hay cc. 30 tipos de cervezas;
• la cerveza se puede embotellar como 3 dl, 5 dl, a veces recibe un collar especial (nivel 4), luego se puede empacar como caja de 5x4, paquete de 6 (nivel 5).

Hay "líneas" de máquinas para cada operación: desde la preparación hasta el envasado. Las máquinas pueden realizar más operaciones, por ejemplo, algunas máquinas de embalaje pueden hacer paquetes de 6 y 3 paquetes, pero otros solo pueden hacer 6 paquetes. Hay restricciones, por ejemplo, la velocidad, o la gran tetera de elaboración es para preparar cerveza mín. 6000, máximo, 8000 l de cerveza, (pero si el tipo de cerveza es ligero, entonces el mínimo es de 5000 ly el máximo es de 7000 l). Y así sucesivamente, en todos los niveles.

La tarea: como mencioné, hay un plan de demanda, para el tipo 100 de nivel 5 (el material embotellado y empaquetado). Haga un plan de fabricación óptimo para los 5 niveles, todas las máquinas. Minimice los interruptores de la máquina (por ejemplo, embotellar .5, .5, .5, .3, .3, .3 es mejor que .3, .5, .3, .5, .3, .5, hay menos swithc, menos tiempo muerto para máquinas de embotellado). Priorización por cliente: algunos clientes requieren enviar la cerveza solo con más del 50% del tiempo de vencimiento restante. Etcétera etcétera.

Descubra los cuellos de botella (eh), haga planes alternativos agregando máquinas inexistentes a estos puntos, luego se puede usar el mejor escenario virtual para sugerir comprar nuevas máquinas.

¿Es lo suficientemente difícil o debería decirle cómo funciona una fábrica textil ?

(Comentario personal: la web, el banco y la logística son áreas desafiantes, pero son juguetes para bebés en comparación con los problemas de fabricación).

Descargo de responsabilidad: los números están distorsionados por razones de seguridad, el orden de magnitud es real.