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

基于用户自定义份量粒度的个性化膳食优化混合整数目标规划

Abstract: 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. 摘要： 确定如何通过饮食满足营养需求是运筹学中最古老的优化问题之一，但现有的公式存在两个长期存在的局限性：连续变量会产生不切实际的分数份量（如 1.7 个鸡蛋、0.37 根香蕉），而硬性营养约束在目标冲突时会导致问题无解。

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. 通过对 56 篇膳食优化论文的系统综述发现，目前尚无研究将整数规划与目标规划相结合来同时解决这两个问题。我们提出了用于个性化膳食优化的混合整数目标规划（MIGP）。该公式使用整数变量来表示实际的份量计数，并使用目标规划偏差来处理软性营养目标，同时采用逆目标归一化来平衡多营养素优化。

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. 每种食物的份量粒度允许使用自然单位（一个鸡蛋、一汤匙油），而无需事后四舍五入。我们刻画了目标规划背景下的整数间隙，并确定了一种偏差吸收特性：GP 偏差变量缓冲了要求整数份量所带来的成本，使得该间隙在结构上比硬约束混合整数规划（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%. 对于包含 15 种以上食物的膳食，整数解在每个基准实例中都与连续最优解相匹配。对 810 个实例（30 种美国农业部食物、9 种配置、3 种方法）进行的计算评估表明，与事后四舍五入的 GP 相比，MIGP 在 66% 的情况下能找到明显更好的解（且从未更差），同时保持了 100% 的可行性；而硬约束整数规划（IP）仅达到 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. 使用开源 HiGHS 求解器，典型膳食规模的求解时间保持在 100 毫秒以内。该实现作为一个开源 Python 模块提供，并集成到了一个交互式膳食规划应用程序中。