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

ماتریس های دودوئی با خاصیت یک های متوالی (C۱P) در زمینه های کاربردی متعددی ظاهر می شوند و در مواردی که ماتریس مورد بررسی، خاصیت یک های متوالی را ندارد، تبدیل آن به ماتریسی که این خاصیت را داراست، اهمیت می یابد. یکی از تبدیلاتی که در این خصوص مطرح شده است، حذف برخی ستون هاست به طوری که در زیرماتریس حاصل، خاصیت C۱P برقرار گردد. لذا، حذف برخی ستون-های ماتریس با هدف یافتن بزرگ ترین زیرماتریس با خاصیت C۱P مساله ای است که مورد توجه محققین قرار گرفته است. این مساله NP-سخت است و الگوریتم های تقریبی با پیچیدگی های محاسباتی مختلفی برای حل آن مطرح شده اند. اما با توجه به اطلاعات ما، این مساله تاکنون از دیدگاه بهینه سازی مورد مطالعه قرار نگرفته است. این مقاله یک مدل بهینه سازی برای این مساله معرفی می کند و یک رویکرد محاسباتی برای حل مسائل بهینه سازی که شامل ماتریس ضرایب دودوئی است، ارائه می دهد.

Keywords:

بزرگ ترین زیرماتریس با خاصیت یک های متوالی , مدل بهینه سازی , مساله فروشنده دوره گرد