El problema de la mochila con ítems secuenciados: Complejidad, métodos de resolución, extensiones y aplicaciones.
Director del proyecto
Dr. Óscar C. Vásquez, académico e investigador del Departamento de Ingeniería Industrial Usach
Contexto
En contextos de incertidumbre o restricciones como interrupciones prolongadas del calendario académico, emergencias sanitarias o eventos críticos de carácter social o ambiental, docentes, gestores y profesionales deben tomar decisiones claves sobre qué y en qué secuencia se deben realizar las tareas en los sistemas productivos de bienes y servicios donde interactúan, tales como educación, salud, alimentos, energía. Estas decisiones, que combinan selección y secuenciación, son fundamentales para maximizar el impacto con recursos limitados. Desde la ingeniería industrial y la matemática aplicada, este proyecto propone una respuesta estructurada a ese desafío.
Problema
El proyecto aborda una versión extendida del clásico problema de la mochila (knapsack problem), integrando el elemento de programación temporal, es decir, no solo elegir qué ítems ingresar como contenidos, productos, tareas, sino también en qué secuencia hacerlo, ya que el valor de cada decisión depende del momento en que se ejecuta. Esta extensión, conocida como el Knapsack Problem with Scheduled Items (KPsi), aún presenta vacíos importantes en cuanto a su complejidad computacional, modelado y métodos de resolución, y requiere herramientas que integren tanto lógica algorítmica como conocimiento práctico.
Solución
La investigación propone modelos matemáticos que representen estos problemas de forma estructurada mediante ecuaciones y funciones objetivo, permitiendo su análisis y resolución. El equipo desarrollará algoritmos exactos, aproximados, heurísticos y metaheurísticos para resolver el problema KPsi, evaluando su rendimiento en distintos escenarios reales y simulados. Este enfoque técnico se complementa con la validación práctica de decisiones humanas, generando herramientas que fortalezcan los procesos de toma de decisiones.
Objetivos
1. Caracterizar problemas reales de selección y secuenciación a través del modelo KPsi.
2. Determinar su complejidad computacional y propiedades estructurales.
3. Desarrollar y evaluar métodos de resolución (exactos, aproximados, heurísticos, metaheurísticos).
4. Generalizar los resultados a distintos sectores productivos de bienes y servicios, tales como educación, salud, alimentos, energía.
5. Transferir conocimientos a estudiantes y tomadores de decisión mediante difusión académica y actividades de formación.
Beneficios
El proyecto busca desarrollar algoritmos que mejoren la toma de decisiones en contextos con recursos limitados y condiciones adversas, como interrupciones académicas o emergencias sanitarias. Sus aplicaciones incluyen la planificación curricular, la gestión de listas de espera en salud y la optimización de procesos productivos asociados a la alimentación y energía. Además, aportará al avance científico en optimización y algoritmos, y fortalecerá la formación de capital humano en programas de pre y postgrado.
