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

📅 آخر تحديث: ١٩ يوليو ٢٠٢٦
✍️ نُشر في: ١٩ يوليو ٢٠٢٦
📷 يحتوي على 54 صور
الموسوعة الحرة

تُعرف مسألة البرمجة العددية الصحيحة ، أو ما يُسمى أيضًا بتحسين الأعداد الصحيحة ، [ 1 ] بأنها مسألة تحسين رياضي أو برنامج جدوى تُقيد فيه بعض المتغيرات أو جميعها لتكون أعدادًا صحيحة . في كثير من السياقات، يشير المصطلح إلى البرمجة الخطية الصحيحة (ILP)، حيث تكون دالة الهدف والقيود (باستثناء قيود الأعداد الصحيحة) خطية .

تُعدّ البرمجة العددية مسألةً كاملةً من فئة NP [ 2 ] (ويكمن الجزء الصعب في إثبات انتماء المسألة إلى فئة NP [ 3 ] ). وعلى وجه الخصوص، تُعتبر الحالة الخاصة للبرمجة الخطية العددية الثنائية (0-1)، حيث تكون المجاهيل ثنائية، ولا يلزم سوى استيفاء القيود، إحدى مسائل كارب الـ 21 الكاملة من فئة NP . [ 4 ]

إذا لم تكن بعض متغيرات القرار منفصلة، ​​فإن المشكلة تُعرف باسم مشكلة البرمجة الخطية المختلطة . [ 5 ]

الشكل القانوني والقياسي لبرامج التعلم الذاتي

يمكن التعبير عن البرامج الخطية الصحيحة إما بالصيغة المعيارية أو الصيغة القياسية (كما هو موضح أدناه)، وهما مختلفتان عن بعضهما البعض. يُعبَّر عن البرنامج الخطي الصحيح بالصيغة المعيارية على النحو التالي (لاحظ أنها الصيغة القياسية).x{\displaystyle \mathbf {x} }المتجه الذي سيتم تحديده): [ 6 ]

أقصىx∈Zنجتيxرهناً بـأx≤ب،x≥0{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}}

ويُعبّر عن نموذج البرمجة الخطية الصحيحة (ILP) في شكله القياسي كما يلي:

أقصىx∈Zنجتيxرهناً بـأx+s=ب،s≥0،x≥0،{\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\end{aligned}}}

أينج∈Rن،ب∈Rم{\displaystyle \mathbf {c} \in \mathbb {R} ^{n},\mathbf {b} \in \mathbb {R} ^{m}} هي متجهات وأ∈Rم×ن{\displaystyle A\in \mathbb {R} ^{m\times n}}هي مصفوفة. وكما هو الحال مع البرامج الخطية، يمكن تحويل برامج البرمجة الخطية غير القياسية إلى صيغة قياسية عن طريق حذف المتباينات، وإدخال متغيرات الركود (s{\displaystyle \mathbf {s} }) واستبدال المتغيرات غير المقيدة بالإشارة بفرق متغيرين مقيدين بالإشارة.

مثال

متعدد السطوح IP مع استرخاء LP

يوضح الرسم البياني على اليمين المشكلة التالية.

أقصىx،y∈Zyرهناً بـ-x+y≤13x+2y≤122x+3y≤12x،y≥0{\displaystyle {\begin{aligned}{\underset {x,y\in \mathbb {Z} }{\text{maximize}}}\quad &y\\{\text{subject to}}\quad &-x+y\leq 1\\&3x+2y\leq 12\\&2x+3y\leq 12\\&x,y\geq 0\end{aligned}}}

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

إثبات صعوبة NP

فيما يلي اختزال من الحد الأدنى لتغطية الرؤوس إلى البرمجة العددية الصحيحة والتي ستكون بمثابة دليل على صعوبة NP.

يتركجي=(V،هـ){\displaystyle G=(V,E)}ليكن رسمًا بيانيًا غير موجه. عرّف برنامجًا خطيًا كما يلي:

