درس بهینه‌سازی ترکیبیاتی (پاییز ۹۴)

(کامل خواهد شد)

  • مقطع: درس کارشناسی ارشد
  • فیلم‌های کلاس در سایت ویدئوهای دانشکده ریاضی
  • جزوه‌های تایپ شده به زودی در اینجا قرار خواهد گرفت.

منابع:

  • منبع اصلی درس: اسلایدهای درس آقای وندراک
  • کتاب‌های زیر:
  • Introduction to Linear Optimization (Athena Scientific Series in Optimization and Neural Computation, 6) Third printing Edition, by Dimitris Bertsimas (Author), John N. Tsitsiklis (Author), John Tsitsiklis (Author)
  • Understanding and Using Linear Programming (Universitext) Paperback – November 14, 2006
    by Jiri Matousek (Author), Bernd Gärtner (Author)
  • Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics) 5th ed. 2012 Edition
    by Bernhard Korte (Author), Jens Vygen (Author)
  • Combinatorial Optimization: Algorithms and Complexity (Dover Books on Computer Science) Unabridged Edition
    by Christos H. Papadimitriou (Author), Kenneth Steiglitz (Author)
  • The Design of Approximation Algorithms 1st Edition
    by David P. Williamson (Author), David B. Shmoys (Author)
  • Integer Programming (Graduate Texts in Mathematics) 2014th Edition
    by Michele Conforti (Author), Gerard Cornuejols (Author), Giacomo Zambelli (Author)
  • Combinatorial Optimization (3 volume, A,B, & C) 1st Edition
    by Alexander Schrijver (Author)

مبحث ۱) برنامه‌ریزی صحیح و برنامه‌ریزی خطی

مبحث ۲) نظریه برنامه‌ریزی خطی و دوگان

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

هم‌چنین مبحث دوگان‌ها در برنامه‌ریزی خطی و قضیه Farkas و قضیه دوگان را نیز مطرح و اثبات می‌کنیم.

مبحث ۳) چندوجهی تطابق در گراف دوبخشی

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

مبحث ۴) الگوریتم تطابق در گراف غیردوبخشی

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

مبحث ۵) چندوجهی تطابق در گراف غیر دوبخشی

تطابق‌ها در گراف‌های غیردوبخشی را مشخص کرد. در این مبحث توصیف چندوجهی در گراف‌های غیردوبخشی را ارائه می‌کنیم.

مبحث ۶) روش اولیه-دوگان

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

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

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

مبحث ۷) ماترویدها

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

مبحث ۸) توابع زیرپیمانه‌ای

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

مبحث ۹) نگاهی وسیع به بهینه‌سازی ترکیبیاتی

فیلم Michel Goemans در این مورد را نگاه می‌کنیم.