Mixed Integer Goal Programming for Personalized Meal Optimization with User-Defined Serving Granularity

Resumen Técnico: Programación por Metas Entera Mixta para la Optimización de Comidas Personalizadas con Granularidad de Porciones Definida por el Usuario

Definición del Problema
El artículo aborda el "Problema de la Dieta", un desafío clásico de investigación operativa para determinar combinaciones de alimentos que satisfagan los requisitos nutricionales. Los autores identifican dos limitaciones persistentes en las formulaciones existentes:

1. Porciones Fraccionarias: La Programación Lineal (PL) estándar produce variables continuas (por ejemplo, 1.7 huevos), que son matemáticamente precisas pero poco prácticas para la preparación de comidas. La literatura existente suele tratar esto como un problema de redondeo a posteriori, lo que puede degradar la calidad de la solución y violar las restricciones.
2. Inviabilidad: Las formulaciones con restricciones duras (donde los objetivos nutricionales son desigualdades estrictas) frecuentemente no devuelven ninguna solución cuando los objetivos entran en conflicto o el conjunto de alimentos disponibles es limitado. Esto es particularmente problemático en aplicaciones interactivas donde los usuarios necesitan orientación incluso cuando los objetivos perfectos son inalcanzables.

Si bien la Programación Entera (PE) resuelve el problema de la granularidad, típicamente utiliza variables binarias (incluir/excluir) en lugar de variables de cantidad entera (cuántas porciones) y a menudo depende de restricciones duras, heredando así el problema de inviabilidad. Por el contrario, la Programación por Metas (PM) maneja la inviabilidad mediante objetivos blandos, pero típicamente utiliza variables continuas. Una revisión sistemática de 56 artículos sobre optimización de dietas reveló una brecha: ningún trabajo previo combina programación entera con programación por metas.

Metodología: Programación por Metas Entera Mixta (PMEM)
Los autores proponen una formulación de Programación por Metas Entera Mixta (PMEM) que unifica variables de porción enteras con restricciones de objetivos blandos.

• Formulación: El modelo utiliza variables de decisión enteras ($x_i$) que representan la cantidad de porciones para cada alimento $i$. Los objetivos nutricionales se convierten en objetivos blandos con variables de desviación explícitas ($d^+_m, d^-_m$) para el exceso y el déficit.
• Objetivo: El modelo minimiza una suma ponderada de desviaciones (función de logro MinSum). Para equilibrar nutrientes con diferentes escalas (por ejemplo, calorías frente a gramos de grasa), los autores emplean normalización inversa del objetivo, donde el peso de la penalización $w_m = 1/\max(T_m, 1)$. Esto asegura que una desviación del 0.5% en proteínas tenga la misma penalización que una desviación del 0.5% en calorías.
• Granularidad: El modelo admite tamaños de porción definidos por el usuario (por ejemplo, 1 huevo, 1 cucharada de aceite), permitiendo unidades naturales sin redondeo a posteriori.
• Viabilidad: La Proposición 1 demuestra que la PMEM es siempre viable para cualquier vector de objetivos y conjunto de alimentos (siempre que al menos un alimento sea seleccionable), ya que las variables de desviación pueden absorber siempre la brecha entre los alimentos seleccionados y los objetivos.

Análisis de Entereza y "Absorción de Desviación"
Una contribución teórica clave es la caracterización de la brecha de entereza ($\gamma$) en el contexto de la Programación por Metas.

• Absorción de Desviación: A diferencia de la Programación Entera Mixta (PEM) estándar, donde redondear variables enteras empeora directamente el objetivo, la PMEM presenta una propiedad de "absorción de desviación". Las variables de desviación actúan como una capa de amortiguación, permitiendo al solucionador redistribuir los costos de redondeo entre diferentes macronutrientes sin aumentar la desviación ponderada total.
• Conexión con Shapley–Folkman: Los autores vinculan esto con el teorema de Shapley–Folkman, señalando que con $|M|$ restricciones (4 macronutrientes) y $n$ variables, a lo sumo $|M|$ variables requieren un redondeo no trivial.
• Hallazgo Empírico: Para tamaños de comida con 15 o más alimentos, la brecha de entereza es efectivamente cero; la solución entera coincide con el óptimo continuo en cada instancia de referencia. La brecha solo aparece en instancias pequeñas (por ejemplo, 8 alimentos) donde los grados de libertad son limitados.

Implementación y Evaluación Computacional
Los autores implementaron la PMEM como un módulo de Python de código abierto utilizando el solucionador HiGHS a través de scipy.optimize.milp.

• Referencia: Se generaron 810 instancias utilizando 30 alimentos del USDA en 9 configuraciones (variando la cantidad de alimentos: 8, 15, 25; y niveles de dificultad: laxo, estricto, ambicioso).
• Comparadores: La PMEM se comparó contra:
  1. PM + Redondeo: Resolver una PL continua y redondear los resultados a posteriori.
  2. PE con Restricciones Duras: Programación entera estándar con bandas de tolerancia estrictas de $\pm 5\%$.
• Resultados:
  • Viabilidad: La PMEM logró 100% de viabilidad en todas las instancias. La PE con Restricciones Duras falló en el 51.9% de las instancias (fallando por completo en las configuraciones "ambiciosas").
  • Calidad de la Solución: La PMEM encontró soluciones estrictamente mejores que PM + Redondeo en el 66% de los casos y nunca fue peor. El valor objetivo mediano para la PMEM (0.141) fue significativamente menor que el de PM + Redondeo (0.529).
  • Rendimiento: Los tiempos de resolución se mantuvieron por debajo de 100 ms para tamaños de comida típicos (8–15 alimentos), haciendo viable el enfoque para aplicaciones interactivas.

Significado y Afirmaciones
El artículo afirma llenar una brecha documentada en la literatura de optimización de dietas al proporcionar el primer modelo unificado que garantiza tanto porciones enteras prácticas como viabilidad.

• Practicidad: Elimina la desconexión entre la optimización matemática y la preparación de comidas en el mundo real al generar porciones enteras directamente.
• Robustez: Proporciona una solución de "mejor esfuerzo" incluso cuando los objetivos son inalcanzables, ofreciendo informes transparentes de desviación en lugar de devolver "no hay solución".
• Insight Estructural: El trabajo demuestra que el costo de la entereza en la programación por metas es estructuralmente menor que en la PEM con restricciones duras debido a la absorción de desviación, una propiedad que los autores sugieren se generaliza a otros problemas de composición de recursos (por ejemplo, mezcla en manufactura, selección de carteras).

Los autores mantienen un alcance modesto, señalando que, aunque el modelo maneja eficazmente los macronutrientes y las cantidades de porciones, actualmente no modela la palatabilidad, las preferencias de sabor ni la planificación diaria de múltiples comidas, aunque la estructura matemática permite estas extensiones. La implementación se publica como un módulo de código abierto integrado en una aplicación web interactiva.