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

기술 요약: 사용자 정의 서빙 단위를 활용한 개인화된 식사 최적화를 위한 혼합 정수 목표 계획법

문제 정의
본 논문은 영양 요구 사항을 충족시키기 위한 식품 조합을 결정하는 고전적인 운영 연구 과제인 "식단 문제 (Diet Problem)"를 다룹니다. 저자들은 기존 수식에서 두 가지 지속적인 한계를 식별했습니다:

1. 분수 서빙: 표준 선형 계획법 (LP) 은 1.7 개의 계란과 같은 연속 변수를 생성하여 수학적으로 정확하지만 식사 준비에는 비실용적입니다. 기존 문헌은 이를 사후 반올림 문제로 간주하는 경우가 많아, 해의 품질을 저하시키고 제약 조건을 위반할 수 있습니다.
2. 실행 불가능성: 영양 목표가 엄격한 부등식인 하드 제약 수식 (Hard-constraint formulations) 은 목표가 상충되거나 사용 가능한 식품 세트가 제한될 때 해를 전혀 반환하지 않는 경우가 많습니다. 이는 완벽한 목표를 달성할 수 없더라도 사용자에게 지침이 필요한 대화형 응용 프로그램에서 특히 문제가 됩니다.

정수 계획법 (IP) 은 단위 (granularity) 문제를 해결하지만, 일반적으로 포함/제외를 나타내는 이진 변수를 사용하거나 정수 양 변수 (몇 개의 서빙) 를 사용하는 대신 하드 제약에 의존하여 실행 불가능성 문제를 물려받습니다. 반면, 목표 계획법 (GP) 은 소프트 목표를 통해 실행 불가능성을 처리하지만 일반적으로 연속 변수를 사용합니다. 56 편의 식단 최적화 논문에 대한 체계적 검토 결과, 정수 계획법과 목표 계획법을 결합한 선행 연구는 없다는 간극이 드러났습니다.

방법론: 혼합 정수 목표 계획법 (MIGP)
저자들은 정수 서빙 변수와 소프트 목표 제약을 통합하는 혼합 정수 목표 계획법 (MIGP) 수식을 제안합니다.

• 수식화: 이 모델은 각 식품 $i$에 대한 서빙 수를 나타내는 정수 결정 변수 ($x_i$) 를 사용합니다. 영양 목표는 과달성 및 미달성을 위한 명시적 편차 변수 ($d^+_m, d^-_m$) 를 가진 소프트 목표로 변환됩니다.
• 목적 함수: 모델은 편차의 가중 합 (MinSum 달성 함수) 을 최소화합니다. 칼로리와 지방 그램과 같이 서로 다른 척도를 가진 영양소를 균형 있게 조정하기 위해, 저자들은 역목표 정규화를 사용합니다. 여기서 페널티 가중치 $w_m = 1/\max(T_m, 1)$로 정의됩니다. 이는 단백질의 0.5% 편차가 칼로리의 0.5% 편차와 동일한 페널티를 받도록 보장합니다.
• 단위 (Granularity): 이 모델은 1 개의 계란, 1 큰술의 기름과 같은 사용자 정의 서빙 크기를 지원하여 사후 반올림 없이 자연스러운 단위를 허용합니다.
• 실행 가능성: 명제 1 은 편차 변수가 선택된 식품과 목표 사이의 차이를 항상 흡수할 수 있으므로, 적어도 하나의 식품이 선택 가능하다는 전제 하에 MIGP 는 모든 목표 벡터와 식품 세트에 대해 항상 실행 가능함을 증명합니다.

정수성 분석 및 "편차 흡수"
주요 이론적 기여는 목표 계획법 맥락에서의 **정수성 간격 (integrality gap, $\gamma$)**에 대한 특성화입니다.

