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

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

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

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

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

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

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

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

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

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

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

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

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

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

.....