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

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

کلیدواژه ها:

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