استرخاء البرمجة الخطية

في الرياضيات، يُعد تخفيف برنامج خطي (مختلط) للأعداد الصحيحة هو المشكلة التي تنشأ عن إزالة قيد التكامل لكل متغير.

على سبيل المثال، في برنامج عدد صحيح ثنائي (0-1) ، تكون جميع القيود على الشكل التالي:

${\displaystyle x_{i}\in \{0,1\}}$.

بدلاً من ذلك، يستخدم تخفيف برنامج الأعداد الصحيحة الأصلي مجموعة من القيود الخطية

${\displaystyle 0\leq x_{i}\leq 1.}$

ينتج عن عملية الاسترخاء برنامج خطي ، ومن هنا جاءت التسمية. تحوّل تقنية الاسترخاء هذه مسألة تحسين صعبة الحل (برمجة عددية صحيحة) إلى مسألة مشابهة قابلة للحل في وقت متعدد الحدود (برمجة خطية)؛ ويمكن استخدام حل البرنامج الخطي المسترخي للحصول على معلومات حول حل البرنامج العددي الصحيح الأصلي.

لنأخذ على سبيل المثال مسألة تغطية المجموعة ، والتي تم النظر في استرخاء البرمجة الخطية لها لأول مرة بواسطة لوفاس في عام 1975. ^{[ 1 ]} في هذه المسألة، يتم إعطاء عائلة من المجموعات F = { S ₀ , S ₁ , ...} كمدخل؛ والمهمة هي إيجاد عائلة فرعية، بأقل عدد ممكن من المجموعات، لها نفس الاتحاد مثل F.

لصياغة هذا كبرنامج عددي ثنائي (0-1)، نُنشئ متغيرًا مؤشرًا xᵢ لكل مجموعة Sᵢ _، يأخذ القيمة 1 عندما تنتمي Sᵢ إلى المجموعة الفرعية المختارة _، والقيمة 0 عندما لا تنتمي إليها. عندئذٍ، يمكن وصف غطاء صالح بتعيين قيم لمتغيرات المؤشر التي تُحقق القيود _.

${\displaystyle \textstyle x_{i}\in \{0,1\}}$

(أي أنه لا يُسمح إلا بقيم متغير المؤشر المحددة) ولكل عنصر e _j من اتحاد F ،

${\displaystyle \textstyle \sum _{\{i\mid e_{j}\in S_{i}\}}x_{i}\geq 1}$

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

${\displaystyle \textstyle \min \sum _{i}x_{i}.}$

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

كمثال محدد لمسألة تغطية المجموعات، لنفترض الحالة F = {{ a , b }, { b , c }, { a , c }}. توجد ثلاث تغطيات مثلى للمجموعات، تتضمن كل منها مجموعتين من المجموعات الثلاث المعطاة. بالتالي، فإن القيمة المثلى لدالة الهدف في برنامج الأعداد الصحيحة المقابل (0-1) هي 2، وهو عدد المجموعات في التغطيات المثلى. مع ذلك، يوجد حل كسري تُخصص فيه لكل مجموعة وزن 1/2، وتكون القيمة الإجمالية لدالة الهدف فيه 3/2. لذا، في هذا المثال، تختلف قيمة تخفيف البرمجة الخطية عن قيمة برنامج الأعداد الصحيحة (0-1) غير المُخفف.

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

في جميع الحالات، تكون جودة حل البرنامج الخطي على الأقل بمستوى جودة حل البرنامج الصحيح، لأن أي حل للبرنامج الصحيح سيكون حلاً صحيحاً للبرنامج الخطي أيضاً. أي، في مسألة تعظيم، تكون قيمة البرنامج المُخفف أكبر من أو تساوي قيمة البرنامج الأصلي، بينما في مسألة تصغير، مثل مسألة تغطية المجموعات، تكون قيمة البرنامج المُخفف أصغر من أو تساوي قيمة البرنامج الأصلي. وبالتالي، يوفر التخفيف حداً متفائلاً لحل البرنامج الصحيح.

