شماره ركورد كنفرانس :
5432
عنوان مقاله :
رويكرد بهينه سازي براي شناسايي بزرگ ترين زيرماتريس با خاصيت يك هاي متوالي
پديدآورندگان :
ياراحمدي محمد نصير nasiryari@aut.ac.ir دانشجوي دكتري دانشگاه صنعتي اميركبير، دانشكده رياضي و علوم كامپيوتر، تهران، ايران , ميرحسني سيدعلي a_mirhassani@aut.ac.ir عضو هيأت علمي دانشگاه صنعتي اميركبير، دانشكده رياضي و علوم كامپيوتر، تهران، ايران , هوشمند خليق فرناز f.hooshmand.khaligh@aut.ac.ir عضو هيأت علمي دانشگاه صنعتي اميركبير، دانشكده رياضي و علوم كامپيوتر، تهران، ايران
كليدواژه :
بزرگ ترين زيرماتريس با خاصيت يك هاي متوالي , مدل بهينه سازي , مسأله فروشنده دوره گرد
عنوان كنفرانس :
شانزدهمين كنفرانس بين المللي انجمن ايراني تحقيق در عمليات
چكيده فارسي :
ماتريس هاي دودوئي با خاصيت يك هاي متوالي (C1P) در زمينه هاي كاربردي متعددي ظاهر مي شوند و در مواردي كه ماتريس مورد بررسي، خاصيت يك هاي متوالي را ندارد، تبديل آن به ماتريسي كه اين خاصيت را داراست، اهميت مي يابد. يكي از تبديلاتي كه در اين خصوص مطرح شده است، حذف برخي ستون هاست به طوري كه در زيرماتريس حاصل، خاصيت C1P برقرار گردد. لذا، حذف برخي ستون-هاي ماتريس با هدف يافتن بزرگ ترين زيرماتريس با خاصيت C1P مسأله اي است كه مورد توجه محققين قرار گرفته است. اين مسأله NP-سخت است و الگوريتم هاي تقريبي با پيچيدگي هاي محاسباتي مختلفي براي حل آن مطرح شده اند. اما با توجه به اطلاعات ما، اين مسأله تاكنون از ديدگاه بهينه سازي مورد مطالعه قرار نگرفته است. اين مقاله يك مدل بهينه سازي براي اين مسأله معرفي مي كند و يك رويكرد محاسباتي براي حل مسائل بهينه سازي كه شامل ماتريس ضرايب دودوئي است، ارائه مي دهد.
