El problema de la mochila aplicado en industria

Todos hemos escuchado alguna vez la pregunta: ¿qué te llevarías a una isla desierta? La idea parece sencilla, pero en realidad obliga a elegir entre varios elementos que aportan un beneficio y consumen una capacidad limitada dentro de nuestra mochila.

Si hay pocos elementos, la decisión puede tomarse a mano. Sin embargo, cuando el número de opciones aumenta, aparecen muchas combinaciones con beneficios parecidos y costes similares. Determinar cuál es la mejor deja de ser trivial.

Este tipo de problema se conoce en investigación operativa como problema de la mochila o knapsack problem.

Para visualizarlo, entenderlo y resolverlo de forma didáctica he desarrollado una aplicación que permite crear configuraciones distintas, probar varios algoritmos y comparar el resultado obtenido por cada técnica.

El siguiente paso natural sería conectar esta lógica con una aplicación SCADA, de forma que las decisiones puedan automatizarse y convertirse en acciones reales sobre los PLC.

En la industria aparecen continuamente problemas de decisión parecidos. Algunos ejemplos claros:

• Activación de líneas productivas con energía limitada: elegir qué líneas activar sin superar los límites de consumo eléctrico.
• Selección de tareas de mantenimiento durante paradas técnicas: decidir qué trabajos ejecutar cuando el tiempo disponible es limitado.
• Gestión de cargas de camiones: maximizar el valor transportado sin superar peso, volumen o prioridades logísticas.

El modelo básico busca maximizar el valor total de los elementos seleccionados sin superar una restricción de capacidad.

A medida que aumenta el número de ítems, el número de combinaciones posibles crece de forma exponencial.

Esto hace que encontrar la solución exacta sea computacionalmente inviable en muchos casos. En la práctica, evaluar todas las combinaciones puede ser imposible cuando hay muchos elementos o muchas restricciones.

Por eso se recurre a algoritmos aproximados que entregan buenas soluciones en poco tiempo, aunque no siempre garanticen la solución perfecta.

Cuando el número de ítems es bajo o moderado se puede usar una solución exacta. Cuando el problema crece, conviene aplicar métodos más eficientes.

• Evalúan todas las combinaciones posibles o exploran el espacio de búsqueda de forma controlada.
• Son fiables, pero pueden ser lentas cuando hay muchos ítems.
• Se apoyan en técnicas como programación dinámica o ramificación y poda.
• OR-Tools de Google permite aplicar estas técnicas en problemas pequeños o medianos.

• No garantizan siempre la mejor solución, pero son rápidas y prácticas.
• Usan reglas simples, por ejemplo seleccionar elementos con mejor relación valor/peso.
• Son muy útiles en sistemas industriales que requieren respuesta en tiempo real.

• Son algoritmos más avanzados, inspirados en procesos como evolución, recocido simulado o enjambres.
• Encajan bien en problemas grandes, complejos o con múltiples restricciones.
• Permiten obtener soluciones muy cercanas a la óptima con bajo coste computacional.

OR-Tools, la librería open source de Google, combina varias de estas técnicas y permite resolver el problema de la mochila de forma exacta o aproximada según el tamaño y la urgencia del caso. Es ligera, rápida y encaja muy bien con soluciones industriales en Python.

La aplicación desarrollada busca hacer visible la problemática de forma didáctica y mostrar distintos algoritmos open source para resolverla. La he creado con Copilot Agent en Visual Studio Code, utilizando Streamlit.

La aplicación permite definir el número de ítems, asignar beneficios y pesos aleatorios, fijar la capacidad máxima de la mochila y ejecutar distintos algoritmos para comparar cómo resuelve cada uno el problema.

Con la aplicación podemos:

• Modificar número de ítems, beneficio y peso de los elementos.
• Seleccionar distintos algoritmos de resolución.
• Comparar los resultados obtenidos por cada algoritmo.

Aquí un vídeo con un ejemplo:

PHS Knapsack está hecho con Streamlit y desarrollado en Visual Studio Code. El código fuente está disponible en GitHub:

Descargar PHS Knapsack

Una vez descargado y abierto en Visual Studio Code, los pasos básicos son los siguientes:

1. Instalar Python

2. Crear un entorno virtual:

3. Activar el entorno:

4. Instalar los requerimientos:

5. Ejecutar la aplicación:

Además, recomiendo usar Copilot Agent para seguir desarrollando la aplicación, añadir nuevos algoritmos y adaptarla a casos reales de planta.