في مثال مسألة تغطية المجموعات الموصوفة أعلاه، حيث تبلغ قيمة الحل الأمثل للحل المُخفف 3/2، نستنتج أن قيمة الحل الأمثل لبرنامج الأعداد الصحيحة غير المُخفف لا تقل عن هذه القيمة. وبما أن حلول مسألة تغطية المجموعات هي أعداد صحيحة (عدد المجموعات المختارة في المجموعة الفرعية)، فإن جودة الحل الأمثل يجب أن تكون على الأقل مساوية للعدد الصحيح الأكبر التالي، وهو 2. وبالتالي، في هذه الحالة، على الرغم من اختلاف قيمة الحل الأمثل عن قيمة الحل في المسألة غير المُخففة، فإن تخفيف البرمجة الخطية يُعطينا حدًا أدنى دقيقًا لجودة حل المسألة الأصلية.

يُعدّ استرخاء البرمجة الخطية أسلوبًا قياسيًا لتصميم خوارزميات تقريبية لمسائل التحسين المعقدة. في هذا التطبيق، يُعدّ مفهوم فجوة التكامل مفهومًا مهمًا ، وهو النسبة القصوى بين جودة حل البرنامج الصحيح واسترخاءه. في حالة مسألة تصغير، إذا كانت القيمة الصغرى الحقيقية (القيمة الصغرى للمسألة الصحيحة)${\displaystyle M_{\text{int}}}$، والحد الأدنى المُرخى (الحد الأدنى لتخفيف البرمجة الخطية) هو${\displaystyle M_{\text{frac}}}$إذن، فإن فجوة التكامل في تلك الحالة هي${\displaystyle IG={\frac {M_{\text{int}}}{M_{\text{frac}}}}}$في مسائل التعظيم، يُعكس الكسر. وتكون فجوة التكامل دائمًا 1 على الأقل. في المثال أعلاه ، تُظهر الحالة F = {{ a , b }, { b , c }, { a , c }} فجوة تكامل مقدارها 4/3.

عادةً، تُترجم فجوة التكامل إلى نسبة التقريب لخوارزمية التقريب. وذلك لأن خوارزمية التقريب تعتمد على استراتيجية تقريب معينة تجد، لكل حل مُخفف بحجم${\displaystyle M_{\text{frac}}}$، حل صحيح بحجم لا يتجاوز${\displaystyle RR\cdot M_{\text{frac}}}$(حيث RR هي نسبة التقريب). إذا وُجدت حالة بفجوة تكاملية IG ، فإن كل استراتيجية تقريب ستُعيد، في تلك الحالة، حلاً مُقرباً بحجم لا يقل عن${\displaystyle M_{\text{int}}=IG\cdot M_{\text{frac}}}$لذلك بالضرورة${\displaystyle RR\geq IG}$نسبة التقريب RR هي مجرد حد أعلى لنسبة التقريب، لذا نظريًا قد تكون نسبة التقريب الفعلية أقل من IG ، ولكن قد يصعب إثبات ذلك. عمليًا، تشير قيمة IG الكبيرة عادةً إلى أن نسبة التقريب في استرخاء البرمجة الخطية قد تكون غير دقيقة، وقد يكون من الأفضل البحث عن طرق تقريب أخرى لهذه المسألة.

