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

ملخص تقني: البرمجة الهدفية ذات الأعداد الصحيحة المختلطة لتحسين الوجبات الشخصية مع تحديد دقة الحصص من قبل المستخدم

تعريف المشكلة
تتناول الورقة البحثية "مشكلة النظام الغذائي" (Diet Problem)، وهي تحدٍ كلاسيكي في بحوث العمليات يتعلق بتحديد مجموعات الأطعمة التي تلبي المتطلبات الغذائية. حدد المؤلفون قصورين مستمرين في الصيغ الحالية:

1. الحصص الكسرية: تنتج البرمجة الخطية (LP) القياسية متغيرات مستمرة (مثل 1.7 بيضة)، وهي دقيقة رياضياً ولكنها غير عملية لإعداد الوجبات. غالباً ما تتعامل الأدبيات الحالية مع هذا الأمر كمسألة تقريب لاحقة، مما قد يؤدي إلى تدهور جودة الحل وانتهاك القيود.
2. عدم الإمكانية (Infeasibility): الصيغ القائمة على القيود الصارمة (حيث تكون الأهداف الغذائية عبارة عن متباينات حادة) غالباً ما تعيد نتائج "لا يوجد حل" عندما تتعارض الأهداف أو عندما تكون مجموعة الأطعمة المتاحة محدودة. هذا الأمر يمثل مشكلة خاصة في التطبيقات التفاعلية حيث يحتاج المستخدمون إلى توجيه حتى عندما تكون الأهداف المثالية غير قاب achievable (غير قابلة للتحقيق).

بينما تحل البرمجة الصحيحة (IP) مسألة الدقة، إلا أنها تعتمد عادةً على متغيرات ثنائية (إدراج/استبعاد) بدلاً من متغيرات الكمية الصحيحة (عدد الحصص)، وغالباً ما تعتمد على القيود الصارمة، مما يرث مشكلة عدم الإمكانية. وعلى النقيال، فإن البرمجة الهدفية (GP) تعالج عدم الإمكانية عبر أهداف مرنة، ولكنها تستخدم عادةً متغيرات مستمرة. ومن خلال مراجعة منهجية لـ 56 ورقة بحثية في مجال تحسين النظام الغذائي، تبين وجود فجوة: لا يوجد عمل سابق يجمع بين البرمجة الصحيحة والبرمجة الهدفية.

المنهجية: البرمجة الهدفية ذات الأعداد الصحيحة المختلطة (MIGP)
يقترح المؤلفون صيغة للبرمجة الهدفية ذات الأعداد الصحيحة المختلطة (MIGP) توحد متغيرات الحصص الصحيحة مع قيود الأهداف المرنة.

• الصيغة: يستخدم النموذج متغيرات قرار صحيحة ($x_i$) تمثل عدد حصص كل طعام ($i$). يتم تحويل الأهداف الغذائية إلى أهداف مرنة مع متغيرات انحراف صريحة ($d^+_m, d^-_m$) للزيادة أو النقصان عن الهدف.
• الهدف: يعمل النموذج على تقليل مجموع الأوزان المرجحة للانحرافات (دالة تحقيق MinSum). ولموازنة المغذيات ذات المقاييس المختلفة (مثل السعرات الحرارية مقابل جرامات الدهون)، استخدم المؤلفون التطبيع بالهدف العكسي (inverse-target normalization)، حيث يكون وزن العقوبة $w_m = 1/\max(T_m, 1)$. يضمن ذلك أن انحراف بنسبة 0.5% في البروتين يحمل نفس عقوبة الانحراف بنسبة 0.5% في السعرات الحرارية.
• الدقة (Granularity): يدعم النموذج أحجام حصص يحددها المستخدم (مثل بيضة واحدة، أو ملعقة كبيرة من الزيت)، مما يسمح بوحدات طبيعية دون الحاجة للتقريب اللاحق.
• الإمكانية (Feasibility): يثبت الاقتراح الأول (Proposition 1) أن نموذج MIGP يكون دائماً ممكناً لأي متجه أهداف ومجموعة أطعمة (بشرم أن يكون هناك طعام واحد على الأقل يمكن اختياره)، حيث يمكن لمتغيرات الانحراف دائماً استيعاب الفجوة بين الأطعبات المختارة والأهداف.

تحليل التكامل و"امتصاص الانحراف"
المساهمة النظرية الرئيسية هي توصيف فجوة التكامل ($\gamma$) في سياق البرمجة الهدفية.

