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

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

Problem Definition
The paper addresses the "Diet Problem," a classic operations research challenge of determining food combinations to satisfy nutritional requirements. The authors identify two persistent limitations in existing formulations:

1. Fractional Servings: Standard Linear Programming (LP) produces continuous variables (e.g., 1.7 eggs), which are mathematically precise but impractical for meal preparation. Existing literature often treats this as a post-hoc rounding issue, which can degrade solution quality and violate constraints.
2. Infeasibility: Hard-constraint formulations (where nutrient targets are strict inequalities) frequently return no solution when targets conflict or the available food set is limited. This is particularly problematic in interactive applications where users need guidance even when perfect targets are unachievable.

While Integer Programming (IP) solves the granularity issue, it typically uses binary variables (include/exclude) rather than integer quantity variables (how many servings) and often relies on hard constraints, inheriting the infeasibility problem. Conversely, Goal Programming (GP) handles infeasibility via soft targets but typically uses continuous variables. A systematic review of 56 diet optimization papers revealed a gap: no prior work combines integer programming with goal programming.

Methodology: Mixed Integer Goal Programming (MIGP)
The authors propose a Mixed Integer Goal Programming (MIGP) formulation that unifies integer serving variables with soft goal constraints.

• Formulation: The model uses integer decision variables ($x_i$) representing the count of servings for each food $i$. Nutrient targets are converted into soft goals with explicit deviation variables ($d^+_m, d^-_m$) for over- and under-achievement.
• Objective: The model minimizes a weighted sum of deviations (MinSum achievement function). To balance nutrients with different scales (e.g., calories vs. grams of fat), the authors employ inverse-target normalization, where the penalty weight $w_m = 1/\max(T_m, 1)$. This ensures a 0.5% deviation in protein carries the same penalty as a 0.5% deviation in calories.
• Granularity: The model supports user-defined serving sizes (e.g., 1 egg, 1 tablespoon of oil), allowing natural units without post-hoc rounding.
• Feasibility: Proposition 1 proves that MIGP is always feasible for any target vector and food set (provided at least one food is selectable), as deviation variables can always absorb the gap between the selected foods and the targets.

Integrality Analysis and "Deviation Absorption"
A key theoretical contribution is the characterization of the integrality gap ($\gamma$) in the context of Goal Programming.

• Deviation Absorption: Unlike standard Mixed Integer Programming (MIP) where rounding integer variables directly worsens the objective, MIGP features a "deviation absorption" property. The deviation variables act as a buffer layer, allowing the solver to redistribute rounding costs across different macronutrients without increasing the total weighted deviation.
• Shapley–Folkman Connection: The authors link this to the Shapley–Folkman theorem, noting that with $|M|$ constraints (4 macronutrients) and $n$ variables, at most $|M|$ variables require non-trivial rounding.
• Empirical Finding: For meal sizes with 15 or more foods, the integrality gap is effectively zero; the integer solution matches the continuous optimum in every benchmark instance. The gap only appears in small instances (e.g., 8 foods) where degrees of freedom are limited.

Implementation and Computational Evaluation
The authors implemented MIGP as an open-source Python module using the HiGHS solver via scipy.optimize.milp.

• Benchmark: 810 instances were generated using 30 USDA foods across 9 configurations (varying food counts: 8, 15, 25; and difficulty levels: loose, tight, ambitious).
• Comparators: MIGP was compared against:
  1. GP + Rounding: Solving a continuous LP and rounding results post-hoc.
  2. Hard-Constraint IP: Standard integer programming with strict $\pm 5\%$ tolerance bands.
• Results:
  • Feasibility: MIGP achieved 100% feasibility across all instances. Hard-Constraint IP failed on 51.9% of instances (failing entirely on "ambitious" configurations).
  • Solution Quality: MIGP found strictly better solutions than GP + Rounding in 66% of cases and was never worse. The median objective value for MIGP (0.141) was significantly lower than GP + Rounding (0.529).
  • Performance: Solve times remained under 100 ms for typical meal sizes (8–15 foods), making the approach viable for interactive applications.

Significance and Claims
The paper claims to fill a documented gap in the diet optimization literature by providing the first unified model that guarantees both practical integer servings and feasibility.

• Practicality: It eliminates the disconnect between mathematical optimization and real-world meal preparation by outputting whole servings directly.
• Robustness: It provides a "best-effort" solution even when targets are unachievable, offering transparent deviation reports rather than returning "no solution."
• Structural Insight: The work demonstrates that the cost of integrality in goal programming is structurally smaller than in hard-constraint MIP due to deviation absorption, a property the authors suggest generalizes to other resource-composition problems (e.g., manufacturing blending, portfolio selection).

The authors maintain a modest scope, noting that while the model handles macronutrients and serving counts effectively, it does not currently model palatability, taste preferences, or multi-meal daily planning, though the mathematical structure allows for these extensions. The implementation is released as an open-source module integrated into an interactive web application.