في مسألة تغطية المجموعات، أثبت لوفاس أن فجوة التكامل لحالة تحتوي على n عنصرًا هي H _{_n} ، وهو العدد التوافقي النوني . يمكن تحويل استرخاء البرمجة الخطية لهذه المسألة إلى حل تقريبي لحالة تغطية المجموعات الأصلية غير المسترخية باستخدام تقنية التقريب العشوائي . ^{[ 2 ]} بافتراض وجود تغطية كسرية، حيث يكون لكل مجموعة S_{_i} وزن w_{_i} ، يتم اختيار قيمة كل متغير مؤشر ثنائي (0-1) x_{_i} عشوائيًا لتكون 1 باحتمالية w _{_i} × (ln n + 1)، و0 فيما عدا ذلك. عندئذٍ، يكون احتمال بقاء أي عنصر e_{_j} غير مغطى أقل من 1/( e × n )، وبالتالي، باحتمالية ثابتة، تكون جميع العناصر مغطاة. يبلغ الحجم الكلي للتغطية الناتجة عن هذه التقنية، باحتمالية عالية ، (1 + o(1))(ln n ) W ، حيث W هو الوزن الكلي للحل الكسري. وبالتالي، تؤدي هذه التقنية إلى خوارزمية تقريب عشوائية تجد تغطية مجموعة ضمن عامل لوغاريتمي من الحل الأمثل. كما أوضح يونغ في عام 1995 ^{[ 3 ]،} يمكن التخلص من كلٍّ من الجزء العشوائي لهذه الخوارزمية والحاجة إلى بناء حل صريح لمعادلة البرمجة الخطية باستخدام طريقة الاحتمالات الشرطية ، مما يؤدي إلى خوارزمية جشعة حتمية لتغطية المجموعات، والتي كانت معروفةً بالفعل للوفاس، حيث تقوم هذه الخوارزمية باختيار المجموعة التي تغطي أكبر عدد ممكن من العناصر المتبقية غير المغطاة بشكل متكرر. وتقارب هذه الخوارزمية الجشعة تغطية المجموعات ضمن نفس عامل H_{_n} الذي أثبته لوفاس كفجوة التكامل لتغطية المجموعات. وهناك أسباب قوية من منظور نظرية التعقيد تدعو إلى الاعتقاد بأنه لا توجد خوارزمية تقريبية ذات زمن متعدد الحدود يمكنها تحقيق نسبة تقريب أفضل بشكل ملحوظ. ^{[ 4 ]}     

يمكن استخدام تقنيات التقريب العشوائي المماثلة ، وخوارزميات التقريب غير العشوائية، جنبًا إلى جنب مع استرخاء البرمجة الخطية لتطوير خوارزميات التقريب للعديد من المشاكل الأخرى، كما وصفها راغافان وتومبسون ويونغ.

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

إذا كانت بعض المتغيرات في الحل الأمثل ذات قيم كسرية، فيمكننا البدء بعملية من نوع التفرع والتقييد ، حيث نحل بشكل متكرر مسائل فرعية تكون فيها قيم بعض المتغيرات الكسرية ثابتة عند الصفر أو الواحد. في كل خطوة من خوارزمية من هذا النوع، نعتبر مسألة فرعية من برنامج الأعداد الصحيحة الأصلي (0-1) حيث تكون قيم بعض المتغيرات إما 0 أو 1، بينما تظل المتغيرات المتبقية حرة في أخذ أي من القيمتين. في المسألة الفرعية i ، لنرمز بـ V _{_i} إلى مجموعة المتغيرات المتبقية. تبدأ العملية بالنظر في مسألة فرعية لم تُحدد فيها أي قيم للمتغيرات، حيث V _₀ هي مجموعة المتغيرات الكاملة للمسألة الأصلية. ثم، لكل مسألة فرعية i ، تُنفذ الخطوات التالية.