مين∑v∈Vyvyv+yu≥1∀u،v∈هـyv∈Z0+∀v∈V{\displaystyle {\begin{aligned}\min \sum _{v\in V}y_{v}\\y_{v}+y_{u}&\geq 1&&\forall u,v\in E\\y_{v}&\in \mathbb {Z_{0}^{+}} &&\forall v\in V\end{aligned}}}

أي حل ممكن لبرنامج الأعداد الصحيحة سيكون غير صفري على مجموعة جزئية من الرؤوس. يشير القيد الأول إلى أن نقطة نهاية واحدة على الأقل من كل حافة تقع ضمن هذه المجموعة الجزئية. لذلك، يصف الحل غطاءً للرؤوس. بالإضافة إلى ذلك، إذا كان لدينا غطاء رؤوس C،yv{\displaystyle y_{v}}يمكن ضبطه على 1 لأيv∈ج{\displaystyle v\in C}وإلى صفر لأيv∉ج{\displaystyle v\not \in C}وبذلك نحصل على حل ممكن لبرنامج الأعداد الصحيحة. ومن ثم نستنتج أنه إذا قمنا بتقليل مجموعyv{\displaystyle y_{v}}لقد وجدنا أيضًا الحد الأدنى لتغطية الرؤوس. [ 7 ]

المتغيرات

تتضمن البرمجة الخطية المختلطة ( MILP ) مشاكل يكون فيها بعض المتغيرات فقط،xأنا{\displaystyle x_{i}}، مقيدة بأن تكون أعدادًا صحيحة، بينما يُسمح للمتغيرات الأخرى بأن تكون أعدادًا غير صحيحة.

تتضمن البرمجة الخطية الثنائية (أو البرمجة العددية الثنائية ) مسائل تكون فيها المتغيرات محصورة بين 0 أو 1. ويمكن التعبير عن أي متغير عددي محدود كمجموعة من المتغيرات الثنائية . [ 8 ] على سبيل المثال، إذا كان لدينا متغير عددي،0≤x≤يو{\displaystyle 0\leq x\leq U}يمكن التعبير عن المتغير باستخدام⌊سجل2⁡يو⌋+1{\displaystyle \lfloor \log _{2}U\rfloor +1}المتغيرات الثنائية:

x=x1+2x2+4x3+⋯+2⌊سجل2⁡يو⌋x⌊سجل2⁡يو⌋+1.{\displaystyle x=x_{1}+2x_{2}+4x_{3}+\cdots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\rfloor +1}.}

التطبيقات

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

  1. تمثل بعض المتغيرات العددية كميات لا يمكن أن تكون إلا أعدادًا صحيحة. على سبيل المثال، لا يمكن بناء 3.7 سيارة.
  2. تمثل المتغيرات العددية الأخرى القرارات (مثل ما إذا كان سيتم تضمين حافة في الرسم البياني ) وبالتالي يجب أن تأخذ القيمة 0 أو 1 فقط.

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

خطة الإنتاج

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

الجدولة

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

التقسيم الإقليمي

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

شبكات الاتصالات

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

الشبكات الخلوية

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

تطبيقات أخرى

الخوارزميات

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

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

على الرغم من أنه بشكل عام لا يُضمن أن يكون حل استرخاء البرمجة الخطية متكاملاً، إلا أنه إذا كانت البرمجة الخطية الصحيحة تأخذ الشكل التاليالأعلىجتيx{\displaystyle \max \mathbf {c} ^{\mathrm {T} }\mathbf {x} }بحيثأx=ب{\displaystyle A\mathbf {x} =\mathbf {b} }أينأ{\displaystyle A}وب{\displaystyle \mathbf {b} }جميع المدخلات أعداد صحيحة وأ{\displaystyle A}إذا كانت الدالة أحادية القيمة تمامًا ، فإن كل حل أساسي ممكن يكون صحيحًا. وبالتالي، فإن الحل الذي تُرجعه خوارزمية السمبلكس يكون صحيحًا. لإثبات أن كل حل أساسي ممكن يكون صحيحًا، لنفترضx{\displaystyle \mathbf {x} }ليكن حلاً أساسياً ممكناً عشوائياً.x{\displaystyle \mathbf {x} }إذا كان ذلك ممكناً، فنحن نعلم ذلك.أx=ب{\displaystyle A\mathbf {x} =\mathbf {b} }. يتركx0=[xن1،xن2،⋯،xنج]{\displaystyle \mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]}لتكن العناصر المقابلة لأعمدة الأساس للحل الأساسيx{\displaystyle \mathbf {x} }بحسب تعريف الأساس، توجد مصفوفة فرعية مربعة ماب{\displaystyle B}ل أ{\displaystyle A}بأعمدة مستقلة خطيًا بحيثبx0=ب{\displaystyle B\mathbf {x} _{0}=\mathbf {b} }.

