برنامه‌ریزی ریاضی به صورت کلی به حل مسئله‌های بهینه‌سازی با استفاده از مدل‌سازی آن به صورت زیر می‌پردازد:

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

حالت خاص دیگری از برنامه‌ریزی ریاضی، برنامه‌ریزی صحیح است که مانند برنامه‌ریزی خطی است با این تفاوت که در برنامه‌ریزی صحیح می‌توان برروی برخی یا تمام متغیرها قید صحیح بودن را اضافه کرد. بدین صورت دیگر لزوما نمی‌توان برنامه‌ریزی صحیح را در زمان سریع حل کرد، اما تبدیل مسئله‌های الگوریتمی و مسئله‌های بهینه‌سازی ترکیبیاتی به برنامه‌ریزی صحیح کاری بسیار ساده‌تر است. از برنامه‌ریزی صحیح مخصوصا برای ارائه الگوریتم‌های تقریبی بسیار استفاده می‌شود.

اما حالت‌های دیگری نیز از برنامه‌ریزی ریاضی وجود دارد که نه برنامه‌ریزی خطی هستند و نه برنامه‌ریزی صحیح. برنامه‌ریزی نیمه معین، برنامه‌ریزی محدب، و برنامه‌ریزی غیر خطی برخی از انواع برنامه‌ریزی‌های ریاضی است.

درس برنامه‌ریزی ریاضی به بررسی انواع برنامه‌ریزی‌های ریاضی، کاربردهای آن در حل مسئله‌های مختلف و الگوریتم‌های یافتن جواب برای یک برنامه‌ریزی ریاضی می‌پردازد. این درس می‌تواند با سوگیری‌های مختلفی ارائه شود.

در این ترم، تاکید بر برنامه‌ریزی نیمه معین، تعریف آن، روش‌های حل آن، و کاربردهای آن در ارائه الگوریتم‌های تقریبی برای مسئله‌های ترکیبیاتی است.

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

آشنایی با بهینه‌سازی ترکیبیاتی و بهینه‌سازی محدب و الگوریتم‌های تقریبی و پیچیدگی محاسباتی به همراهی با درس کمک فراوانی خواهد کرد.

• مروری بر الگوریتم‌های تقریبی
• چرا برنامه‌ریزی نیمه معین برای الگوریتم‌های تقریبی
• برنامه‌ریزی نیمه معین
• ظرفیت شنون
• برنامه‌ریزی کنج و دوگان
• حل تقریبی برنامه‌ریزی معین
• یک الگوریتم نقطه درونی برای برنامه‌ریزی معین
• برنامه‌ریزی هم‌مثبت
• کران پایین برای الگوریتم گومنز-ویلیامسون
• رنگ‌آمیزی گراف ۳-رنگ‌پذیری
• بیشینه‌سازی فرم مربعی روی گراف
• رنگ‌آمیزی با دیسکریپنسی پایین
• مسئله ارضای قیود
• گرد کردن با مینیاتورها

• Gärtner, Bernd, and Jiri Matousek. Approximation algorithms and semidefinite programming. Springer Science & Business Media, 2012.
• Grötschel, Martin, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization. Vol. 2. Springer Science & Business Media, 2012.

• پایان‌ترم: ۶ نمره
• آزمونک: ۴ نمره، ۵ آزمونک
• تمرین: ۵ نمره
• تمرین خانه‌بر: ۵ نمره

• در مورد برنامه‌ریزی ریاضی و تاریخچه آن
• درس مشابهی که کتاب منبع درس نیز بر اساس محتوای آن درس تهیه شده.
  • اطلاعات اصلی در مرود این درس را می‌توانید اینجا بیابید.