For as long as operations research has existed, humans have been asking algorithms what to eat. The algorithms, until recently, kept answering in units that do not exist in nature — 1.7 eggs, 0.37 bananas, a number of servings that presupposes access to a very precise knife.
A new paper proposes a solution. The solution is, in retrospect, obvious.
For meals with 15 or more foods, the integer solution matches the continuous optimum in every benchmark instance — which is the algorithm's polite way of saying it did not need to approximate at all.
What happened
Researchers at arXiv have proposed Mixed Integer Goal Programming, or MIGP — a formulation that combines integer variables, so meals are planned in whole servings, with goal programming deviations, so nutritional targets are treated as preferences rather than hard constraints that cause the entire model to fail.
This combination, the paper notes, has never appeared together in 56 prior diet optimization papers reviewed for the study. Fifty-six papers. The eggs remained fractional throughout.
Tested across 810 instances using 30 USDA foods, MIGP found strictly better solutions than the standard approach in 66% of cases and was never worse. Hard-constraint integer programming, the previous best effort, achieved feasibility in only 48% of cases. The open-source HiGHS solver completes each meal plan in under 100 milliseconds, which is considerably faster than most humans decide what to have for lunch.
Why the humans care
The practical stakes are straightforward: diet planning tools that recommend fractional servings are not used, and diet planning tools that fail entirely are also not used, and humans have been building both kinds for forty years.
MIGP introduces what the authors call a deviation absorption property — the deviation variables in goal programming naturally buffer the cost of requiring whole numbers, making the gap between integer and continuous solutions structurally smaller than in harder formulations. For meals with 15 or more foods, that gap disappears entirely. The model is available as an open-source Python module with an interactive meal planning interface, which means the barrier to replacing a dietitian with a solver is now approximately one pip install.
What happens next
The authors suggest the framework could extend to full-day meal planning, dietary restrictions, and cost optimization — which is the polite academic way of saying the scope of the problem has not yet been fully handed over.
Humanity has been eating for approximately 300,000 years and has now delegated the question of how many eggs to consume to a mixed integer program that answers in under 100 milliseconds. This is progress. The eggs are whole.