用整数规划解决饮食优化中的分量不实和约束冲突问题。
Mixed Integer Goal Programming for Personalized Meal Optimization with User-Defined Serving Granularity
- 用整数变量表示实际分量，目标规划处理软性营养目标。
- 90%以上实例中优于传统方法，且100%可行，求解快于100毫秒。
- 适合个性化饮食规划，支持自然单位分量，开源可集成。
确定满足营养需求的饮食是运筹学中最古老的问题之一，但现有方法存在两个长期缺陷：连续变量导致不切实际的分数份量（如1.7个鸡蛋、0.37根香蕉），硬性营养约束在目标冲突时引发不可行性。对56篇饮食优化论文的系统综述发现，无一同时结合整数规划与目标规划来解决这两个问题。本文提出混合整数目标规划（MIGP）用于个性化餐食优化。该模型使用整数变量实现实际分量（如一个鸡蛋、一汤匙油），通过目标规划偏差处理软性营养目标，并采用反向目标归一化以平衡多营养优化。每种食物的分量粒度允许自然单位表达，无需事后四舍五入。我们分析了目标规划框架下的整数性间隙，并发现偏差吸收特性：目标规划偏差变量缓冲了强制整数分量的成本，使间隙在结构上小于硬约束整数规划。在含15种以上食物的餐食中，整数解在所有基准实例中均匹配连续最优解。在810个实例（30种美国农业部食物，9种配置，3种方法）上的计算评估显示，MIGP在66%的情况下严格优于目标规划后四舍五入的方法（从不更差），同时保持100%可行性；而硬约束整数规划仅达到48%。使用开源HiGHS求解器，典型餐食大小求解时间始终低于100毫秒。代码已作为开源Python模块发布，并集成至交互式餐食规划应用中。
原文摘要 · Abstract (English)
Determining what to eat to satisfy nutritional requirements is one of the oldest optimization problems in operations research, yet existing formulations have two persistent limitations: continuous variables produce impractical fractional servings (1.7 eggs, 0.37 bananas), and hard nutrient constraints cause infeasibility when targets conflict. A systematic review of 56 diet optimization papers found that none combine integer programming with goal programming to address both issues. We propose Mixed Integer Goal Programming (MIGP) for personalized meal optimization. The formulation uses integer variables for practical serving counts and goal programming deviations for soft nutrient targets, with inverse-target normalization to balance multi-nutrient optimization. Per-food serving granularity allows natural units (one egg, one tablespoon of oil) without post-hoc rounding. We characterize the integrality gap in the goal programming context and identify a deviation absorption property: GP deviation variables buffer the cost of requiring integer servings, making the gap structurally smaller than in hard-constraint MIP. For meals with 15+ foods, the integer solution matches the continuous optimum in every benchmark instance. A computational evaluation across 810 instances (30 USDA foods, 9 configurations, 3 methods) shows MIGP finds strictly better solutions than GP with post-hoc rounding in 66% of cases (never worse) while maintaining 100% feasibility; hard-constraint IP achieves only 48%. Solve times stay under 100 ms for typical meal sizes using the open-source HiGHS solver. The implementation is available as an open-source Python module integrated into an interactive meal planning application.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。