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

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.

📋 한 줄 요약

**[Operations Research / Personalized Optimization]** 1.7개 달걀 같은 비현실적 분수 해와 제약 충돌로 인한 비실행 가능성을 동시에 해결하는 정수–목표 계획법(MIGP) 기반 개인 맞춤 식단 최적화 프레임워크를 제안한다.

🎯 핵심 기여도

다이어트 최적화 56편 체계적 리뷰를 통해 정수 계획(integer programming)과 목표 계획(goal programming)을 결합한 사례가 부재함을 확인하고 그 빈자리를 채움
실제 단위(달걀 1개, 기름 1큰술 등)에 맞는 정수 서빙과 다영양소 충돌을 흡수하는 soft target을 결합한 MIGP 정식화 제안
inverse-target normalization으로 다영양소 균형을 잡고, 음식별 serving granularity를 자연 단위로 설정 가능
GP 편차 변수의 deviation absorption 특성을 이론·실험적으로 분석해, 정수 제약의 비용이 일반적인 hard-constraint MIP보다 구조적으로 작음을 보임

💡 핵심 아이디어

식단 최적화의 두 고질적 문제—분수 서빙과 제약 충돌로 인한 infeasibility—를 정수 변수와 목표 편차 변수의 결합으로 동시에 해결한다. 핵심 통찰은 goal programming의 편차 변수가 정수화로 인한 손실을 흡수해 integrality gap을 줄여준다는 점이다.

🔬 기술적 접근법

**모델/방법론**: Mixed Integer Goal Programming(MIGP) 식단 최적화 모델, 오픈소스 HiGHS 솔버 사용 Python 구현
**핵심 기법**: 정수 변수 기반 자연 단위 서빙, 영양소별 soft target과 inverse-target normalization, GP 편차에 의한 integrality gap 흡수 분석

📊 주요 결과

15개 이상 음식의 식단에서 모든 벤치마크 인스턴스의 정수 해가 연속 해 최적값과 일치
810개 인스턴스(30 USDA 음식, 9 구성, 3 방법) 평가에서 MIGP가 GP+사후 반올림 대비 66%에서 더 좋은 해, 한 번도 더 나쁘지 않음, 100% feasibility 유지
hard-constraint IP는 feasibility 48%에 그침, 일반적 식단 크기에서 100 ms 이하 solve time

💭 의의 및 한계

**의의**: 영양·운영연구 양쪽 측면에서 실용 단위로 신뢰 가능한 개인 맞춤 식단 최적화 가능성을 입증, 오픈소스 모듈로 인터랙티브 앱에 통합. **한계**: 30 음식 단위의 평가 규모, 음식 가격·기호·조리시간 같은 추가 현실 제약은 향후 과제.

🚀 실용적 활용

영양사·헬스케어 앱에서 개인 맞춤 식단 자동 생성
단체급식·임상영양 분야의 실용 단위 식단 최적화
일반 운영연구의 정수+목표 결합 문제에 대한 모범 사례