یک مدل جدید برنامه ریزی خطی اعدادصحیح برای مساله بزرگترین خوشه متوازن در گرافهای چگال
- سال انتشار: 1402
- محل انتشار: شانزدهمین کنفرانس بین المللی انجمن ایرانی تحقیق در عملیات
- کد COI اختصاصی: ICIORS16_173
- زبان مقاله: فارسی
- تعداد مشاهده: 161
نویسندگان
دانشجوی دکتری، تحقیق در عملیات دانشگاه گیلان، دانشکده ریاضی
دانشیار، عضو هیات علمی دانشگاه گیلان، دانشکده ریاضی
چکیده
مساله پیدا کردن بزرگترین خوشه متوازن درگراف دوبخشی ساده که از دسته مساله های سخت محسوب می شود، کاربرد فراوانی در زمینه-هایی مانند کشف فعل و انفعالات بین پروتئین ها و بیان ژن دارد. منظور از پیدا کردن بزرگترین خوشه متوازن، یافتن بزرگترین زیرمجموعه از راسها در هر سمت گراف دوبخشی است به طوری که تعداد راسهای انتخاب شده در دو سمت گراف دوبخشی برابر باشد و تشکیل زیرگراف کامل بدهند. بنابراین در خوشه متوازن پیدا شده، درجه راسها باهم برابرخواهد شد و هر راس در یک سمت با همه راسها در سمت دیگر خوشه مرتبط است. در این مقاله یک مدل برنامه ریزی خطی با اعداد صحیح جدید معرفی می شود که برای گرافهایی که تعداد راسهای دو سمت تقریبا برابر است و ماتریس مجاورت متناظر با گراف، چگالی هفتاد صدم تا نود و پنج صدم دارد، مناسب است. مدل سازی جدید در مقایسه با یکی از مدل های پیشین تعداد قیود کمتر و در مقایسه با مدل قبلی دیگر تعداد متغیر کمتری دارد. جهت ارزیابی مدل جدید در مقایسه با دو مدل عدد صحیح پیشین، ماتریس مجاورت گرافهای دو بخشی تصادفی با توزیع نرمال تولید و سپس با توزیع برنولی درایه های ماتریس مجاورت با صفر یک مقداردهی می شوند تا چگالی های مدنظر حاصل شوند. نتایج به دست آمده حاکی از برتری مدل جدید از نظر زمان حل نسبت به دو مدل سازی پیشین در گرافهای با ماتریس مجاورت تقریبا مربعی و چگالی هفتاد صدم تا نود و پنج صدم است.کلیدواژه ها
بهینه سازی ترکیباتی، مدل سازی عدد صحیح، بزرگترین خوشه متوازنمقالات مرتبط جدید
- داده کاوی و یادگیری ماشین در سری های زمانی تحلیل بصری اقتصاد منطقه ای
- یک مدل ریاضی برای مدیریت زنجیره تامین با در نظر گرفتن عدم قطعیت تقاضا
- طراحی زنجیره تامین یکپارچه سبز دو هدفه با هزینه های تصادفی
- Solving a Stochastic Multi-Objective Location-Routing Problem: a Comparative Study of Meta-heuristics
- مکانیابی تسهیلات تولیدی در زنجیره تامین با بکارگیری تکنیک Linmap فازی(مطالعه موردی: تولید قطعات مخابراتی)
اطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.