Iterative Methods in Combinatorial Optimization

http://drops.dagstuhl.de/opus/volltexte/2009/2339/pdf/09005.RaviR.2339.pdf

درس بهینه‌سازی ترکیبیاتی دانشگاه خودمان

http://math.sharif.ir/faculties/foroughmand/page/show/130
http://theory.stanford.edu/~jvondrak/CS369P.html

Convex Optimization Theory

مرجع: Convex Optimization Algorithms

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

این مرجع پیشنهاد یکی از دوستان بود که کامنت خصوصی گذاشته بود.

روش تکراری برای رند کردن LP

منبع: http://www.cs.umd.edu/~hajiagha/NetDsgn11/Iterative-Methods-UMD.pdf

برای رند کردن LP روش‌های مختلفی هست:

- وقتی مقدار متغیرهای اعداد اعشاری بزرگ باشد، مثل پوشش رأسی، به نزدیک‌ترین عدد صحیح رند می‌کنیم. (رند کردن قطعی)

- رند کردن تصادفی، مثل مسایل پوشش و بسته‌بندی، در این مسایل هر متغیری را با احتمال مقدار اعشاری آن رند می‌کنیم. (برای متغیرهای صفر و یک)

- رند کردن با جاسازی متریک؟

مثل برش بیشینه

- روش اولیه-ثانویه (primal-dual)

- رند کردن تکراری؟

- ریلکس کردن تکراری؟

من خودم هم نمی‌دانم خیلی از این رند کردن‌ها چطوری کار می‌کنند و آنهایی را هم که می‌دانم نمی‌دانم چرا درست کار می‌کنند. اما این ارائه در مورد رند کردن تکراری است.

رند کردن تکراری:

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

الگوریتم: برای این کار LP را به شکل یک covering LP بنویسید. بعد باید ثابت کنید که متغیر با مقدار بزرگ هست. متغیرهای با مقدار بزرگ را رند کنید. قیدها را طوری تغییر بدهید که باقیمانده‌ی مسأله را مدل کنند. (به نظرم منظورش جایگذاری است.) این کار را تکرار کنید تا همه‌ی متغیرها مقدار صحیح پیدا کنند.

.....

برنامه ریزی خطی و ترکیبیات چندوجهی

http://math.mit.edu/~goemans/18433S13/polyhedral.pdf

Matroid

http://math.mit.edu/~goemans/18433S13/matroid-notes.pdf

http://en.wikipedia.org/wiki/Matroid