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

Resumo Técnico: Programação de Metas Inteira Mista para Otimização de Refeições Personalizadas com Granularidade de Porções Definida pelo Usuário

Definição do Problema
O artigo aborda o "Problema da Dieta", um desafio clássico de pesquisa operacional de determinar combinações de alimentos para satisfazer requisitos nutricionais. Os autores identificam duas limitações persistentes nas formulações existentes:

1. Porções Fracionadas: A Programação Linear (PL) padrão produz variáveis contínuas (por exemplo, 1,7 ovos), que são matematicamente precisas, mas impraticáveis para o preparo de refeições. A literatura existente frequentemente trata isso como um problema de arredondamento post-hoc, o que pode degradar a qualidade da solução e violar restrições.
2. Inviabilidade: Formulações com restrições rígidas (onde os objetivos nutricionais são desigualdades estritas) frequentemente retornam nenhuma solução quando os objetivos entram em conflito ou o conjunto de alimentos disponíveis é limitado. Isso é particularmente problemático em aplicações interativas onde os usuários precisam de orientação mesmo quando objetivos perfeitos são inatingíveis.

Embora a Programação Inteira (PI) resolva o problema de granularidade, ela tipicamente usa variáveis binárias (incluir/excluir) em vez de variáveis de quantidade inteira (quantas porções) e frequentemente depende de restrições rígidas, herdando o problema de inviabilidade. Por outro lado, a Programação de Metas (PM) lida com a inviabilidade por meio de metas flexíveis, mas tipicamente usa variáveis contínuas. Uma revisão sistemática de 56 artigos de otimização de dietas revelou uma lacuna: nenhum trabalho anterior combina programação inteira com programação de metas.

Metodologia: Programação de Metas Inteira Mista (PMIM)
Os autores propõem uma formulação de Programação de Metas Inteira Mista (PMIM) que unifica variáveis de porção inteiras com restrições de metas flexíveis.

• Formulação: O modelo usa variáveis de decisão inteiras ($x_i$) representando a contagem de porções para cada alimento $i$. Os objetivos nutricionais são convertidos em metas flexíveis com variáveis de desvio explícitas ($d^+_m, d^-_m$) para superação e submissão.
• Objetivo: O modelo minimiza uma soma ponderada de desvios (função de realização MinSum). Para equilibrar nutrientes com escalas diferentes (por exemplo, calorias vs. gramas de gordura), os autores empregam normalização inversa ao objetivo, onde o peso da penalidade $w_m = 1/\max(T_m, 1)$. Isso garante que um desvio de 0,5% em proteínas carregue a mesma penalidade que um desvio de 0,5% em calorias.
• Granularidade: O modelo suporta tamanhos de porção definidos pelo usuário (por exemplo, 1 ovo, 1 colher de sopa de óleo), permitindo unidades naturais sem arredondamento post-hoc.
• Viabilidade: A Proposição 1 prova que a PMIM é sempre viável para qualquer vetor de objetivos e conjunto de alimentos (desde que pelo menos um alimento seja selecionável), pois as variáveis de desvio podem sempre absorver a lacuna entre os alimentos selecionados e os objetivos.

Análise de Integralidade e "Absorção de Desvio"
Uma contribuição teórica chave é a caracterização da lacuna de integralidade ($\gamma$) no contexto da Programação de Metas.

• Absorção de Desvio: Diferentemente da Programação Inteira Mista (PIM) padrão, onde o arredondamento de variáveis inteiras piora diretamente o objetivo, a PMIM possui uma propriedade de "absorção de desvio". As variáveis de desvio atuam como uma camada de amortecimento, permitindo que o solucionador redistribua os custos de arredondamento entre diferentes macronutrientes sem aumentar o desvio ponderado total.
• Conexão com Shapley–Folkman: Os autores vinculam isso ao teorema de Shapley–Folkman, observando que, com $|M|$ restrições (4 macronutrientes) e $n$ variáveis, no máximo $|M|$ variáveis exigem arredondamento não trivial.
• Descoberta Empírica: Para tamanhos de refeição com 15 ou mais alimentos, a lacuna de integralidade é efetivamente zero; a solução inteira corresponde ao ótimo contínuo em todas as instâncias de referência. A lacuna aparece apenas em instâncias pequenas (por exemplo, 8 alimentos) onde os graus de liberdade são limitados.

Implementação e Avaliação Computacional
Os autores implementaram a PMIM como um módulo Python de código aberto usando o solucionador HiGHS via scipy.optimize.milp.

• Referência: 810 instâncias foram geradas usando 30 alimentos do USDA em 9 configurações (variando contagens de alimentos: 8, 15, 25; e níveis de dificuldade: frouxo, apertado, ambicioso).
• Comparadores: A PMIM foi comparada contra:
  1. PM + Arredondamento: Resolver uma PL contínua e arredondar os resultados post-hoc.
  2. PI com Restrições Rígidas: Programação inteira padrão com faixas de tolerância estritas de $\pm 5\%$.
• Resultados:
  • Viabilidade: A PMIM alcançou 100% de viabilidade em todas as instâncias. A PI com Restrições Rígidas falhou em 51,9% das instâncias (falhando completamente nas configurações "ambiciosas").
  • Qualidade da Solução: A PMIM encontrou soluções estritamente melhores que PM + Arredondamento em 66% dos casos e nunca foi pior. O valor mediano do objetivo para a PMIM (0,141) foi significativamente menor que PM + Arredondamento (0,529).
  • Desempenho: Os tempos de resolução permaneceram abaixo de 100 ms para tamanhos de refeição típicos (8–15 alimentos), tornando a abordagem viável para aplicações interativas.

Significado e Alegações
O artigo alega preencher uma lacuna documentada na literatura de otimização de dietas ao fornecer o primeiro modelo unificado que garante tanto porções inteiras práticas quanto viabilidade.

• Praticidade: Elimina a desconexão entre otimização matemática e preparo de refeições do mundo real ao outputar porções inteiras diretamente.
• Robustez: Fornece uma solução "melhor esforço" mesmo quando os objetivos são inatingíveis, oferecendo relatórios de desvio transparentes em vez de retornar "nenhuma solução".
• Insight Estrutural: O trabalho demonstra que o custo da integralidade na programação de metas é estruturalmente menor do que na PIM com restrições rígidas devido à absorção de desvio, uma propriedade que os autores sugerem generalizar para outros problemas de composição de recursos (por exemplo, mistura na manufatura, seleção de portfólio).

Os autores mantêm um escopo modesto, observando que, embora o modelo lide efetivamente com macronutrientes e contagens de porções, ele não modela atualmente palatabilidade, preferências de sabor ou planejamento diário de múltiplas refeições, embora a estrutura matemática permita essas extensões. A implementação é lançada como um módulo de código aberto integrado a um aplicativo web interativo.