💻 computer science

Solving the Two-dimensional single stock size Cuting Stock Problem with SAT and MaxSAT

تقدم هذه الورقة إطار عمل قائماً على نموذج إرضاء الالتزامات (SAT) لمسألة تقطيع مخزون السلع أحادية حجم السهم ثنائية الأبعاد، والتي تستخدم توسيع الطلب، وإلغاء التوجيه، واستراتيجيات حل متنوعة للتفوق بشكل كبير على الحلول التجارية مثل OR-Tools وCPLEX وGurobi في إثبات المثالية وتقليل الفجوات في النماذج المرجعية.

المؤلفون الأصليون: Tuyen Van Kieu, Chi Linh Hoang, Khanh Van To

نُشر 2026-04-03

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Tuyen Van Kieu, Chi Linh Hoang, Khanh Van To

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك تدير مصنعاً ضخماً للأثاث. كل يوم، تتلقى طلباً هائلاً: 50 طاولة، 30 كرسياً، و20 رفاً للكتب. لديك مستودع مليء بصفائح خشب الأبلكاش (الخشب الرقائقي) المتطابقة والضخمة. هدفك؟ قص كل تلك القطع من أقل عدد ممكن من الصفائح لتوفير المال وتقليل الهدر.

هذه هي مشكلة تقطيع المخزون أحادي الحجم ثنائي الأبعاد (2D-CSSP). قد يبدو الأمر بسيطاً، لكنه كابوس للحواسيب. لماذا؟ لأنه إذا كان لديك 50 طاولة، فعلى الحاسوب ألا يكتفي بمعرفة "أين" يضعها فحسب، بل يجب أن يعرف أيضاً "أي" واحدة من بين الـ 50 طاولة متطابقة ستوضع في أي مكان. عدد الاحتمالات ينفجر مثل آلة الفشار التي تم ضبطها على وضع "نووي".

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

1. الطريقة القديمة مقابل الطريقة الجديدة

الطريقة القديمة (المحللات التجارية): تخيل أنك تحاول حل هذا اللغز بسؤال روبوت ذكي جداً ولكنه حرفي للغاية: "هل يمكنني وضع 50 طاولة في 10 صفائح؟". يحاول الروبوت، يفشل، ثم يقول "لا". ثم تسأله: "ماذا عن 11 صفيحة؟". يحاول مرة أخرى. هذه الطريقة بطيئة، وغالباً ما يعلق الروبوت في حلقة مفرغة، غير قادر على إثبات أنه وجد الإجابة "الأفضل مطلقاً"، بل يجد فقط إجابة "جيدة بما يكفي".
الطريقة الجديدة (نهج SAT): قام المؤلفون ببناء محرك منطقي مخصص يعامل المشكلة كأنها لعبة سودوكو منطقية ضخمة. بدلاً من مجرد التخمين، يبني المحرك مجموعة من القواعد الصارمة (البنود) التي تصف العالم المادي: "إذا كانت الطاولة (أ) هنا، فلا يمكن للطاولة (ب) أن تكون هناك".

2. السر الخفي: القواعد "الشرطية"

الاختراق الأكبر في هذه الورقة هو كيفية تعاملهم مع مشكلة "النسخ".

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

3. الاختصارات الذكية (كسر التماثل)

عندما يكون لديك 50 كرسياً متطابقاً، لا يهم إذا كان الكرسي رقم 1 على اليسار والكرسي رقم 2 على اليمين، أو العكس. كلاهما يبدو متشابهاً.

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

4. ثلاث استراتيجيات لإيجاد أفضل إجابة

اختبر الفريق ثلاث طرق مختلفة لاستخدام محرك المنطق الخاص بهم للعثور على الحد الأدنى من الصفائح:

البحث الثنائي (غير التزايدي): مثل تخمين رقم بين 1 و 100. "هل هو 50؟ لا. هل هو 25؟ نعم. هل هو 12؟". إنها سريعة ولكنها تلقي بكل عملها في القمامة في كل مرة تخمن فيها رقماً جديداً.
حافظ الذاكرة (Incremental SAT): هذا هو الفائز في معظم الحالات. تخيل محققاً يحل لغزاً. إذا أثبت أن مشتبهاً به بريء يوم الاثنين، فإنه يتذكر هذه الحقيقة يوم الثلاثاء.
- عندما يحاول الحاسوب وضع العناصر في 10 صفائح ويفشل، فإنه يتعلم لماذا فشل (على سبيل المثال: "هذه العناصر الثلاثة العريضة لا يمكن أن تجتمع أبداً"). عندما يحاول 11 صفيحة، فإنه يتذكر هذا الدرس فوراً. إنه لا يبدأ من الصفر؛ بل يبني على إخفاقاته السابقة.
الرهان بضربة واحدة (MaxSAT): يحاول هذا النهج حل المسألة للوصول للرقم المثالي في قفزة واحدة عملاساً. إنه قوي ولكنه قد يصاب بالارتباك بسبب الحجم الهائل للرياضيات، مثل محاولة أكل بيتزا كاملة في قضمة واحدة.

5. النتائج: من الفائز؟

