محمدجواد قدیری - دانشجوی دکتری، تحقیق در عملیات دانشگاه گیلان، دانشکده ریاضی
مهری باقریان - دانشیار، عضو هیات علمی دانشگاه گیلان، دانشکده ریاضی

مساله پیدا کردن بزرگترین خوشه متوازن درگراف دوبخشی ساده که از دسته مساله های سخت محسوب می شود، کاربرد فراوانی در زمینه-هایی مانند کشف فعل و انفعالات بین پروتئین ها و بیان ژن دارد. منظور از پیدا کردن بزرگترین خوشه متوازن، یافتن بزرگترین زیرمجموعه از راسها در هر سمت گراف دوبخشی است به طوری که تعداد راسهای انتخاب شده در دو سمت گراف دوبخشی برابر باشد و تشکیل زیرگراف کامل بدهند. بنابراین در خوشه متوازن پیدا شده، درجه راسها باهم برابرخواهد شد و هر راس در یک سمت با همه راسها در سمت دیگر خوشه مرتبط است. در این مقاله یک مدل برنامه ریزی خطی با اعداد صحیح جدید معرفی می شود که برای گرافهایی که تعداد راسهای دو سمت تقریبا برابر است و ماتریس مجاورت متناظر با گراف، چگالی هفتاد صدم تا نود و پنج صدم دارد، مناسب است. مدل سازی جدید در مقایسه با یکی از مدل های پیشین تعداد قیود کمتر و در مقایسه با مدل قبلی دیگر تعداد متغیر کمتری دارد. جهت ارزیابی مدل جدید در مقایسه با دو مدل عدد صحیح پیشین، ماتریس مجاورت گرافهای دو بخشی تصادفی با توزیع نرمال تولید و سپس با توزیع برنولی درایه های ماتریس مجاورت با صفر یک مقداردهی می شوند تا چگالی های مدنظر حاصل شوند. نتایج به دست آمده حاکی از برتری مدل جدید از نظر زمان حل نسبت به دو مدل سازی پیشین در گرافهای با ماتریس مجاورت تقریبا مربعی و چگالی هفتاد صدم تا نود و پنج صدم است.

بهینه سازی ترکیباتی، مدل سازی عدد صحیح، بزرگترین خوشه متوازن