1. احسب الحل الأمثل لتخفيف البرمجة الخطية للمسألة الفرعية الحالية. أي، لكل متغير x _j في V _i ، نستبدل القيد الذي ينص على أن x _j يساوي 0 أو 1 بالقيد المخفف الذي ينص على أن يكون في الفترة [0,1]؛ ومع ذلك، فإن المتغيرات التي تم تعيين قيم لها بالفعل لا يتم تخفيفها.
2. إذا كان الحل المُخفف للمشكلة الفرعية الحالية أسوأ من أفضل حل صحيح تم العثور عليه حتى الآن، فارجع من هذا الفرع من البحث المتكرر.
3. إذا كان الحل المخفف يحتوي على جميع المتغيرات مضبوطة على 0 أو 1، فقم باختباره مقابل أفضل حل صحيح تم العثور عليه حتى الآن واحتفظ بأي من الحلين هو الأفضل.
4. وإلا، فليكن _xj أي متغير يُعيّن له قيمة كسرية في الحل المُخفف. كوّن مسألتين فرعيتين، إحداهما يُعيّن فيها _xj إلى 0 والأخرى يُعيّن فيها xj إلى 1؛ في كلتا المسألتين الفرعيتين، لا تزال القيم المُعيّنة لبعض المتغيرات مستخدمة، لذا تصبح مجموعة المتغيرات المتبقية Vi _\  {  xj } _. ابحث بشكل متكرر في كلتا المسألتين الفرعيتين _.

على الرغم من صعوبة إثبات الحدود النظرية لأداء الخوارزميات من هذا النوع، إلا أنها يمكن أن تكون فعالة للغاية في الممارسة العملية.

قد يمتلك برنامجان صحيحان ثنائيا القيمة (0-1) متكافئان، أي لهما نفس دالة الهدف ونفس مجموعة الحلول الممكنة، استرخاءات برمجة خطية مختلفة تمامًا: يمكن النظر إلى استرخاء البرمجة الخطية هندسيًا على أنه متعدد سطوح محدب يشمل جميع الحلول الممكنة ويستبعد جميع المتجهات الثنائية الأخرى، وتتمتع بهذا الخاصية عدد لا نهائي من متعددات السطوح المختلفة. من الناحية المثالية، يُفضل استخدام الغلاف المحدب للحلول الممكنة كاسترخاء؛ إذ أن البرمجة الخطية على هذا متعدد السطوح ستؤدي تلقائيًا إلى الحل الصحيح للبرنامج الصحيح الأصلي. مع ذلك، بشكل عام، سيكون لهذا متعدد السطوح عدد هائل من الأوجه ، وسيكون من الصعب إنشاؤه. تشكل الاسترخاءات النموذجية، مثل استرخاء مسألة تغطية المجموعة التي نوقشت سابقًا، متعدد سطوح يحتوي بدقة على الغلاف المحدب، وله رؤوس أخرى غير المتجهات الثنائية التي تحل المسألة غير المسترخية.

تستغل طريقة القطع المستوي لحل برامج الأعداد الصحيحة الثنائية (0-1)، التي طُرحت لأول مرة لمسألة البائع المتجول من قِبل دانتزيج وفولكرسون وجونسون عام 1954 ^{[ 5 ]} ، ثم عُممت لتشمل برامج أعداد صحيحة أخرى بواسطة جوموري عام 1958 ^{[ 6 ]} ، تعددَ التسهيلات الممكنة من خلال إيجاد سلسلة من التسهيلات التي تُقيد فضاء الحل بشكل أدق حتى يتم الحصول في النهاية على حل صحيح. تبدأ هذه الطريقة من أي تسهيل للبرنامج المُعطى، وتجد الحل الأمثل باستخدام مُحلل البرمجة الخطية. إذا كان الحل يُسند قيمًا صحيحة لجميع المتغيرات، فهو أيضًا الحل الأمثل للمسألة غير المُستحدثة. وإلا، يتم إيجاد قيد خطي إضافي ( مستوى قطع أو قطع ) يفصل الحل الكسري الناتج عن الغلاف المحدب للحلول الصحيحة، وتُكرر الطريقة على هذه المسألة الجديدة ذات القيود الأكثر دقة.

