المؤلف
Layeb, S. B., Hajri, I., Haouari, Mohamed
تاريخ النشر
2013
مكان النشر
-
IEEE
الموضوع
شجرة شتاينر، برمجة الأعداد الصحيحة المختلطة، قيود إزالة الجولة الفرعية MTZ، تقنية إعادة الصياغة الخطية
النوع
دورية
اللغة
الإنجليزية
رقمي
نعم
مخطوط
لا
المكتبة
جامعة اوزيجين
معرف أصل المكتبة
2-s2.0-84881411023
رقم السجل
ed0ea209-9edc-4e73-8481-595e7c1b0cd0
موقع المكتبة
الهندسة الصناعية
التاريخ
2013
ملاحظات
نظرًا لقيود حقوق الطبع والنشر، فإن الوصول إلى النص الكامل لهذه المقالة متاح فقط عبر الاشتراك.
نص عينة
نحن نتحقق من مشكلة شجرة شتاينر فيما يتعلق بالإيرادات والميزانية وقيود القفزات (STPRBH) على الرسم البياني، وهو تعميم لمشكلة شجرة شتاينر المعروفة. نظرًا للعقدة الجذرية وتكاليف الحافة وإيرادات العقد بالإضافة إلى الميزانية المحددة مسبقًا والقفزة، تسعى STPRBH إلى العثور على شجرة فرعية تتضمن العقدة الجذرية وتعظيم مجموع إجمالي إيرادات الحافة مع احترام قيود الميزانية والقفزة. تفرض هذه القيود حدودًا على التكلفة الإجمالية للشبكة وعدد الحواف بين أي قمة والجذر. ليس من المستغرب أن يكون STPRBH صلبًا NP. بالنسبة لمشكلة تصميم الشبكة الصعبة التي تنشأ في إعدادات الاتصالات وتوجيه البث المتعدد، نقدم العديد من صيغ الحجم متعدد الحدود. نقترح صياغة محسنة تعتمد على العمل الكلاسيكي لميلر وتاكر وزيملين باستخدام مجموعة إضافية من المتغيرات التي تمثل ترتيب رتبة زيارة العقد. أيضًا، نحن ندرس صياغة جديدة لـ STPRBH من خلال تصميم رتبة جزئية -1 لتقنية إعادة الصياغة الخطية. يتم عرض نتائج واسعة النطاق باستخدام مجموعة من الأمثلة القياسية لمقارنة الصيغ المقترحة باستخدام حل MIP للأغراض العامة.
DOI
10.1109/ICMSAO.2013.6552674