منذ أعمدةب{\displaystyle B}مستقلة خطيًا وب{\displaystyle B}مربع،ب{\displaystyle B}هي غير منفردة، وبالتالي، بافتراض ذلك،ب{\displaystyle B}هو أحادي الوحدة ، وبالتاليالمحقق(ب)=±1{\displaystyle \det(B)=\pm 1}أيضًا، بما أنب{\displaystyle B}إذا كانت غير منفردة، فهي قابلة للعكس، وبالتاليx0=ب-1ب{\displaystyle \mathbf {x} _{0}=B^{-1}\mathbf {b} }بحسب التعريف،ب-1=بأدجالمحقق(ب)=±بأدج{\displaystyle B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }}. هنابأدج{\displaystyle B^{\mathrm {adj} }}يشير إلى المرافق لـب{\displaystyle B}وهو أمر أساسي لأنب{\displaystyle B}وهو أمر أساسي. لذلك، ⇒ب-1=±بأدج جزء لا يتجزأ.⇒x0=ب-1ب جزء لا يتجزأ.⇒كل حل أساسي ممكن هو حل متكامل.{\displaystyle {\begin{aligned}&\Rightarrow B^{-1}=\pm B^{\mathrm {adj} }{\text{ is integral.}}\\&\Rightarrow \mathbf {x} _{0}=B^{-1}b{\text{ is integral.}}\\&\Rightarrow {\text{Every basic feasible solution is integral.}}\end{aligned}}} وبالتالي، إذا كانت المصفوفةأ{\displaystyle A}إذا كان برنامج ILP أحادي الوحدة تمامًا، فبدلاً من استخدام خوارزمية ILP، يمكن استخدام طريقة سيمبلكس لحل استرخاء LP وسيكون الحل عددًا صحيحًا.

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

عندما تكون المصفوفةأ{\displaystyle A}على الرغم من أن البرمجة الخطية ليست أحادية النمط تمامًا، إلا أن هناك مجموعة متنوعة من الخوارزميات التي يمكن استخدامها لحل برامج البرمجة الخطية الصحيحة بدقة. ومن بين هذه الخوارزميات، طرق القطع المستوية ، التي تعمل عن طريق حل استرخاء البرمجة الخطية ثم إضافة قيود خطية تدفع الحل نحو أن يكون صحيحًا دون استبعاد أي نقاط ممكنة صحيحة.

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

خوارزميات دقيقة لعدد صغير من المتغيرات

يفترضأ{\displaystyle A}هي مصفوفة أعداد صحيحة من الرتبة m × n وب{\displaystyle \mathbf {b} }هو متجه صحيح ذو أبعاد m × 1. نركز على مسألة الجدوى، وهي تحديد ما إذا كان يوجد متجه ذو أبعاد n × 1x{\displaystyle \mathbf {x} }مُرضٍأx≤ب{\displaystyle A\mathbf {x} \leq \mathbf {b} }.

