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

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