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

Sintesi Tecnica: Programmazione a Obiettivi Interi Mista per l'Ottimizzazione Personalizzata dei Pasti con Granularità delle Porzioni Definita dall'Utente

Definizione del Problema
Il documento affronta il "Problema della Dieta", una sfida classica della ricerca operativa riguardante la determinazione delle combinazioni alimentari per soddisfare i requisiti nutrizionali. Gli autori identificano due limitazioni persistenti nelle formulazioni esistenti:

1. Porzioni Frazionarie: La Programmazione Lineare (LP) standard produce variabili continue (ad esempio, 1,7 uova), che sono matematicamente precise ma poco pratiche per la preparazione dei pasti. La letteratura esistente tratta spesso questo aspetto come un problema di arrotondamento successivo, il quale può degradare la qualità della soluzione e violare i vincoli.
2. Inammissibilità: Le formulazioni a vincoli rigidi (dove gli obiettivi nutrizionali sono disuguaglianze strette) restituiscono frequentemente nessuna soluzione quando gli obiettivi sono in conflitto o l'insieme di alimenti disponibili è limitato. Ciò è particolarmente problematico nelle applicazioni interattive in cui gli utenti necessitano di indicazioni anche quando gli obiettivi perfetti sono irraggiungibili.

Sebbene la Programmazione Interi (IP) risolva il problema della granularità, utilizza tipicamente variabili binarie (incluso/escluso) anziché variabili di quantità intera (quante porzioni) e spesso si basa su vincoli rigidi, ereditando il problema dell'inammissibilità. Al contrario, la Programmazione a Obiettivi (GP) gestisce l'inammissibilità tramite obiettivi morbidi, ma utilizza tipicamente variabili continue. Una revisione sistematica di 56 articoli sull'ottimizzazione della dieta ha rivelato un vuoto: nessun lavoro precedente combina la programmazione intera con la programmazione a obiettivi.

Metodologia: Programmazione a Obiettivi Interi Mista (MIGP)
Gli autori propongono una formulazione di Programmazione a Obiettivi Interi Mista (MIGP) che unifica le variabili intere delle porzioni con vincoli a obiettivi morbidi.

• Formulazione: Il modello utilizza variabili decisionali intere ($x_i$) che rappresentano il conteggio delle porzioni per ciascun alimento $i$. Gli obiettivi nutrizionali sono convertiti in obiettivi morbidi con variabili di deviazione esplicite ($d^+_m, d^-_m$) per il superamento e il mancato raggiungimento.
• Obiettivo: Il modello minimizza una somma pesata delle deviazioni (funzione di raggiungimento MinSum). Per bilanciare nutrienti con scale diverse (ad esempio, calorie contro grammi di grassi), gli autori impiegano la normalizzazione inversa dell'obiettivo, dove il peso della penalità $w_m = 1/\max(T_m, 1)$. Ciò garantisce che una deviazione dello 0,5% nelle proteine comporti la stessa penalità di una deviazione dello 0,5% nelle calorie.
• Granularità: Il modello supporta dimensioni delle porzioni definite dall'utente (ad esempio, 1 uovo, 1 cucchiaio di olio), consentendo unità naturali senza arrotondamento successivo.
• Ammissibilità: La Proposizione 1 dimostra che la MIGP è sempre ammissibile per qualsiasi vettore di obiettivi e insieme di alimenti (purché sia selezionabile almeno un alimento), poiché le variabili di deviazione possono sempre assorbire il divario tra gli alimenti selezionati e gli obiettivi.

Analisi dell'Interezza e "Assorbimento della Deviazione"
Un contributo teorico chiave è la caratterizzazione del gap di interezza ($\gamma$) nel contesto della Programmazione a Obiettivi.

• Assorbimento della Deviazione: A differenza della Programmazione Lineare Interi Mista (MIP) standard, dove l'arrotondamento delle variabili intere peggiora direttamente l'obiettivo, la MIGP presenta una proprietà di "assorbimento della deviazione". Le variabili di deviazione agiscono come uno strato tampone, permettendo al risolutore di ridistribuire i costi di arrotondamento tra diversi macronutrienti senza aumentare la deviazione pesata totale.
• Connessione con Shapley–Folkman: Gli autori collegano questo aspetto al teorema di Shapley–Folkman, notando che con $|M|$ vincoli (4 macronutrienti) e $n$ variabili, al massimo $|M|$ variabili richiedono un arrotondamento non banale.
• Risultato Empirico: Per dimensioni dei pasti con 15 o più alimenti, il gap di interezza è efficacemente zero; la soluzione intera corrisponde all'ottimo continuo in ogni istanza di riferimento. Il gap appare solo in istanze piccole (ad esempio, 8 alimenti) dove i gradi di libertà sono limitati.

Implementazione e Valutazione Computazionale
Gli autori hanno implementato la MIGP come modulo Python open-source utilizzando il risolutore HiGHS tramite scipy.optimize.milp.

• Benchmark: Sono state generate 810 istanze utilizzando 30 alimenti USDA in 9 configurazioni (variando il numero di alimenti: 8, 15, 25; e i livelli di difficoltà: lasco, stretto, ambizioso).
• Comparatori: La MIGP è stata confrontata con:
  1. GP + Arrotondamento: Risoluzione di una LP continua e arrotondamento dei risultati successivo.
  2. IP a Vincoli Rigidi: Programmazione intera standard con bande di tolleranza strette di $\pm 5\%$.
• Risultati:
  • Ammissibilità: La MIGP ha raggiunto il 100% di ammissibilità in tutte le istanze. L'IP a Vincoli Rigidi ha fallito nel 51,9% delle istanze (fallendo completamente nelle configurazioni "ambiziose").
  • Qualità della Soluzione: La MIGP ha trovato soluzioni strettamente migliori rispetto a GP + Arrotondamento nel 66% dei casi e non è mai stata peggiore. Il valore mediano dell'obiettivo per la MIGP (0,141) è stato significativamente inferiore rispetto a GP + Arrotondamento (0,529).
  • Prestazioni: I tempi di risoluzione sono rimasti sotto i 100 ms per dimensioni tipiche dei pasti (8–15 alimenti), rendendo l'approccio praticabile per applicazioni interattive.

Significato e Affermazioni
Il documento afferma di colmare un vuoto documentato nella letteratura sull'ottimizzazione della dieta fornendo il primo modello unificato che garantisce sia porzioni intere pratiche sia ammissibilità.

• Praticità: Elimina la discontinuità tra l'ottimizzazione matematica e la preparazione reale dei pasti restituendo direttamente porzioni intere.
• Robustezza: Fornisce una soluzione "massimo sforzo" anche quando gli obiettivi sono irraggiungibili, offrendo rapporti trasparenti sulle deviazioni invece di restituire "nessuna soluzione".
• Insight Strutturale: Il lavoro dimostra che il costo dell'interezza nella programmazione a obiettivi è strutturalmente inferiore rispetto alla MIP a vincoli rigidi grazie all'assorbimento della deviazione, una proprietà che gli autori suggeriscono si generalizza ad altri problemi di composizione delle risorse (ad esempio, miscelazione nella produzione, selezione di portafogli).

Gli autori mantengono un ambito modesto, notando che, sebbene il modello gestisca efficacemente macronutrienti e conteggi delle porzioni, non modella attualmente la palatabilità, le preferenze di gusto o la pianificazione giornaliera multi-pasto, sebbene la struttura matematica consenta tali estensioni. L'implementazione è rilasciata come modulo open-source integrato in un'applicazione web interattiva.