• امتصاص الانحراف (Deviation Absorption): على عكس البرمجة الصحيحة المختلطة (MIP) القياسية حيث يؤدي تقريب المتغيرات الصحيحة مباشرة إلى سوء الهدف، يتميز نموذج MIGP بخاصية "امتصاص الانحراف". تعمل متغيرات الانحراف كطبقة عازلة، مما يسمح للمحلل بإعادة توزيع تكاليف التقريب عبر مختلف المغذيات الكبرى دون زيادة إجمالي الانحراف المرجح.
• الارتباط بنظرية شابلي-فولكمان (Shapley–Folkman): ربط المؤلفون هذا بالنظرية، مشيرين إلى أنه مع وجود $|M|$ من القيود (4 مغذيات كبرى) و $n$ من المتغيرات، فإن بحد أقصى $|M|$ من المتغيرات تتطلب تقريباً غير بديهي.
• النتيجة التجريبية: بالنسبة لحجم الوجبات الذي يحتوي على 15 نوعاً أو أكثر من الأطعمة، تكون فجوة التكامل صفراً فعلياً؛ حيث يتطابق الحل الصحيح مع الحل المستمر في كل حالات الاختبار. وتظهر الفجوة فقط في الحالات الصغيرة (مثل 8 أطعمة) حيث تكون درجات الحرية محدودة.

التنفيذ والتقييم الحسابي
قام المؤلفون بتنفيذ MIGP كنموذج بايثون مفتوح المصدر باستخدام محرك HiGHS عبر scipy.optimize.milp.

• الاختبار المرجعي: تم إنشاء 810 حالة باستخدام 30 نوعاً من أطعمة USDA عبر 9 تكوينات (تختلف في عدد الأطعمة: 8، 15، 25؛ وفي مستويات الصعوبة: مرنة، ضيقة، طموحة).
• المقارنات: تمت مقارنة MIGP مع:
  1. البرمجة الهدفية + التقريب (GP + Rounding): حل برنامج خطي مستمر وتقريب النتائج لاحقاً.
  2. البرمجة الصحيحة ذات القيود الصارمة (Hard-Constraint IP): البرمجة الصحيحة القياسية مع نطاقات سماحية صارمة تبلغ $\pm 5\%$.
• النتائج:
  • الإمكانية: حقق MIGP إمكانية بنسبة 100% عبر جميع الحالات. بينما فشلت البرمجة الصحيحة ذات القيود الصارمة في 51.9% من الحالات (فشلت تماماً في التكوينات "الطموحة").
  • جودة الحل: وجد MIGP حلولاً أفضل تماماً من (GP + Rounding) في 66% من الحالات، ولم يكن أسوأ منها أبداً. كانت قيمة الهدف الوسيطة لـ MIGP (0.141) أقل بكثير من (GP + Rounding) التي بلغت (0.529).
  • الأداء: ظلت أوقات الحل أقل من 100 مللي ثانية لحجم الوجبات النموذجي (8-15 نوعاً من الطعام)، مما يجعل النهج قابلاً للتطبيق في التطبيقات التفاعلية.

الأهمية والادعاءات
تدعي الورقة أنها تسد فجوة موثقة في أدبيات تحسين النظام الغذائي من خلال توفير أول نموذج موحد يضمن كلاً من الحصص الصحيحة العملية والإمكانية.

• العملية: يقضي النموذج على الانفصال بين التحسين الرياضي وإعداد الوجبات في العالم الحقيقي من خلال إخراج حصص كاملة مباشرة.
• القوة (Robustness): يوفر حلاً "بأفضل جهد ممكن" حتى عندما تكون الأهداف غير قابلة للتحقيق، ويقدم تقارير انحراف شفافة بدلاً من إرجاع "لا يوجد حل".
• الرؤية الهيكلية: توضح العمل أن تكلفة التكامل في البرمجة الهدفية أصغر هيكلياً منها في البرمجة الصحيحة ذات القيود الصارمة بسبب امتصاص الانحراف، وهي خاصية يشير المؤلفون إلى إمكانية تعميمها على مشاكل تركيب الموارد الأخرى (مثل مزج التصنيع أو اختيار المحافظ الاستثمارية).

يحافظ المؤلفون على نطاق متواضع، مشيرين إلى أنه بينما يتعامل النموذج مع المغذيات الكبرى وعدد الحصص بفعالية، فإنه لا يعالج حالياً المذاق، أو تفضيلات الطعم، أو التخطيط للوجبات المتعددة يومياً، رغم أن البنية الرياضية تسمح بهذه التوسعات. تم إصدار التنفيذ كنموذج مفتوح المصدر متكامل في تطبيق ويب تفاعلي.