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

技術概要：ユーザー定義の提供粒度を備えたパーソナライズされた食事最適化のための混合整数目標計画

問題定義
本論文は、栄養要件を満たす食品の組み合わせを決定するという古典的なオペレーションズ・リサーチの課題である「食事問題」に取り組む。著者らは、既存の定式化における 2 つの持続的な限界を特定している。

1. 分数提供量: 標準的な線形計画法（LP）は連続変数（例：1.7 個の卵）を生成する。これは数学的に正確であるが、食事の準備には実用的ではない。既存の文献では、これを事後の丸め問題として扱うことが多く、これにより解の質が低下し、制約違反を招く可能性がある。
2. 実行不可能性: 硬制約定式化（栄養目標が厳密な不等式である場合）は、目標が矛盾するか、利用可能な食品セットが限られている場合、頻繁に解を返さない。これは、完璧な目標が達成不可能な場合でもユーザーにガイダンスが必要な対話型アプリケーションにおいて、特に問題となる。

整数計画法（IP）は粒度の問題を解決するが、通常は整数数量変数（何回分か）ではなく、バイナリ変数（含める/含めない）を使用し、硬制約に依存することが多く、実行不可能性の問題を引き継ぐ。一方、目標計画（GP）はソフト目標を通じて実行不可能性を処理するが、通常は連続変数を使用する。56 件の食事最適化論文の体系的なレビューにより、以下のギャップが明らかになった。すなわち、整数計画法と目標計画を組み合わせた先行研究は存在しない。

手法：混合整数目標計画（MIGP）
著者らは、整数提供変数とソフト目標制約を統合する混合整数目標計画（MIGP）定式化を提案する。

• 定式化: このモデルは、各食品 $i$ の提供回数を表す整数決定変数 ($x_i$) を使用する。栄養目標は、過剰達成と不足達成のための明示的な偏差変数 ($d^+_m, d^-_m$) を伴うソフト目標に変換される。
• 目的関数: このモデルは、偏差の重み付き和（MinSum 達成関数）を最小化する。カロリーと脂肪のグラム数など、異なるスケールを持つ栄養素をバランスさせるため、著者らは逆目標正規化を採用する。ここで、ペナルティ重み $w_m = 1/\max(T_m, 1)$ である。これにより、タンパク質の 0.5% の偏差とカロリーの 0.5% の偏差が同じペナルティを負うことが保証される。
• 粒度: このモデルは、ユーザー定義の提供サイズ（例：卵 1 個、油大さじ 1 杯）をサポートし、事後の丸めなしで自然な単位を可能にする。
• 実行可能性: 命題 1 は、少なくとも 1 つの食品が選択可能であれば、偏差変数が常に選択された食品と目標の間のギャップを吸収できるため、MIGP は任意の目標ベクトルと食品セットに対して常に実行可能であることを証明している。

整数性と「偏差吸収」の分析
重要な理論的貢献は、目標計画の文脈における整数性ギャップ（$\gamma$）の特性付けである。

• 偏差吸収: 整数変数を丸めることが直接目的関数を悪化させる標準的な混合整数計画法（MIP）とは異なり、MIGP には「偏差吸収」という特性がある。偏差変数はバッファ層として機能し、ソルバーが丸めコストを異なるマクロ栄養素間で再分配することを可能にし、重み付き偏差の総和を増加させない。
• シャプレイ・フォークマンの定理との関連: 著者らはこれをシャプレイ・フォークマンの定理に関連付け、$|M|$ 個の制約（4 つのマクロ栄養素）と $n$ 個の変数がある場合、高々 $|M|$ 個の変数だけが非自明な丸めを必要とすることを指摘している。
• 実証的発見: 15 種類以上の食品を含む食事サイズの場合、整数性ギャップは事実上ゼロである。すべてのベンチマーク事例において、整数解は連続最適解と一致する。ギャップは自由度が制限された小規模な事例（例：8 種類の食品）でのみ現れる。

実装と計算評価
著者らは、scipy.optimize.milp を介して HiGHS ソルバーを使用したオープンソースの Python モジュールとして MIGP を実装した。

• ベンチマーク: 30 種類の USDA 食品を用いて 9 つの構成（食品数：8、15、25 を変化；難易度：緩い、きつい、野心的）で 810 件の事例を生成した。
• 比較対象: MIGP は以下の手法と比較された。
  1. GP + 丸め: 連続 LP を解き、結果を事後に丸める。
  2. 硬制約 IP: 厳密な $\pm 5\%$ の許容範囲バンドを持つ標準的な整数計画法。
• 結果:
  • 実行可能性: MIGP はすべての事例で100% の実行可能性を達成した。硬制約 IP は事例の**51.9%**で失敗し、「野心的」な構成では完全に失敗した。
  • 解の質: MIGP は 66% のケースで GP + 丸めよりも厳密に優れた解を見つけ、決して劣ることはなかった。MIGP の中央値目的関数値（0.141）は、GP + 丸め（0.529）よりも有意に低かった。
  • パフォーマンス: 典型的な食事サイズ（8〜15 種類の食品）における求解時間は 100 ミリ秒未満に留まり、このアプローチは対話型アプリケーションにおいて実用的である。

意義と主張
本論文は、実用的な整数提供量と実行可能性の両方を保証する最初の統合モデルを提供することで、食事最適化文献において記録されたギャップを埋めると主張している。

• 実用性: 数学的最適化と現実世界の食事準備の間の断絶を排除し、直接整数提供量を出力することで、これを解消する。
• 堅牢性: 目標が達成不可能な場合でも「最善を尽くす」解を提供し、「解なし」を返すのではなく、透明性のある偏差レポートを提供する。
• 構造的洞察: この研究は、偏差吸収により、目標計画における整数性のコストが、硬制約 MIP におけるものよりも構造的に小さいことを示している。著者らは、この性質が他の資源構成問題（例：製造ブレンド、ポートフォリオ選択）にも一般化されると提案している。

著者らは範囲を控えめに保ち、モデルはマクロ栄養素と提供回数を効果的に処理するが、現時点では嗜好性、味覚の好み、または 1 日複数回の食事計画をモデル化していないが、数学的構造はこれらの拡張を可能にすると指摘している。実装は、対話型 Web アプリケーションに統合されたオープンソースモジュールとして公開されている。