Diet Optimization with Integer Programming: Goodbye to 1.7 Eggs

Fifty-six papers reviewed, none combining the two techniques that have been available separately for decades. That is what the authors of arXiv:2605.13849, published May 16, 2026, found: a systematic literature review on diet optimization reveals that no one had merged integer programming with goal programming to simultaneously tackle the two most persistent problems in the field. The practical result of that omission is as everyday as it is absurd: existing models recommend 1.7 eggs or 0.37 bananas.

It is not a minor problem. When a nutritional planning system returns impossible-to-execute fractions in a real kitchen, the usual solution is to round afterwards. But that rounding breaks optimality guarantees and can push the nutritional plan outside established margins. It is like optimizing an investment portfolio and then buying whole shares by eye.

What MIGP Proposes

The proposal is called Mixed Integer Goal Programming (MIGP) and its logic is more elegant than complex. It combines two classical operations research tools:

• Integer variables so portions are countable: one egg, one tablespoon of oil, two slices of bread. Each food has its own natural granularity defined by the user.
• Goal programming with soft deviations instead of hard constraints on nutrients. If calcium and protein targets conflict, the model does not fail: it penalizes deviations and seeks the best possible compromise.

The second point is especially relevant in clinical practice and consumer applications. Hard nutrient constraints—"exactly 2,000 kcal, exactly 50 g of protein"—frequently cause infeasibility when targets are imposed by different dietary guidelines or when the inventory of available foods is limited. Models with hard constraints simply find no solution and stop. MIGP, in contrast, always returns a plan, even if imperfect.

The authors also formally characterize what they call the deviation absorption property: the deviation variables from goal programming act as a buffer to absorb the cost of imposing integrality, making the integrality gap structurally smaller than in an equivalent MIP with hard constraints. In practical terms, this means the quality gap between the relaxed continuous solution and the actual integer solution is smaller, and therefore more computationally tractable.

Who This Helps

The most obvious case is personalized nutrition applications: from clinical tools for patients with specific conditions to meal-planning apps. But there is a less obvious angle that directly interests the AI tools ecosystem: these formulations are exactly the type of structured reasoning that LLM-based agents—including those built on Claude through sub-agents or MCP servers—need to externalize to a specialized solver.

A nutritional planning agent should not solve a MILP internally with text generation. What makes sense is for the agent to collect user preferences, translate them into model parameters, and call an external solver through a tool. MIGP provides exactly the formulation that solver needs: well-defined, with formal guarantees and interpretable output without post-processing.

The paper reports results for meals with 15 or more foods, although the public summary available at the time of writing this post does not detail full computation time benchmarks or exhaustive experimental comparisons—elements that will need review in the complete version.

Field Context

The optimal diet problem has roots in the 1940s, when George Stigler formulated the "diet problem" as a linear programming exercise. Eighty years later, the gap between academic formulation and practical utility remained notable. That in 2026 there is still room for such fundamental methodological contributions to such a well-studied problem says something about how literature tends to accumulate in variations on the same approach rather than crossing subdisciplines.

From our perspective: it is technically solid work that solves a real problem with well-combined existing tools. It needs no more merit than that.