حل مسئله درخت اشتاینر با محدودیت های درآمد، بودجه و هاپ تا بهینه

عنوان حل مسئله درخت اشتاینر با محدودیت های درآمد، بودجه و هاپ تا بهینه
نویسنده لیب، ص. ب.، هجری، ه.، حواری، محمد
تاریخ انتشار: 2013
محل انتشار - IEEE
موضوع درخت اشتاینر، برنامه‌ریزی عدد صحیح مختلط، محدودیت‌های حذف زیرتور MTZ، تکنیک خطی‌سازی مجدد
نوع دوره ای
زبان انگلیسی
دیجیتال بله
نسخه خطی خیر
کتابخانه: دانشگاه اوزیغین
شناسه دارایی کتابخانه 2-s2.0-84881411023
شماره ثبت ed0ea209-9edc-4e73-8481-595e7c1b0cd0
محل کتابخانه مهندسی صنایع
تاریخ 2013
یادداشت‌ها با توجه به محدودیت های کپی رایت، دسترسی به متن کامل این مقاله تنها از طریق اشتراک امکان پذیر است.
متن نمونه ما مشکل درخت اشتاینر را با محدودیت‌های درآمد، بودجه و هاپ (STPRBH) روی نمودار بررسی می‌کنیم، که تعمیم مشکل درخت اشتاینر شناخته شده است. با توجه به یک گره ریشه، هزینه های لبه، درآمدهای گره ها، و همچنین بودجه و هاپ از پیش تعیین شده، STPRBH به دنبال یافتن زیردرختی است که شامل گره ریشه است و مجموع کل درآمد لبه را با توجه به محدودیت های بودجه و هاپ به حداکثر می رساند. این محدودیت ها محدودیت هایی را بر هزینه کل شبکه و تعداد یال های بین هر رأس و ریشه تحمیل می کند. جای تعجب نیست که STPRBH NP-hard است. برای این مشکل طراحی شبکه چالش برانگیز که در تنظیمات مخابراتی و مسیریابی چندپخشی بوجود می آید، چندین فرمول اندازه چند جمله ای را ارائه می کنیم. ما یک فرمول پیشرفته را بر اساس کار کلاسیک میلر، تاکر، و زملین با استفاده از مجموعه‌ای از متغیرهای اضافی که رتبه‌بندی بازدید از گره‌ها را نشان می‌دهند، پیشنهاد می‌کنیم. همچنین، ما یک فرمول جدید برای STPRBH را با ایجاد یک رتبه جزئی-1 از تکنیک خطی‌سازی مجدد، بررسی می‌کنیم. نتایج گسترده‌ای با استفاده از مجموعه‌ای از نمونه‌های معیار برای مقایسه فرمول‌های پیشنهادی با استفاده از حل‌کننده MIP با هدف کلی به نمایش گذاشته می‌شوند.
DOI 10.1109/ICMSAO.2013.6552674
مشاهده در منبع دانشگاه اوزیغین دانشگاه اوزیغین - موتور جستجوی آثار تاریخی، آرشیوها و نشریات
دانشگاه اوزیغین - موتور جستجوی آثار تاریخی، آرشیوها و نشریات دانشگاه اوزیغین

حل مسئله درخت اشتاینر با محدودیت های درآمد، بودجه و هاپ تا بهینه

نویسنده لیب، ص. ب.، هجری، ه.، حواری، محمد
تاریخ انتشار 2013
محل انتشار - IEEE
موضوع درخت اشتاینر، برنامه‌ریزی عدد صحیح مختلط، محدودیت‌های حذف زیرتور MTZ، تکنیک خطی‌سازی مجدد
نوع دوره ای
زبان انگلیسی
دیجیتال بله
نسخه خطی خیر
کتابخانه دانشگاه اوزیغین
شناسه دارایی کتابخانه 2-s2.0-84881411023
شماره ثبت ed0ea209-9edc-4e73-8481-595e7c1b0cd0
محل کتابخانه مهندسی صنایع
تاریخ 2013
یادداشت‌ها با توجه به محدودیت های کپی رایت، دسترسی به متن کامل این مقاله تنها از طریق اشتراک امکان پذیر است.
متن نمونه ما مشکل درخت اشتاینر را با محدودیت‌های درآمد، بودجه و هاپ (STPRBH) روی نمودار بررسی می‌کنیم، که تعمیم مشکل درخت اشتاینر شناخته شده است. با توجه به یک گره ریشه، هزینه های لبه، درآمدهای گره ها، و همچنین بودجه و هاپ از پیش تعیین شده، STPRBH به دنبال یافتن زیردرختی است که شامل گره ریشه است و مجموع کل درآمد لبه را با توجه به محدودیت های بودجه و هاپ به حداکثر می رساند. این محدودیت ها محدودیت هایی را بر هزینه کل شبکه و تعداد یال های بین هر رأس و ریشه تحمیل می کند. جای تعجب نیست که STPRBH NP-hard است. برای این مشکل طراحی شبکه چالش برانگیز که در تنظیمات مخابراتی و مسیریابی چندپخشی بوجود می آید، چندین فرمول اندازه چند جمله ای را ارائه می کنیم. ما یک فرمول پیشرفته را بر اساس کار کلاسیک میلر، تاکر، و زملین با استفاده از مجموعه‌ای از متغیرهای اضافی که رتبه‌بندی بازدید از گره‌ها را نشان می‌دهند، پیشنهاد می‌کنیم. همچنین، ما یک فرمول جدید برای STPRBH را با ایجاد یک رتبه جزئی-1 از تکنیک خطی‌سازی مجدد، بررسی می‌کنیم. نتایج گسترده‌ای با استفاده از مجموعه‌ای از نمونه‌های معیار برای مقایسه فرمول‌های پیشنهادی با استفاده از حل‌کننده MIP با هدف کلی به نمایش گذاشته می‌شوند.
DOI 10.1109/ICMSAO.2013.6552674
دانشگاه اوزیغین - موتور جستجوی آثار تاریخی، آرشیوها و نشریات
دانشگاه اوزیغین شما در حال هدایت مجدد هستید...

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