مدل‌های فشرده و تحلیل مقایسه‌ای برای جمع‌آوری جایزه مسئله درخت اشتاینر

عنوان مدل‌های فشرده و تحلیل مقایسه‌ای برای جمع‌آوری جایزه مسئله درخت اشتاینر
نویسنده حواری، محمد، لایب، س.ب.، شرالی، ح.د.
تاریخ انتشار: 2013-03
محل انتشار - الزویر
موضوع درخت اشتاینر، محدودیت‌های حذف زیرگرد MTZ، تکنیک خطی‌سازی مجدد فرمول‌بندی (RLT)، برنامه‌ریزی عدد صحیح مختلط
نوع دوره ای
زبان انگلیسی
دیجیتال بله
نسخه خطی خیر
کتابخانه: دانشگاه اوزیغین
شناسه دارایی کتابخانه 0166-218X
شماره ثبت 118d13e6-c7c2-4e0a-9399-c1732e185247
محل کتابخانه مهندسی صنایع
تاریخ 2013-03
یادداشت‌ها با توجه به محدودیت های کپی رایت، دسترسی به متن کامل این مقاله تنها از طریق اشتراک امکان پذیر است.
متن نمونه ما یک نسخه تعمیم‌یافته از مشکل درخت اشتاینر جمع‌آوری جایزه (PCSTP) را بررسی می‌کنیم، که در آن هر گره از یک نمودار وزن داده شده با یک جایزه و همچنین هزینه جریمه مرتبط است. مشکل یافتن درختی است که زیرمجموعه‌ای از گره‌ها را در بر می‌گیرد که مجموع جایزه را کمتر از یک سهمیه Q جمع‌آوری می‌کند، به طوری که مجموع وزن یال‌های درخت به اضافه مجموع جریمه‌های گره‌هایی که درخت پوشانده نشده‌اند به حداقل برسد. ما چندین مدل برنامه‌نویسی اعداد صحیح مختلط را برای PCSTP فرموله می‌کنیم و با اضافه کردن نابرابری‌های معتبر، رفع محدودیت‌ها، یا فرمول‌بندی مجدد مدل با استفاده از تکنیک خطی‌سازی مجدد (RLT) آنها را تقویت می‌کنیم. ما همچنین یک مقایسه نظری از نقاط قوت نسبی آرامش‌های LP مرتبط انجام می‌دهیم. نتایج گسترده ای با استفاده از مجموعه بزرگی از نمونه های معیار برای مقایسه فرمول های مختلف ارائه شده است. به طور خاص، یک رویکرد فرمول فشرده هیبریدی پیشنهادی نشان داده شده است که راه‌حل‌های بهینه یا بسیار نزدیک به بهینه را برای نمونه‌هایی که تا ۲۵۰۰ گره و ۳۱۲۵ لبه دارند، ارائه می‌کند.
DOI 10.1016/j.dam.2011.09.012
Cilt 161
مشاهده در منبع دانشگاه اوزیغین دانشگاه اوزیغین - موتور جستجوی آثار تاریخی، آرشیوها و نشریات
دانشگاه اوزیغین - موتور جستجوی آثار تاریخی، آرشیوها و نشریات دانشگاه اوزیغین

مدل‌های فشرده و تحلیل مقایسه‌ای برای جمع‌آوری جایزه مسئله درخت اشتاینر

نویسنده حواری، محمد، لایب، س.ب.، شرالی، ح.د.
تاریخ انتشار 2013-03
محل انتشار - الزویر
موضوع درخت اشتاینر، محدودیت‌های حذف زیرگرد MTZ، تکنیک خطی‌سازی مجدد فرمول‌بندی (RLT)، برنامه‌ریزی عدد صحیح مختلط
نوع دوره ای
زبان انگلیسی
دیجیتال بله
نسخه خطی خیر
کتابخانه دانشگاه اوزیغین
شناسه دارایی کتابخانه 0166-218X
شماره ثبت 118d13e6-c7c2-4e0a-9399-c1732e185247
محل کتابخانه مهندسی صنایع
تاریخ 2013-03
یادداشت‌ها با توجه به محدودیت های کپی رایت، دسترسی به متن کامل این مقاله تنها از طریق اشتراک امکان پذیر است.
متن نمونه ما یک نسخه تعمیم‌یافته از مشکل درخت اشتاینر جمع‌آوری جایزه (PCSTP) را بررسی می‌کنیم، که در آن هر گره از یک نمودار وزن داده شده با یک جایزه و همچنین هزینه جریمه مرتبط است. مشکل یافتن درختی است که زیرمجموعه‌ای از گره‌ها را در بر می‌گیرد که مجموع جایزه را کمتر از یک سهمیه Q جمع‌آوری می‌کند، به طوری که مجموع وزن یال‌های درخت به اضافه مجموع جریمه‌های گره‌هایی که درخت پوشانده نشده‌اند به حداقل برسد. ما چندین مدل برنامه‌نویسی اعداد صحیح مختلط را برای PCSTP فرموله می‌کنیم و با اضافه کردن نابرابری‌های معتبر، رفع محدودیت‌ها، یا فرمول‌بندی مجدد مدل با استفاده از تکنیک خطی‌سازی مجدد (RLT) آنها را تقویت می‌کنیم. ما همچنین یک مقایسه نظری از نقاط قوت نسبی آرامش‌های LP مرتبط انجام می‌دهیم. نتایج گسترده ای با استفاده از مجموعه بزرگی از نمونه های معیار برای مقایسه فرمول های مختلف ارائه شده است. به طور خاص، یک رویکرد فرمول فشرده هیبریدی پیشنهادی نشان داده شده است که راه‌حل‌های بهینه یا بسیار نزدیک به بهینه را برای نمونه‌هایی که تا ۲۵۰۰ گره و ۳۱۲۵ لبه دارند، ارائه می‌کند.
DOI 10.1016/j.dam.2011.09.012
Cilt 161
دانشگاه اوزیغین - موتور جستجوی آثار تاریخی، آرشیوها و نشریات
دانشگاه اوزیغین شما در حال هدایت مجدد هستید...

لطفاً صبر کنید