ليكن V القيمة المطلقة القصوى للمعاملات فيأ{\displaystyle A} وب{\displaystyle \mathbf {b} }إذا كان n (عدد المتغيرات) ثابتًا، فيمكن حل مسألة الجدوى في وقت متعدد الحدود بالنسبة إلى m و log V. وهذا بديهي في حالة n = 1. أما حالة n = 2 فقد حُلت عام 1981 بواسطة هربرت سكارف . [ 16 ] وحُلت الحالة العامة عام 1983 بواسطة هندريك لينسترا ، جامعًا أفكار لازلو لوفاس وبيتر فان إمده بواس . [ 17 ] وتنص نظرية دويغنون على أن برنامجًا صحيحًا يكون قابلاً للحل عندما تكون كل مجموعة جزئية من2ن{\displaystyle 2^{n}}القيود ممكنة؛ ويمكن استخدام طريقة تجمع هذه النتيجة مع خوارزميات لمسائل البرمجة الخطية لحل برامج الأعداد الصحيحة في وقت خطي فيم{\displaystyle m}و ذات المعاملات الثابتة القابلة للمعالجة (FPT) فين{\displaystyle n}، ولكن ربما يكون النمو الأسي مضاعفًا فين{\displaystyle n}، دون الاعتماد علىV{\displaystyle V}[ 18 ]​

