طه قاسمی - دانشگاه صنعتی امیرکبیر، دانشکده مهندسی کامپیوتر و فناوری اطلاعات
محمدرضا رزازی

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