هدف این درس آشنایی دانشجو با بهینه‌سازی ترکیبیاتی از طریق بررسی مسائل بهینه‌سازی و الگوریتم‌های خاص این حوزه از جمله الگوریتم‌های Simplex و Prime-Dual، دوگانی و برنامه‌ریزی خطی صحیح است.

1. مسئله‌های بهینه‌سازی
   • معرفی، همسایگی، بهینه‌سازی محلی و سراسری، مجموعه و توابع محدب، مسئله‌های برنامه‌ریزی محدب
2. الگوریتم Simplex
   • فرم‌های مسئله‌ی برنامه‌ریزی خطی، راه‌حل امکان‌پذیر، هندسه‌ی برنامه‌ریزی خطی، الگوریتم و پیچیدگی سیمپلکس، جنبه‌های هندسی انتخاب محور
3. ‎دوگانی ‎
   • دوگان برنامه‌ریزی خطی در حالت کلی، ‎Slackness، مسئله‌ی کوتاه‌ترین مسیر ودوگان آن، مسئله‌ی شبکه‌ی شاره، دوگان الگوریتم سیمپلکس، ‎جنبه‌های محاسباتی الگوریتم سیمپلکس
4. ‎الگوریتم Primal-Dual
   • الگوریتم و کاربرد آن در شبکه‌ی شاره و مسئله‌های کوتاه‌ترین مسیر دایکسترا، ‎الگوریتم‌های کارا برای مسئله‌های شبکه‌ی شاره، تطابق (عادی و وزن‌دار)، درخت‌های پوشای کمینه
5. ‎برنامه‌ریزی خطی صحیح
   • ان‌پی-تمام بودن مسئله و راه‌های تقریبی، ‎استفاده از بهینه‌سازی در حل تقریبی مسئله‌های ان‌پی-سخت

• تمرین‌های نظری: ۳ نمره
• آزمون‌های میان‌ترم و پایانی: ۱۵ نمره
• گزارش پژوهشی: ۲ نمره