اختبر المؤلفون نظامهم مقابل أفضل البرمجيات التجارية في العالم (مثل Google OR-Tools و CPLEX و Gurobi) باستخدام 30 لغزاً من واقع الحياة شديد الصعوبة.

الحكم: كان نظامهم القائم على SAT بطلاً مهيمناً.
- إثبات الكمال: بينما تمكنت البرامج التجارية من إيجاد حل "جيد" في كثير من الأحيان، إلا أنها كثيراً ما فشلت في إثبات أنه الحل الأفضل مطلقاً. نظام SAT الجديد أثبت الحل الأمثل لـ 2 إلى 3 أضعاف عدد الألغاز التي حلها العمالقة التجاريون.
- الكفاءة: وجد حلولاً أفضل بهدر أقل (فجوة مثالية أقل).
- المفاجأة: من المثير للاهتمام أن نهج "حافظ الذاكرة" (التزايدي) كان الأفضل عندما لم يكن بالإمكان تدوير العناصر. ولكن عندما كان بالإمكان تدوير العناصر (مما يجعل الرياضيات أكبر بكثير)، كان نهج "البحث الثنائي" يؤدي بشكل أفضل لأن الذاكرة تصبح مزدحمة جداً بالقواعد.

الخلاصة

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

باخت-طصار: لقد بنوا طريقة أكثر ذكاءً ومنطقية لتقطيع الخشب توفر المال، وتقلل الهدر، وتثبت أنها الطريقة الأفضل في كل مرة.

إليك ملخص تقني مفصل لورقة البحث بعنوان "حل مشكلة تقطيع مخزون القطعة الواحدة ثنائية الأبعاد باستخدام SAT و MaxSAT".

1. تعريف المشكلة

تتناول الورقة مشكلة تقطيع مخزون القطعة الواحدة ثنائية الأبعاد (2D-CSSP).

الهدف: تقطيع مجموعة من العناصر المستطيلة من ألواح مخزون متطابقة لتلبية طلبات محددة مع تقليل إجمالي عدد الألواح المستخدمة.
المدخلات: قائمة بأنواع العناصر $T = \{(w_t, h_t, d_t)\}$ ، حيث تمثل $w_t$ و $h_t$ الأبعاد و $d_t$ هو الطلب (عدد النسخ المطلوبة). حجم اللوح هو $W \times H$ .
التعقيد: المشكلة هي مسألة NP-hard. وهي تعمم مشكلة التعبئة في حاويات ثنائية الأبعاد (2D-BPP). التحدي المحدد في 2D-CSSP هو الأثر التضاعفي للطلبات: إذا كان لنوع عنصر ما طلب مرتفع، فإنه ينشئ العديد من النسخ المتطابقة، مما يؤدي إلى مساحة بحث هائلة وتماثل كبير (تبادلية النسخ المتطابقة).
القيود: يجب وضع العناصر دون تداخل، وضمن حدود اللوح، ويمكن اختيار تدويرها بزاوية 90 درجة اختيارياً.

2. المنهجية

يقترح المؤلفون إطار عمل يعتمد على SAT يقوم بترميز المشكلة إلى "الاشباع البولياني" (Boolean Satisfiability) و "MaxSAT الجزئي الموزون" (Weighted Partial MaxSAT).

أ. استراتيجية ترميز SAT

على عكس البرمجة الخطية المختلطة (MIP) التقليدية التي تتوسع بشكل سيء مع الطلبات العالية، يستخدم نهج SAT ما يلي:

