برمجة الأعداد الصحيحة

برمجة الأعداد الصحيحة هي عبارة عن مسألة أمثَلة رياضية أو برنامج لدراسة الجدوى، الذي فيه بعض أو كل المتغيرات لابد ان تكون أعداد صحيحة. في كثير من الحالات هذا المصطلح يُعبِر عن البرمجة الخطية الصحيحة، التي فيها دالة الهدف والقيود تكون خطية. البرمجة الصحيحة هي مسألة غير حتمية متعددة الحدود مسائل NP صعبة. حالة خاصة: البرمجة الخطية الصحيحة تكون فيها المتغيرات المجهولة رقمية (0-1) هي مسألة حاسوبية وتُعتَبر من المسائل الحتمية متعددة الحدود.

الشكل القياسي والمتعارف عليه للبرمجة الخطية الصحيحة

البرمجة الخطية الصحيحة في الشكل المُتعارف عليه يُعبر عنها كالتالي:

${\begin{aligned}&{\text{maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\\&{\text{and}}&&\mathbf {x} \in \mathbb {Z} ,\end{aligned}}$,

والبرمجة الخطية الصحيحة بالشكل القياسي يُعبر عنها كالتالي:

${\begin{aligned}&{\text{maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&{\text{and}}&&\mathbf {x} \in \mathbb {Z} ,\end{aligned}}$

بحيث أن المُدخلات ال C , B عبارة عن متجهات وال A عباره عن مصفوفة تحتوي على قيم صحيحة لاحظ أنه مشابه للبرمجة الخطية. البرمجة الخطية الصحيحة التي ليست في الشكل القياسي يمكن تحويلها إلى الشكل القياسي [1] عن طريق حذف شرط عدم التساوي بإضافة متغير إضافي للمعادلة واستبدال المتغيرات الغير مُقيدة بالإشارة بالفرق بين متغيرين مقيدين بالإشارة.

مثال

الشكل التالي يوضح المسألة التالية:

IP polytope with LP relaxation

${\begin{aligned}\max &{\text{ }}y\\-x+y&\leq 1\\3x+2y&\leq 12\\2x+3y&\leq 12\\x,y&\geq 0\\x,y&\in \mathbb {Z} \end{aligned}}$

النقاط الصحيحة للحل هي الموضحة باللون الأحمر في الشكل المقابل بينما الخط المتقطع الأحمر يُعبِر عن شكلهم المُحدب، الذي هو عبارة عن مجسم صغير يحتوي على كل هذه النقاط. الخطوط الزرقاء مع المحاور تُعبِر عن مجسم للبرمجة الخطية البسيطة المُعطى بشروط عدم التساوي. الهدف من الأمثَلَه هو تحريك الخط الأسود المُنقَّط أعلى مايمكن بشرط أن يضل ملامس للمُجسم. نقاط الحل الأمثل لهذه المسألة هي (1,2) و (2, 2) حيث أن قيمة دالة الهدف في النقطتين السابقتين هي القيمة 2. الحل الوحيد الأمثل التي تصل فيه الدلة إلى حالة الإستقرار وتكون برمجة خطية غير مقيده هو (1.8, 2.8) حيث أن قيمة دالة الهدف في النقطة السابقة هي القيمة 2.8 لاحظ أنه إذا قرَّبنا قيمة دالة الهدف (2.8) إلى أقرب عدد صحيح (3) من الشكل نلاحظ أنه خارج منطقة الحل.

المتغيرات

البرمجة الخطية الصحيحة المختلطة: عباره عن مسألة تحتوي على متغيرات بعضها مُقيده بأن تكون صحيحة والبعض الآخر مسموح لها بأن تكون غير صحيحة. البرمجة الخطية صفر- واحد هي المسألة التي تتضمن متغيرات مُقيدة بأن تكون صفر أو واحد. لاحظ أن المتغيرات الصحيحة المحدودة يمكن أن يُعبَر عنها كخليط من المتغيرات الرقمية ، على سبيل المثال، مُعطى متغير صحيح $0\leq x\leq U$ ، المتغير يمكن أن يُعبَر عنه باستخدام $\lfloor \log _{2}U\rfloor +1$ المتغيرات الرقيمة:$x=x_{1}+2x_{2}+4x_{3}+\ldots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\rfloor +1}.$

مثال للمسائل التي يمكن صياغتها كبرمجة خطية صحيحة

العديد من المسائل يمكن صياغتها بشكل برمجة خطية صحيحة

• سفريات مندوب المبيعات [2]
• تحديد نقاط التقاطع [[Vertex_cover#ILP_formulation]|و [3]] [[:en:Vertex_cover#ILP_formulation]|]]
• مجموعة ومشاكل التغليف [[Set_packing#Integer_linear_program_formulation]|و [4]] [[:en:Set_packing#Integer_linear_program_formulation]|]]
• تحقيق الدوال المنطقية [5]

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

التطبيقات

هناك سببان رئيسيان لإستخدام المتغيرات الصحيحه عند تصميم المسائل كبرمجة خطيه

1. المتغيرات الصحيحه تمثل الكميات التي نستطيع أن نعبر عنها بأعداد صحيحه فقط، على سبيل المثال، ليس من الممكن صناعة 3.7 من السيارات
2. المتعيرات الصحيحه تمثل قرارات يجب أن تأخذ قيم صفر أو واحد.

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

التخطيط الإنتاجي

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

الجدولة الزمني

هذه المسائل تقدم خدمه في جدولة خطوط النقل، على سبيل المثال، هذه المسألة تُستخدم في مترو الأنفاق لتحديد مسارات مختلفه في أوقات محدده يتم التعامل معها من قِبَل السائقين. المتغيرات التي تؤثر على القرار تُعبر ما إذا كان السائق سوف يسلك هذا الطريق أو لا.

الخوارزميات

الطريقة البسيطة لحل مسائل البرمجة الخطية الصحيحة هي خذف القيد الذي فيه x عباره عن رقم صحيح، الحل المكافئ للبرمجة الخطية الصحيحة (يُسمى البرمجة الخطية الصحيحة الغير مقيدة [6]) وبعد ذلك يتم تقريب مدخلات الحلول لهذه المسألة. لكن ليس من الضروري أن تكون هذه هي الحلول الأمثل، ولايمكن أن تكون حتى ضمن نطاق الحل، ممكن أنها لا تحقق بعض القيود.

استخدام أحادية النمط الكاملة

بينما في الصيغة العامة الحل لمسألة البرمجة الخطية الغير مُقيدة لاتضمن بأن تكون مُثلى، لو البرمجة الخطية الصحيحة بالشكل التالي: $\max \mathbf {c} ^{\mathrm {T} }\mathbf {x}$ بحيث ان $A\mathbf {x} =\mathbf {b}$ where $A,\mathbf {b} ,$ and $\mathbf {c}$ حيث أن ال A, B, C أعداد صحيحة وال A أُحادية النمط، بعد ذلك كل الحلول الأساسية الممكنة تكون أعداد صحيحة. بناء على ذلك، الحل الناتج من طريقة التبسيط (برمجة) نضمن بأن يكون عدد صحيح. لتوضيح أن كل الحلول الأساسية الممكنة تكون أعداد صحيحة نفرض أن ال x هو حل أساسي عشوائي ضمن نطاق الحل وبما أن ال $\mathbf {x}$ يكون في نطاق الحل ونحن نعرف أن ال $\mathbf {x}$ نفرض ان $A\mathbf {x} =\mathbf {b}$. Let $\mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]$هي عبارة عن العناصر المكافئة للأعمدة الأساسية التي تُعبر عن الحلول الأساسية $\mathbf {x}$ . بتعريف الأساسيات، هناك بعض المصفوفات الجزئية المربعة B من A مع أعمدة خطية مستقلة مثال ذلك$B$ of $A$ من هنا أعمدة ال B تكون مستقلة خطية وال B مربعة، ال B لديها معكوس، وبالتالي حسب الفرض ال B أحادية النمط، وبالتالي المحددة $\det(B)=\pm 1$ وأيضا بما أن B لديها معكوس ولذلك $\mathbf {x} _{0}=B^{-1}\mathbf {b}$ بتعرف ال $B^{-1}={\frac {B^{adj}}{\det(B)}}=\pm B^{adj}$ لاحظ أن $B^{adj}$ يرمز لمقلوب [7] ال B وتكون أعداد صحيحة بسبب أن ال B أعداد صحيحة. ولذلك:${\begin{aligned}&\Rightarrow B^{-1}=\pm B^{adj}{\text{ is integral.}}\\&\Rightarrow x_{0}=B^{-1}b{\text{ is integral.}}\\&\Rightarrow {\text{Every basic feasible solution is integral.}}\end{aligned}}$ كل الحلول الأساسية الممكنة أعداد صحيحة. وبالتالي إذا المصفوفه A التابعة للبرمجة الخطية تكون أحادية النمط، بدلا عن استخدام خوارزميات البرمجة الخطية الصحيحة، الطريقة البسيطة يمكن أن تستخدم لحل البرمجة الخطية الغير مُقيدة والحل يكون عباره عن أعداد صحيحة.

الخوارزميات الدقيقة

عندما المصفوفة A لاتكون أحادية النمط، هناك تغيٌر في الخوارزميات التي تُستخدم في حل البرمجة الخطية الصحيحة بشكل دقيق. أحد أصناف الخوارزميات طرق تقاطع المستويات [8] التي تعمل على حل البرمجة الخطية الغير مقيده ومن ثم إضافة القيود الخطية التي تقود الحل بإتجاه الأعداد الصحيحة بدون إستثناء أي من نقاط الحل الصحيحة الممكنة. صنف اخر من الخوارزميات يكون متغير من الفرع والحد [[Branch_and_bound]|.علي سبيل المثال الفرع والقطع [9]] [[:en:Branch_and_bound]|]] يضم الصنفين السابقين. خوارزميات الفرع والحد تمتلك عددا من المميزات أكثر من الخوارزميات التي تستخدم فقط المستويا المتقاطعة. واحدة من ميزات هذه الخوارزميات أنها تعطينا على الأقل حل واحد صحيح بطريقة سريعة في نطاق الحل وليس من الضروري أن يكون حل أمثَل. علاوة على ذلك حلول البرمجة الخطية الغير مقيدة يمكن أن تُستخدم لتقييم أسواء حالة تٌحدد بعد الحل الناتج عن الحل الأمثل. أخيرا، طُرق الفرع والحد يمكن أن تُستخدم لكي تعطينا العديد من الحلول المُثلى Lenstra in 1983 يوضح أنه عندما يكون عدد المتغيرات ثابت، فإن البرمجة الصحيحة يمكن أن تُحل باستخدام كثيرة الحدود.

ُطرق الحدس المهنية

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

• تسلق الهضاب [10]
• تخمير محاكى
• رد الفعل للبحث الأمثل [11]
• طريقة حل المسائل الحسابية لإيجاد مسارات جديدة عن طريق الرسم [12]
• شبكة هوبفيلد

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