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

Résumé technique : Programmation par objectifs à nombres entiers mixtes pour l'optimisation personnalisée des repas avec granularité de portion définie par l'utilisateur

Définition du problème
L'article aborde le « problème du régime », un défi classique de recherche opérationnelle consistant à déterminer des combinaisons alimentaires satisfaisant des besoins nutritionnels. Les auteurs identifient deux limitations persistantes dans les formulations existantes :

1. Portions fractionnaires : La Programmation Linéaire (PL) standard produit des variables continues (par exemple, 1,7 œuf), qui sont mathématiquement précises mais peu pratiques pour la préparation des repas. La littérature existante traite souvent cela comme un problème d'arrondi a posteriori, ce qui peut dégrader la qualité de la solution et violer les contraintes.
2. Inviabilité : Les formulations à contraintes strictes (où les objectifs nutritionnels sont des inégalités strictes) retournent fréquemment aucune solution lorsque les objectifs entrent en conflit ou que l'ensemble d'aliments disponibles est limité. Cela est particulièrement problématique dans les applications interactives où les utilisateurs ont besoin de conseils même lorsque des objectifs parfaits sont inatteignables.

Bien que la Programmation en Nombres Entiers (PNE) résolve le problème de granularité, elle utilise généralement des variables binaires (inclure/exclure) plutôt que des variables de quantité entière (combien de portions) et repose souvent sur des contraintes strictes, héritant ainsi du problème d'invibilité. À l'inverse, la Programmation par Objectifs (PO) gère l'invibilité via des objectifs souples mais utilise typiquement des variables continues. Une revue systématique de 56 articles sur l'optimisation des régimes a révélé un vide : aucun travail antérieur ne combine la programmation en nombres entiers avec la programmation par objectifs.

Méthodologie : Programmation par objectifs à nombres entiers mixtes (PONIM)
Les auteurs proposent une formulation de Programmation par objectifs à nombres entiers mixtes (PONIM) qui unifie des variables de portion entières avec des contraintes d'objectifs souples.

• Formulation : Le modèle utilise des variables de décision entières ($x_i$) représentant le nombre de portions pour chaque aliment $i$. Les objectifs nutritionnels sont convertis en objectifs souples avec des variables d'écart explicites ($d^+_m, d^-_m$) pour la sur- et la sous-réalisation.
• Objectif : Le modèle minimise une somme pondérée des écarts (fonction d'atteinte MinSum). Pour équilibrer les nutriments ayant des échelles différentes (par exemple, les calories contre les grammes de matières grasses), les auteurs emploient une normalisation par l'inverse de la cible, où le poids de pénalité $w_m = 1/\max(T_m, 1)$. Cela garantit qu'un écart de 0,5 % en protéines entraîne la même pénalité qu'un écart de 0,5 % en calories.
• Granularité : Le modèle prend en charge des tailles de portions définies par l'utilisateur (par exemple, 1 œuf, 1 cuillère à soupe d'huile), permettant des unités naturelles sans arrondi a posteriori.
• Invibilité : La proposition 1 démontre que la PONIM est toujours réalisable pour tout vecteur cible et tout ensemble d'aliments (à condition qu'au moins un aliment soit sélectionnable), car les variables d'écart peuvent toujours absorber l'écart entre les aliments sélectionnés et les cibles.

Analyse de l'intégralité et « absorption des écarts »
Une contribution théorique clé est la caractérisation de l'écart d'intégralité ($\gamma$) dans le contexte de la programmation par objectifs.

• Absorption des écarts : Contrairement à la Programmation Linéaire en Nombres Entiers Mixtes (PLIM) standard où l'arrondi des variables entières aggrave directement l'objectif, la PONIM possède une propriété d'« absorption des écarts ». Les variables d'écart agissent comme une couche tampon, permettant au solveur de redistribuer les coûts d'arrondi entre différents macronutriments sans augmenter l'écart pondéré total.
• Lien avec Shapley–Folkman : Les auteurs établissent un lien avec le théorème de Shapley–Folkman, notant qu'avec $|M|$ contraintes (4 macronutriments) et $n$ variables, au plus $|M|$ variables nécessitent un arrondi non trivial.
• Résultat empirique : Pour des tailles de repas avec 15 aliments ou plus, l'écart d'intégralité est pratiquement nul ; la solution entière correspond à l'optimum continu dans chaque instance de référence. L'écart n'apparaît que dans de petites instances (par exemple, 8 aliments) où les degrés de liberté sont limités.

Implémentation et évaluation computationnelle
Les auteurs ont implémenté la PONIM comme un module Python open-source utilisant le solveur HiGHS via scipy.optimize.milp.

• Référence : 810 instances ont été générées à l'aide de 30 aliments du USDA répartis sur 9 configurations (variant les nombres d'aliments : 8, 15, 25 ; et les niveaux de difficulté : lâche, serré, ambitieux).
• Comparateurs : La PONIM a été comparée à :
  1. PO + Arrondi : Résolution d'une PL continue et arrondi des résultats a posteriori.
  2. PNE à contraintes strictes : Programmation en nombres entiers standard avec des bandes de tolérance strictes de $\pm 5\%$.
• Résultats :
  • Invibilité : La PONIM a atteint une invibilité de 100 % sur toutes les instances. La PNE à contraintes strictes a échoué sur 51,9 % des instances (échec total sur les configurations « ambitieuses »).
  • Qualité de la solution : La PONIM a trouvé des solutions strictement meilleures que la PO + Arrondi dans 66 % des cas et n'a jamais été pire. La valeur médiane de l'objectif pour la PONIM (0,141) était significativement inférieure à celle de la PO + Arrondi (0,529).
  • Performance : Les temps de résolution sont restés inférieurs à 100 ms pour des tailles de repas typiques (8–15 aliments), rendant l'approche viable pour des applications interactives.

Signification et affirmations
L'article prétend combler un vide documenté dans la littérature sur l'optimisation des régimes en fournissant le premier modèle unifié garantissant à la fois des portions entières pratiques et une invibilité.

• Praticité : Il élimine le décalage entre l'optimisation mathématique et la préparation réelle des repas en sortant directement des portions entières.
• Robustesse : Il fournit une solution « meilleurs efforts » même lorsque les objectifs sont inatteignables, offrant des rapports d'écart transparents plutôt que de retourner « aucune solution ».
• Insight structurel : Le travail démontre que le coût de l'intégralité dans la programmation par objectifs est structurellement plus faible que dans la PLIM à contraintes strictes en raison de l'absorption des écarts, une propriété que les auteurs suggèrent se généraliser à d'autres problèmes de composition de ressources (par exemple, le mélange en fabrication, la sélection de portefeuille).

Les auteurs maintiennent une portée modeste, notant que bien que le modèle gère efficacement les macronutriments et les nombres de portions, il ne modélise pas actuellement l'acceptabilité, les préférences gustatives ou la planification quotidienne multi-repas, bien que la structure mathématique permette ces extensions. L'implémentation est publiée sous forme de module open-source intégré dans une application web interactive.