توسيع الطلب: بدلاً من معاملة أنواع العناصر كمتغيرات مجردة، يتم توسيع الطلبات. إذا كان لنوع العنصر $t$ طلب $d_t$ ، فإنه يُعامل كـ $d_t$ من النسخ المتميزة ( $c_{t,1}, \dots, c_{t,d_t}$ ).
المتغيرات:
- تخصيص اللوح ( $s_{c,j}$ ): متغير بولياني يشير إلى ما إذا كانت النسخة $c$ مخصصة للوح $j$ .
- الإحداثيات (ترميز الترتيب): يستخدم ترميز الترتيب لـ $x_c$ و $y_c$ للحفاظ على عدد المتغيرات خطياً بالنسبة لأبعاد اللوح.
- التدوير ( $R_c$ ): علامة بوليانية للتدوير بزاوية 90 درجة.
- الموقع النسبي: متغيرات لـ "يسار" و "أسفل" العلاقات.
قيود عدم التداخل الشرطية: هذا هو الابتكار الجوهري. قيود عدم التداخل هي شرطية على تخصيص اللوح.
- الترميزات القياسية تفرض عدم التداخل لجميع الأزواج.
- هذا الترميز يفرض عدم التداخل فقط إذا تم تخصيص نسختين لنفس اللوح ( $\neg s_{c,j} \lor \neg s_{c',j} \lor \text{non-overlap}$ ). هذا يقلل بشكل كبير من عدد القيود النشطة للنسخ الموجودة في ألواح مختلفة.
كسر التماثل: للتعامل مع الانفجار التوليفي الناتج عن النسخ المتطابقة، يتم تطبيق أربع قواعد:
- قيود العناصر الكبيرة: تثبيت المواقع النسبية إذا لم تتمكن العناصر من التواجد جنباً إلى جنب.
- ترتيب الحجم المتساوي: فرض ترتيب صارم بين نسخ النوع نفسه لكسر تماثل التبديل.
- إزالة التوجه غير الممكن: إذا كان العنصر يناسب اللوح في توجه واحد فقط (بسبب الأبعاد)، يتم تثبيت متغير التدوير فوراً.
- ترتيب الألواح: تُستخدم الألواح بالترتيب الفهرسي (1، 2، 3...) لإزالة تماثلات إعادة التسمية $k!$ .

ب. طرق الحل

تقارن الورقة بين ثلاث استراتيجيات لإيجاد الحد الأدنى من عدد الألواح ( $k$ ):

SAT غير التزايدي مع البحث الثنائي: يعيد بناء صيغة SAT من الصفر لكل $k$ مرشح باستخدام البحث الثنائي.
SAT التزايدي مع البحث الثنائي: يبني الصيغة للحد الأعلى ( $UB$ ) مرة واحدة. يستخدم افتراضات الحل لـ "تعطيل" الألواح التي تتجاوز $k$ المختبر الحالي. والأهم من ذلك، يتم الاحتفاظ بـ جمل الصراع (conflict clauses) التي تم تعلمها أثناء المحاولات الفاشلة (UNSAT) وإعادة استخدامها في التكرارات اللاحقة، مما يقلص مساحة البحث بفعالية.
MaxSAT الجزئي الموزون: يرمز للمشكلة كمهمة تحسين واحدة حيث يكون تقليل عدد الألواح المستخدمة هدفاً "ناعماً" (soft objective).

3. المساهمات الرئيسية

أول ترميز SAT لـ 2D-CSSP: يقدم المؤلفون أول صياغة منطقية تصريحية لهذه المشكلة المحددة، معالجة التحدي الفريد المتمثل في التماثلات الناتجة عن الطلب والقيود الشرطية.
قاعدة التوجه غير الممكن: قاعدة عامة تقوم بتثبيت متغيرات التدوير عندما يناسب التوجه الواحد فقط اللوح، مما يوسع العمل السابق على "تعبئة الشريط" (strip packing).
التحليل التجريبي لاستراتيجيات الحل: تكشف الدراسة أن استراتيجية SAT المثلى تعتمد على بنية المشكلة:
- بدون تدوير: SAT التزايدي هو الأفضل لأن جمل الصراع المتعلمة من الاستحالات الهندسية (مثل "ثلاث قطع عريضة لا يمكن أن تتسع في لوح واحد") تظل صالحة عبر أعداد الألواح المختلفة.
- مع التدوير: SAT غير التزايدي يعمل بشكل أفضل. يزيد التدوير من حجم الصيغة بشكل كبير (تنمو الجمل بنحو 3 أضعاف)، مما يجعل قاعدة الجمل في الحل التزايدي كبيرة جداً مع وجود "ضجيج"، مما يقلل من فائدة إعادة استخدام الجمل.
التقييم الشامل: مقارنة واسعة النطاق مع الحلول الصناعية (OR-Tools, CPLEX, Guropi) على مجموعة اختبارات Cui–Zhao.

4. النتائج التجريبية

أُجريت التجارب على 30 حالة من مجموعة Cui–Zhao (7-21 نوع عنصر، طلبات تصل إلى 45) بحد زمني قدره 1,800 ثانية.

شهادة المثالية:
- نهج SAT: حقق شهادة المثالية لـ 16 حالة (بدون تدوير) و 18 حالة (مع التدوير).
- الحلول التجارية: حقق أفضل حل تجاري (OR-Tools CP) شهادة لـ 7 حالات فقط (بدون تدوير) و 6 حالات (مع التدوير).
- النتيجة: حقق نهج SAT شهادة مثالية لعدد حالات أكثر بـ مرتين إلى 3 مرات من أي حل تجاري.
فجوات المثالية:
- حقق نهج SAT فجوات أقل بكثير (على سبيل المثال، 3.24% مع التدوير مقابل 4.63% لـ OR-Tools).
- واجهت حلول MIP (مثل CPLEX و Guropi) صعوبة في التعامل مع فجوات تزيد عن 13% وحققت شهادات قليلة جداً.
الفروق الدقيقة في الأداء:
- كان OR-Tools CP سريعاً غالباً في إيجاد حلول ممكنة تطابق أفضل حل معروف (BKS) ولكنه فشل في إثبات المثالية.
- وفرت حلول SAT شهادات مثالية قوية عبر محرك CDCL (تعلم الجمل القائم على الصراع).
- كان SAT التزايدي هو الأسرع للصيغ المدمجة (بدون تدوير)، بينما كان SAT غير التزايدي أكثر متانة عندما أدى التدوير إلى توسيع مساحة البحث.

5. الأهمية

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

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

باختصار، تضع هذه الورقة معياراً جديداً لـ 2D-CSSP، وتثبت أن ترميزات SAT المصممة خصيصاً يمكن أن تتفوق على الحلول التجارية العامة في كل من جودة الحل وشهادة المثالية.