• 편차 흡수: 정수 변수를 반올림하는 것이 목적 함수를 직접 악화시키는 표준 혼합 정수 계획법 (MIP) 과 달리, MIGP 는 "편차 흡수" 특성을 가집니다. 편차 변수는 버퍼 층 역할을 하여 솔버가 다양한 매크로 영양소에 걸쳐 반올림 비용을 재분배할 수 있게 하여 총 가중 편차를 증가시키지 않습니다.
• Shapley–Folkman 연결: 저자들은 이를 Shapley–Folkman 정리와 연결하여, $|M|$개의 제약 조건 (4 가지 매크로 영양소) 과 $n$개의 변수가 있을 때 최대 $|M|$개의 변수만 비자명한 반올림이 필요하다고 지적합니다.
• 실증적 발견: 15 개 이상의 식품으로 구성된 식사 크기에서 정수성 간격은 사실상 0 입니다. 모든 벤치마크 인스턴스에서 정수 해가 연속 최적 해와 일치합니다. 이 간격은 자유도가 제한된 작은 인스턴스 (예: 8 개의 식품) 에서만 나타납니다.

구현 및 계산적 평가
저자들은 scipy.optimize.milp를 통해 HiGHS 솔버를 사용하여 MIGP 를 오픈 소스 Python 모듈로 구현했습니다.

• 벤치마크: 30 가지 USDA 식품을 사용하여 9 가지 구성 (식품 수: 8, 15, 25; 난이도 수준: 느슨함, 엄격함, 야심적) 으로 810 개의 인스턴스를 생성했습니다.
• 비교 대상: MIGP 는 다음과 비교되었습니다:
  1. GP + 반올림: 연속 LP 를 풀고 결과를 사후에 반올림하는 방법.
  2. 하드 제약 IP: 엄격한 $\pm 5\%$ 허용 오차 대역을 가진 표준 정수 계획법.
• 결과:
  • 실행 가능성: MIGP 는 모든 인스턴스에서 100% 실행 가능성을 달성했습니다. 하드 제약 IP 는 인스턴스의 **51.9%**에서 실패했으며 (야심적인 구성에서는 완전히 실패), MIGP 는 모든 인스턴스에서 실행 가능했습니다.
  • 해의 품질: MIGP 는 66% 의 경우에서 GP + 반올림보다 엄격히 더 나은 해를 찾았으며, 결코 더 나쁘지 않았습니다. MIGP 의 중앙값 목적 함수 값 (0.141) 은 GP + 반올림 (0.529) 보다 현저히 낮았습니다.
  • 성능: 일반적인 식사 크기 (8~15 개 식품) 에 대한 해결 시간은 100ms 미만으로 유지되어 대화형 응용 프로그램에 실용적입니다.

의의 및 주장
본 논문은 실용적인 정수 서빙과 실행 가능성을 모두 보장하는 최초의 통합 모델을 제공함으로써 식단 최적화 문헌에 기록된 간극을 메웠다고 주장합니다.

• 실용성: 전체 서빙을 직접 출력함으로써 수학적 최적화와 실제 세계의 식사 준비 사이의 단절을 제거합니다.
• 강건성: 목표가 달성 불가능할 때도 "최선의 노력" 해를 제공하며, "해가 없음"을 반환하는 대신 투명한 편차 보고서를 제공합니다.
• 구조적 통찰: 이 연구는 편차 흡수 특성으로 인해 목표 계획법에서의 정수성 비용이 하드 제약 MIP 에서보다 구조적으로 작음을 보여줍니다. 저자들은 이 특성이 제조 블렌딩, 포트폴리오 선택과 같은 기타 자원 구성 문제로도 일반화된다고 제안합니다.

저자들은 모델이 매크로 영양소와 서빙 수를 효과적으로 처리하지만, 현재 맛의 매력도, 기호, 일일 다중 식사 계획은 모델링하지 않는다고 명시하며 겸손한 범위를 유지했습니다. 다만, 수학적 구조는 이러한 확장을 허용합니다. 구현체는 대화형 웹 애플리케이션에 통합된 오픈 소스 모듈로 공개되었습니다.