في الحالة الخاصة لبرمجة الأعداد الصحيحة الثنائية (0-1 ILP)، تُكافئ خوارزمية لينسترا التعداد الكامل: حيث يكون عدد جميع الحلول الممكنة ثابتًا (2^ n )، ويمكن التحقق من جدوى كل حل في زمن poly( m , log V ). أما في الحالة العامة، حيث يمكن أن يكون كل متغير عددًا صحيحًا كيفيًا، فإن التعداد الكامل يصبح مستحيلاً. هنا، تستخدم خوارزمية لينسترا أفكارًا من هندسة الأعداد . فهي تُحوّل المسألة الأصلية إلى مسألة مكافئة لها الخاصية التالية: إما وجود حل أو عدمه.x{\displaystyle \mathbf {x} }واضح، أو قيمةxن{\displaystyle x_{n}}( المتغير رقم n ) ينتمي إلى فترة طولها محدود بدالة لـ n . في هذه الحالة، تُختزل المسألة إلى عدد محدود من المسائل ذات الأبعاد المنخفضة. وقد تم تحسين تعقيد وقت تشغيل الخوارزمية على عدة مراحل:

  • كانت الخوارزمية الأصلية لـ Lenstra [ 17 ] تحتوي على وقت تشغيل2يا(ن3)⋅(م⋅سجل⁡V)يا(1){\displaystyle 2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}}.
  • قدم كانان [ 19 ] خوارزمية محسنة مع وقت التشغيلنيا(ن)⋅(م⋅سجل⁡V)يا(1){\displaystyle n^{O(n)}\cdot (m\cdot \log V)^{O(1)}}[ 20 ]​
  • قدم فرانك وتاردوس [ 21 ] خوارزمية محسنة مع وقت تشغيل ن2.5ن⋅2يا(ن)⋅(م⋅سجل⁡V)يا(1){\displaystyle n^{2.5n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}[ 22 ] [ 23 ] : الاقتراح 8
  • قدم دادوش [ 24 ] خوارزمية محسنة مع وقت التشغيلنن⋅2يا(ن)⋅(م⋅سجل⁡V)يا(1){\displaystyle n^{n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}.
  • قدم ريس وروثفوس [ 25 ] خوارزمية محسنة مع وقت تشغيل(سجل⁡ن)يا(ن)⋅(م⋅سجل⁡V)يا(1){\displaystyle (\log n)^{O(n)}\cdot (m\cdot \log V)^{O(1)}}.

يمكن استخدام هذه الخوارزميات أيضًا في برامج البرمجة الخطية المختلطة (MILP) - وهي برامج تكون فيها بعض المتغيرات أعدادًا صحيحة وبعضها الآخر أعدادًا حقيقية. [ 26 ] خوارزمية لينسترا الأصلية [ 17 ] : القسم 5 له وقت تشغيل2يا(ن3)⋅صoلy(د،ل){\displaystyle 2^{O(n^{3})}\cdot poly(d,L)}حيث n هو عدد المتغيرات الصحيحة، وd هو عدد المتغيرات المستمرة، و L هو حجم الترميز الثنائي للمسألة. باستخدام تقنيات من خوارزميات لاحقة، فإن العامل2يا(ن3){\displaystyle 2^{O(n^{3})}}يمكن تحسينه إلى2يا(نسجل⁡ن){\displaystyle 2^{O(n\log n)}}أو إلىنن{\displaystyle n^{n}}[ 26 ]​

الأساليب الاستدلالية

نظرًا لأن البرمجة الخطية الصحيحة تُصنف ضمن مسائل NP-hard ، فإن العديد من حالاتها يصعب حلها، لذا يجب استخدام الطرق الاستدلالية. على سبيل المثال، يمكن استخدام البحث المحظور لإيجاد حلول لمسائل البرمجة الخطية الصحيحة. [ 27 ] ولحل هذه المسائل باستخدام البحث المحظور، تُعرَّف الحركات بأنها زيادة أو إنقاص قيمة متغير مقيد صحيح في حل ممكن، مع الحفاظ على ثبات جميع المتغيرات الأخرى المقيدة صحيحة. ثم تُحسب قيمة المتغيرات غير المقيدة. تتكون الذاكرة قصيرة المدى من الحلول التي جُرِّبت سابقًا، بينما تتكون الذاكرة متوسطة المدى من قيم المتغيرات المقيدة صحيحة التي أسفرت عن قيم عالية للدالة الهدف (بافتراض أن مسألة البرمجة الخطية الصحيحة هي مسألة تعظيم). وأخيرًا، توجه الذاكرة طويلة المدى البحث نحو قيم صحيحة لم تُجرَّب من قبل.

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

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

البرمجة العددية المتفرقة

غالباً ما يكون الأمر كذلك بالنسبة للمصفوفةأ{\displaystyle A}تُعرّف المصفوفة التي تُعرّف برنامج الأعداد الصحيحة بأنها مصفوفة متفرقة . ويحدث هذا تحديدًا عندما تكون للمصفوفة بنية كتلية ، وهو الحال في العديد من التطبيقات. ويمكن قياس تفرق المصفوفة كما يلي: رسم بياني لـأ{\displaystyle A}يحتوي على رؤوس تتوافق مع أعمدة منأ{\displaystyle A}ويشكل عمودان حافة إذاأ{\displaystyle A}يحتوي على صف تكون فيه قيم العمودين غير صفرية. وبالمثل، تتوافق الرؤوس مع المتغيرات، ويشكل متغيران حافة إذا اشتركا في متباينة. مقياس التباعدد{\displaystyle d}لأ{\displaystyle A}يمثل الحد الأدنى لعمق الشجرة في الرسم البياني لـأ{\displaystyle A}وعمق الشجرة للرسم البياني لمنقولأ{\displaystyle A}. يتركأ{\displaystyle a}ليكن المقياس العددي لـأ{\displaystyle A}يُعرَّف بأنه القيمة المطلقة القصوى لأي مدخل منأ{\displaystyle A}. يتركن{\displaystyle n}ليكن عدد متغيرات برنامج الأعداد الصحيحة. ثم تم إثبات في عام 2018 [ 28 ] أنه يمكن حل برمجة الأعداد الصحيحة في وقت متعدد الحدود قوي ووقت قابل للمعالجة بمعاملات ثابتة، ويتم تحديده بواسطةأ{\displaystyle a}ود{\displaystyle d}أي، بالنسبة لدالة قابلة للحسابو{\displaystyle f}وبعض الثوابتك{\displaystyle k}يمكن حل البرمجة العددية الصحيحة في وقتو(أ،د)نك{\displaystyle f(a,d)n^{k}}وعلى وجه الخصوص، فإن الوقت مستقل عن الجانب الأيمنب{\displaystyle b}ودالة الهدفج{\displaystyle c}علاوة على ذلك، وعلى عكس النتيجة الكلاسيكية للينسترا، حيث العددن{\displaystyle n}عدد المتغيرات هو أحد المعاملات، وهنا هو العددن{\displaystyle n}يُعدّ عدد المتغيرات جزءًا متغيرًا من المدخلات.

انظر أيضاً

مراجع

  1. ↑
  2. ↑ باباديميتريو، كريستوس هـ. (1981-10-01). "حول تعقيد البرمجة العددية الصحيحة" . مجلة ACM . 28 (4): 765-768 . doi : 10.1145/322276.322287 . hdl : 1721.1/148979 . ISSN 0004-5411 . 
  3. ↑ "التعقيد الحسابي. | BibSonomy" . www.bibsonomy.org . تاريخ الاسترجاع: 2025-10-05 .
  4. ↑ كارب، ريتشارد م. (1972). "قابلية الاختزال بين المسائل التوافقية" (ملف PDF) . في: ر. إي. ميلر؛ ج. و. ثاتشر؛ ج. د. بولينجر (محررون). تعقيد الحسابات الحاسوبية . نيويورك: بلينوم. ص 85-103 . doi : 10.1007/978-1-4684-2001-2_9 . ISBN  978-1-4684-2003-6.{{cite book}}: CS1 maint: publisher location ( link )
  5. ↑ "البرمجة الخطية المختلطة (MILP): صياغة النموذج" (ملف PDF) . تم الاطلاع عليه بتاريخ 16 أبريل 2018 .
  6. ↑ باباديميتريو، سي إتش ؛ ستيغليتز، ك. (1998). التحسين التوافقي: الخوارزميات والتعقيد . مينولا، نيويورك: دوفر. ISBN 0486402584.
  7. ↑ إريكسون، ج. (2015). "اختزال البرمجة العددية الصحيحة" (ملف PDF) . مؤرشف من الأصل (ملف PDF) في 18 مايو 2015.
  8. ↑ ويليامز، إتش بي (2009). المنطق والبرمجة العددية . السلسلة الدولية في بحوث العمليات وعلوم الإدارة. المجلد 130. ISBN  978-0-387-92280-5.
  9. ↑ بورندورفر، ر.؛ غروتشل، م. (2012). "تصميم شبكات الاتصالات السلكية واللاسلكية عن طريق البرمجة العددية" (PDF) .
  10. ↑ شارما، ديباك (2010). "تخطيط التردد" .
  11. ^ مورايس، هوغو؛ كادار، بيتر؛ فاريا، بيدرو؛ فالي زيتا أ. خضر، جلالة الملك (2010-01-01). "الجدولة المثلى لشبكة صغيرة متجددة في منطقة تحميل معزولة باستخدام البرمجة الخطية ذات الأعداد الصحيحة المختلطة" . الطاقة المتجددة . 35 (1): 151– 156. بيب كود : 2010REne...35..151M . دوى : 10.1016/j.renene.2009.02.031 . اتش دي ال : 10400.22/1585 . ISSN 0960-1481 . 
  12. ↑ أومو، أكومينو؛ تشودري، روتشي؛ بويز، آدم (2013-10-01). "تحسين نظام موارد الطاقة الموزعة باستخدام البرمجة الخطية المختلطة" . سياسة الطاقة . 61 : 249-266 . Bibcode : 2013EnPol..61..249O . doi : 10.1016/j.enpol.2013.05.009 . ISSN 0301-4215 . S2CID 29369795 .  
  13. ↑ شوينارز، ت.؛ فالنتي، م.؛ فيرون، إ.؛ هاو، ج. (2005). "تنفيذ ونتائج اختبار الطيران لتوجيه الطائرات بدون طيار باستخدام البرمجة الخطية المختلطة". مؤتمر IEEE للفضاء الجوي 2005. الصفحات 1-13 . doi : 10.1109/AERO.2005.1559600 . ISBN  0-7803-8870-4. S2CID 13447718 . 
  14. ↑ رادمانيش، محمد رضا؛ كومار، مانيش (2016-03-01). "تشكيل طيران الطائرات بدون طيار في وجود عوائق متحركة باستخدام البرمجة الخطية المختلطة السريعة الديناميكية" . علوم وتكنولوجيا الفضاء . 50 : 149-160 . Bibcode : 2016AeST...50..149R . doi : 10.1016/j.ast.2015.12.021 . ISSN 1270-9638 . 
  15. ↑ باست، هانا؛ بروسي، باتريك؛ ستوراندت، سابين (2017-10-05). "إنشاء فعال لخرائط النقل العام الدقيقة جغرافيًا". arXiv : 1710.02226 [ cs.CG ].
  16. ↑ سكارف، هربرت إي. (1981). "مجموعات الإنتاج ذات عدم قابلية التجزئة، الجزء الأول: العموميات" . إيكونومتريكا . 49 (1): 1-32 . doi : 10.2307/1911124 . ISSN 0012-9682 . JSTOR 1911124 .  
  17. لينسترا ، هـ . و. (1983-11-01). "البرمجة العددية الصحيحة بعدد ثابت من المتغيرات" . رياضيات بحوث العمليات . 8 (4): 538-548 . CiteSeerX 10.1.1.431.5444 . doi : 10.1287/moor.8.4.538 . ISSN 0364-765X .  
  18. ↑ أمينتا، نينا ؛ دي لويرا، خيسوس أ .؛ سوبرون، بابلو (2017). "نظرية هيلي: تنويعات وتطبيقات جديدة". في: هارينغتون، هيذر أ .؛ عمر، محمد؛ رايت، ماثيو (محررون). وقائع الجلسة الخاصة للجمعية الأمريكية للرياضيات حول الأساليب الجبرية والهندسية في الرياضيات المتقطعة التطبيقية، المنعقدة في سان أنطونيو، تكساس، 11 يناير 2015. الرياضيات المعاصرة. المجلد 685. بروفيدنس، رود آيلاند: الجمعية الأمريكية للرياضيات. الصفحات 55-95 . arXiv : 1508.07606 . doi : 10.1090/conm/685 . ISBN   9781470423216MR 3625571 .​ 
  19. ↑ كانان، رافي (1987-08-01). "نظرية مينكوفسكي للجسم المحدب والبرمجة العددية" . رياضيات بحوث العمليات . 12 (3): 415-440 . doi : 10.1287/moor.12.3.415 . ISSN 0364-765X . S2CID 495512 .  
  20. ↑ غومانز، ميشيل إكس .؛ روثفوس، توماس (2020-11-07). "تعدد الحدود لتعبئة الصناديق بعدد ثابت من أنواع العناصر" . مجلة ACM . 67 (6): 38:1–38:21. arXiv : 1307.5108 . doi : 10.1145/3421750 . hdl : 1721.1/92865 . ISSN 0004-5411 . S2CID 227154747 .  
  21. ↑ فرانك، أندراس؛ تاردوس، إيفا (1987-03-01). "تطبيق التقريب الديوفانتي المتزامن في التحسين التوافقي" . كومبيناتوريكا . 7 (1): 49-65 . doi : 10.1007/BF02579200 . ISSN 1439-6912 . S2CID 45585308 .  
  22. ↑ بليم، برنارد؛ بريديريك، روبرت؛ نيدرماير، رولف (9 يوليو 2016). "تعقيد تخصيص الموارد بكفاءة ودون حسد: عدد قليل من الوكلاء، أو الموارد، أو مستويات المنفعة" . وقائع المؤتمر الدولي المشترك الخامس والعشرين حول الذكاء الاصطناعي . IJCAI'16. نيويورك، نيويورك، الولايات المتحدة الأمريكية: مطبعة AAAI: 102-108 . ISBN 978-1-57735-770-4.
  23. ↑ بريديريك، روبرت؛ كاتشمارشيك، أندريه؛ كنوب، دوسان؛ نيدرماير، رولف (17 يونيو 2019). "التخصيص العادل عالي التعددية: لينسترا مُعززة ببرمجة عددية صحيحة متعددة الطيات" . وقائع مؤتمر ACM للاقتصاد والحوسبة لعام 2019. EC '19. فينيكس، أريزونا، الولايات المتحدة الأمريكية: رابطة آلات الحوسبة. الصفحات 505-523 . doi : 10.1145/3328526.3329649 . ISBN  978-1-4503-6792-9. S2CID 195298520 . 
  24. ↑ دادوش، دانيال (2012-06-14). "البرمجة العددية الصحيحة، وخوارزميات الشبكة، وتقدير الحجم الحتمي" .
  25. ↑ ريس، فيكتور؛ روثفوس، توماس (2023-03-26). "تخمين تسطح الفضاء الجزئي والبرمجة العددية الأسرع" .
  26. 1 2 هيلدبراند، روبرت (2016-10-07). "خوارزمية FPT لبرنامج الأعداد الصحيحة المختلطة" . موقع تبادل الأسئلة والأجوبة في علوم الحاسوب النظرية . تم الاسترجاع في 21-05-2024 .
  27. ↑ جلوفر، ف. (1989). "البحث المحظور - الجزء الثاني". مجلة ORSA للحوسبة . 1 (3): 4-32 . doi : 10.1287/ijoc.2.1.4 . S2CID 207225435 . 
  28. ↑ كوتيكي، مارتن؛ ليفين، آساف؛ أون، شموئيل (2018). "خوارزمية متعددة الحدود قوية ذات معلمات لبرامج الأعداد الصحيحة ذات البنية الكتلية". في: تشاتزيجياناكيس، يوانيس؛ كاكلامانيس، كريستوس؛ ماركس، دانيال؛ سانيلا، دونالد (محررون). المؤتمر الدولي الخامس والأربعون حول الأوتوماتا واللغات والبرمجة، ICALP 2018، 9-13 يوليو 2018، براغ، جمهورية التشيك . LIPIcs. المجلد 107. شلوس داغشتول - مركز لايبنيز للمعلوماتية. الصفحات 85:1-85:14. arXiv : 1802.05859 . doi : 10.4230/LIPICS.ICALP.2018.85 .  

للمزيد من القراءة

  • جورج ل. نيمهاوزر ؛ لورانس أ. وولسي (1988). التحسين الأمثل للأعداد الصحيحة والتوافقية . وايلي. ISBN 978-0-471-82819-8.
  • ألكسندر شريفر (1998). نظرية البرمجة الخطية والبرمجة الصحيحة . جون وايلي وأولاده. ISBN 978-0-471-98232-6.
  • لورانس أ. وولسي (1998). البرمجة العددية الصحيحة . وايلي. ISBN 978-0-471-28366-9.
  • ديميتريس بيرتسيماس؛ روبرت وايزمانتل (2005). التحسين على الأعداد الصحيحة . أفكار ديناميكية. ISBN 978-0-9759146-2-5.
  • جون ك. كارلوف (2006). البرمجة العددية: النظرية والتطبيق . دار نشر سي آر سي. رقم ISBN 978-0-8493-1914-3.
  • إتش. بول ويليامز (2009). المنطق والبرمجة العددية الصحيحة . سبرينغر. ISBN 978-0-387-92279-9.
  • مايكل يونغر؛ توماس إم. ليبلينغ؛ دينيس نادف؛ جورج نيمهاوزر ؛ ويليام آر. بوليبلانك ؛ غيرهارد راينيلت؛ جيوفاني رينالدي؛ لورانس أ. وولسي، محرران (2009). خمسون عامًا من البرمجة العددية الصحيحة 1958-2008: من السنوات الأولى إلى أحدث التقنيات . سبرينغر. ISBN 978-3-540-68274-5.
  • دير-سان تشين؛ روبرت ج. باتسون؛ يو دانغ (2010). البرمجة العددية التطبيقية: النمذجة والحل . جون وايلي وأولاده. ISBN 978-0-470-37306-4.
  • جيرارد سيركسما؛ يوري زوولز (2015). التحسين الخطي والأعداد الصحيحة: النظرية والتطبيق . الصحافة اتفاقية حقوق الطفل. رقم ISBN 978-1-498-71016-9.
  • فرانسوا كلوتيو؛ إيفانا ليوبيتش (2024). "الخمسون عامًا الأخيرة من البرمجة الخطية الصحيحة: التركيز على التطورات العملية الحديثة" . المجلة الأوروبية لبحوث العمليات . 324 (3). INRIA : 707-731 . doi : 10.1016/j.ejor.2024.11.018 .مقال استعراضي.