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