تتطلب هذه الطريقة أساليب خاصة بكل مسألة لإيجاد القطوع المستخدمة فيها. ومن المستحسن بشكل خاص إيجاد مستويات القطع التي تُشكّل أوجه الغلاف المحدب للحلول الصحيحة، لأن هذه المستويات هي التي تُقيّد فضاء الحلول بشكل أدق؛ إذ يوجد دائمًا مستوى قطع من هذا النوع يفصل أي حل كسري عن الحلول الصحيحة. وقد أُجريت أبحاث كثيرة حول طرق إيجاد هذه الأوجه لأنواع مختلفة من مسائل التحسين التوافقي ، في إطار التوافقية متعددة السطوح . ^{[ 7 ]}

تجمع طريقة التفرع والقطع ذات الصلة بين طريقتي القطع المستوي والتفرع والتقييد. في أي مسألة فرعية، تُطبَّق طريقة القطع المستوي حتى يتعذر إيجاد المزيد من مستويات القطع، ثم تتفرع عند أحد المتغيرات الكسرية المتبقية.

• التلوين الجزئي ، وهو أسلوب برمجة خطية لتخفيف تلوين الرسوم البيانية .
• التقريب العشوائي ، للحصول على حل للمشكلة الأصلية من حل الاسترخاء.

• آردال، كارين ؛ وايزمانتل، روبرت (1997)، "التوافقية متعددة الأوجه: ببليوغرافيا مشروحة"، ببليوغرافيات مشروحة في التحسين التوافقي (ملف PDF) ، وايلي.
• أغمون، شموئيل (1954)، "طريقة الاسترخاء للمتباينات الخطية" ، المجلة الكندية للرياضيات ، 6 : 382-392 ، doi : 10.4153/CJM-1954-037-2 ، مؤرشف من الأصل في 24 فبراير 2012 ، تم استرجاعه في 16 أبريل 2010.
• دانتزيج، جورج ؛ فولكرسون، دي آر ؛ جونسون، سيلمر (1954)، "حل مسألة البائع المتجول واسعة النطاق"، مجلة جمعية بحوث العمليات الأمريكية ، 2 (4): 393-410 ، doi : 10.1287/opre.2.4.393.
• فيج، أوريل (1998)، "عتبة ln n لتقريب تغطية المجموعة"، مجلة ACM ، 45 (4): 634-652 ، CiteSeerX 10.1.1.70.5014 ، doi : 10.1145/285055.285059 .
• جوموري، رالف إي. (1958)، "مخطط لخوارزمية لإيجاد حلول عددية صحيحة للبرامج الخطية"، نشرة الجمعية الرياضية الأمريكية ، 64 (5): 275-279 ، doi : 10.1090/S0002-9904-1958-10224-4.
• Lovász، László (1975)، “حول نسبة الأغطية المتكاملة والكسرية المثالية”، الرياضيات المنفصلة ، ​​13 (4): 383–390 ، دوى : 10.1016 / 0012-365X(75)90058-8.
• موتزكين، تي إس ؛ شونبيرج، آي جيه (1954)، "طريقة الاسترخاء للمتباينات الخطية" ، المجلة الكندية للرياضيات ، 6 : 393-404 ، doi : 10.4153/CJM-1954-038-x ، مؤرشف من الأصل في 24-02-2012 ، تم استرجاعه في 16-04-2010.
• راغافان، برابهاكار؛ طومسون، كلارك د. (1987)، "التقريب العشوائي: تقنية للخوارزميات الجيدة القابلة للإثبات والبراهين الخوارزمية"، كومبيناتوريكا ، 7 (4): 365-374 ، doi : 10.1007/BF02579324.
• يونغ، نيل إي. (1995)، "التقريب العشوائي دون حل البرنامج الخطي" ، وقائع الندوة السادسة لجمعية آلات الحوسبة وجمعية الرياضيات الصناعية والتطبيقية حول الخوارزميات المنفصلة (SODA) ، SODA '95، الصفحات 170-178 ، ISBN  9780898713497.