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

دقیق بودن یک رویکرد حل در مسائل MODM به این معناست که جواب یا جوابهای اون روی جبهه پارتو سراسری قرار میگیره و یا اصطلاحا نامغلوب (nondominated) هستن و پاسخ کارا (Efficient) برای مسئله به حساب میاد.

روش هایی مثل مجموع وزنی، اپسیلون محدودیتو امثالهم رو در ادبیات گرچه دقیق میگن، ولی این زیاد درست نیست و تضمینی نیست که لزوما جواب اونا کارا و نامغلوب باشه (البته کارای ضعیف هست که اثبات داره) .

روش اپسلون محدودیت تکامل یافته عملکرد خوبی داره و معمولا جبهه پارتو اون سراسری هست.
روش مجموع وزنی گرچه جبهه پارتو میده ولی امکان داره سراسری نباشه و مغلوب باشن. مثل روش اپسیلون محدودیت کلاسیک

نرم بینهایت LP متریک یک تک جواب همواره نامغلوب هست

لکسیکوگرافیک تک جواب میده و همیشه نامغلوب هست. لکسیکوگرافیک وزنی گرچه چندین جواب داره ولی تضمینی بر نامغلوب بودن اون نیست


روش TH ترکیب نرم 1 و نرم بینهایت در روش LP متریک هست و بنظر بند نتایج خوبی میده و پیاده سازی ساده ای هم داره

برنامه ریزی آرمانی ، و یا آرمانی فازی هم تقریبا شبیه LP متریک کار میکنن که نرمال شده باشه

#MODM

تبدیل عدد صحیح به باینری
کاربرد: خطی سازی ضرب متغیر عددصحیح در پیوسته
محدودیت: اگر کران بالا متغییر عددصحیح زیاد باشد، انگاه این رویکرد متغیرهای باینری زیادی نیازی دارد و باعث سخت شدن مسئله خطی میشود

خطی سازی ضرب دو متغیر
"اين خطي سازي تقربي هست و بعضا نتايج خوبي حاصل نمي شود"
#Linearization

Outer Approximation

سلام وقت شما بخیر
رویکرد حل لاگرانژ رو چطور باید متوجه بشیم که برای مدلمون کارایی داره یا نه؟

این سوال در حالی که ظاهر ساده داره، ولی واقعا سوال بسیار مهمی هست و باید جواب درستی و کاملی بهش داده شه. موارد زیر بهترین راه کارها هستن

1- اساس تکنیک آزادسازی لاگرانژ (LR) بر این است که در مسئله قید سخت وقت وجود داره و حذف اون موجب کارایی میشه. اینکه چه قیدی سخت کننده هست برمیگرده به آزمایش های قبلی، ابتکار شما در تشخیص و ... . لذا اگر در مسئله تون قیدی مثل ظرفیت، بودجه و امثالهم وجود داره میشه روی تکنیک LR حساب باز کرد.

2- تکنیک LR بعضا موجب به تجزیه لاگرانژ (LD) میشه که بر اساس اون مسئله به زیر مسائل ساده تر تجزیه میشه. اگر مسئله تجزیه پذیر هست LR و LD کارایی خوبی دارند.

3- مسئله شما یا مشابه در ادبیات پیش تر توسط LR و LD حل شده باشه و در مقالات چاپ شده در ژورنال های معتبر (دقت کنید ژورنالهای معتبر ) نتیجه گرفته باشن که LR کارا هست، میتونید شما هم استفاده کنید

و ....

مهمترین نکات در رابطه با مدل های دوسطحی (Bi-Level programming) که در در سطح دوم (پیرو/Follower) غیرخطی بودن داره به صورت زیر هست:

1- اول برای اینکه این اطلاعات مفید باشه به طور کلی یاداوری میکنم که این مدل ها معمولا در شرایطی رقابتی یا گیم بین دو سازمان یا واحد تصمیم گیری رخ میده که واحد اصلی (یا اصطلاحا Leader ) باید بهینگی واحد پیرو (یا واحدی که تحت تاثیر تصمیمات اون هست یا همون Follower ) رو در نظر بگیره. این مسائل در ادبیات معمولا به بازی استکلبرگ (Stackelberg Game) هم معروف هست.

2- نکته اول اینه که حتی اگر مدل پیرو خطی هم باشه باز هم شرایط KKT تضمین نمیکنه حتما به جواب بهینه برسید. در واقع یکی از خاصیت های این مدل ها اینا که لزوما جواب بهینه ندارن. در واقع اگر پیرو پاسخ بهینه چندگانه داشته باشه در این صورت هیچ لزومی نداره که لیدر بتونه در شرایط بهینه قرار بگیره.
این رو گفتم که اشتباه نکنیم و فکر کنیم اگر سطح دوم / پیرو خطی هست دیگه راحت یک KKT بزنیم و تمام. البته با فرض اینکه پیرو به هر تصمیم لیدر فقط یک واکنش بهینه داره استفاد از KKT درست هست در حالت خطی. در حالت کلی چه خطی و چه غیرخطی ما فرض مذکور رو داریم(البته این فرض در برخی از مسائل واقعا غیرمنطقی هست ولی در مقالات معمولا این فرض هست)

3- در مدلهای غیرخطی که مدل قابل خطی سازی هست (مثل ضرب باینری در پیوسته و امثالهم) بهتره مدل خطی شه. یا از تقریب های خطی ساز استفاده شه که حتی این تقریب به نفع پیرو هم باشه. مثلا اگر کمینه سازی هزینه پیرو رو در نظر گرفتیم، تقریب خطی موجب کران پایین هزینه برای اون بشه نه کران بالا)

4- دقت داشته باشیم که ضرب متغیر تصمیم گیری لیدر در متغیر تصمیم گیری پیرو باعث نمیشه مدل پیرو غیرخطی باشه. چراکه تصمیم لیدر برای پیرو ثابت در نظر گرفته میشه. یعنی شما در این شرایط هم راحت KKT رو بزنید (البته اون فرض فراموش نشه). لازم به توضیح است در این شرایط مطمئنا مدل تک سطحی نهایی بعد از اعمال KKT غیرخطی میشه

5- در مدلهای غیرخطی، در صورتی که مدل پیرو کاملا پیوسته است (متغیر باینری و عددصحیح) نداشته باشه. اولین کاری که بهتره انجام شود، بررسی تحدب است. حالا نه لزوما با ماتریس هسین(Hessian) بلکه هر تکنیک که میتونید اعمال کنید. (مثلا جمع محدب ها محدب هست و توان 2 ها محدب هستن و ...) اگر تحدب برقرار هست با خیال راحت قیود KKT رو جایگزین کنید. باز هم میگم در این حالت هم هنوز اون فرض که عرض کردم رو باید قبول کرده باشیم. پر واضح است که اینجا هم مدل نهایی غیرخطی هست. نکته جالب اینجاست که حتی اگر مدل پیرو تحدب رو داشته باشه و KKT بزنید، باز هم هیچ تضمینی نیست مدل نهایی محدب باشه و اتفاقا معمولا عدم تحدب داره و خود این هم چالش است. حالا اگر مدل عددصحیح و غیره هم داشته باشه که چالش دو چندان هم میشه. البته در این شرایط معمولا خیلی راحت مدل نهایی رو یک Solver مثل BARON و ... داده میشه که حل کنه!!! که مطمئنا این حرکت چندان درست نیست و امکان داره لیدر بشدت در بهینگی محلی قرار بگیره (تازه اگر BARON یا BONMIN و امثالهم حل کنن مدل نهایی رو)

6- حالا اگر 5 مورد بالا را برای شما صدق نمیکنه و یا دنبال راه کارهای دیگری هستید؛ روش پیشنهادی بنده به صورت زیر هست که در کارهای مختلفی با تعامل GAMS و MATLAB و یا CPLEX و یا JAVA و CPLEX قابل پیاده سازی هست.

گام 1) جواب اولیه X برای متغیرهای تصمیم گیری لیدر در نظر گرفته شود.

گام 2) مسئله بهینه سازی پیرو (که یک مدل غیر خطی هست حل شود) با توجه به غیرخطی بودن این مدل موارد زیر پیشنهاد میشه:
* با رویکردهای حل ابتکاری و یا فراابتکاری حل شود و پاسخ نزدیک به بهینه Y (که امکان داره بهینه هم باشه) برای پیرو بدست آورده شود.
* با روش های برنامه ریزی عیرحطی (از جمله روش SQP و یا Trust Region ) پاسخ نزدیک به بهینه Y (که امکان داره بهینه هم باشه) برای پیرو بدست آورده شود.

گام 3) مدل بهینه سازی لیدر، با ثابت کردن تصمیم Y برای پیرو، حل می شود. حالا امکان داره این مدل خطی یاشه که از solverهایی مثل CPLEX و امثالهم استفاده میکنید و سریع X جدید رو برای لیدر بدست میاد. یا امکان داره خود این مدل هم غیرخطی باشه که باز هم دو روش * گام 2 پیشنهاد میشه و یا حتی solver غیرخطی موجود در GAMS و ... .

گام 4) تصمیم لیدر در گام 3 آپدیت میشه و مجددا به گام 2 برمیگردیم و این رویه تاجایی پیدا میکنه که بهبود قابل توجه ای در تابع هدف لیدر رخ نده.
در رویه فوق اگرچه تضمینی برای بهینه سراسری نیست، ولی با تغییر در پاسخ اولیه A میتونه به جواب های مختلفی همگرا شه و اگر N مرتبه در مقدار اولیه X تغییر ایجاد شود مطمئنا بهترین پاسخ آن بسیار نزدیک به بهینه است (مطمئنا هرچی N بیشتر و جواب های اولیه متمایزتر باشه، کیفیت پاسخ نهایی بهتر میشه ).

Integer Programming by Prof. Wosley

یک کتاب درجه 1 در خصوص تاریخچه OR و تکنیک های برنامه ریزی ریاضی برای بهینه سازی

برای تقویت زبان هم خوبه؛ بیان شیرین و خوبی داره.

دو کد بسیار کارا برای حل مسئله مسیریابی وسایل نقلیه (VRP) 👆🏻👆🏻
یک مزیت بسیار خوب که دو کد فوق دارند، اینه که با توجه به همگون بودن وسایل نقلیه، اندیس وسیله نقلیه تعریف نشده که بشدت موجب کارایی کدها در عمل شده.

برای استفاده همه دوستان 🌷

این مقاله اصلی خود سوستر هست که در سال 1972 چاپ شده

دقت کنید که روش Soyster بسیار محافظه کار هست و اصطلاحا Conservatism بالایی داره که در عمل چندان مناسب نیست. رویکردهای مختلف Robust Optimization در کتاب Ben-Tal و یا رویکرد Bertsimas & Sim کاراتر هستن و در مقالات متعددی مورد استفاده قرار گرفتن

توضیحاتی که نوشتید کاملا درست هستید. فقط برای محاسبه EVPI ی خورده اشتباه کردید و اونجا هم که گفتید روش های حل میشن EV و WS اشتباه گفتید. میشن EV و SP . چون اصلا WS روش حل نیست بلکه یک رویه است که مثلا شما بهترین وضعیت برای هر سناریو رو بدست میارید.

اول دقت کنید برای حل یک مسئله بهینه سازی تحت شرایط عدم قطعیت سناریومحور دو رویکرد اصلی وجود داره.

یک رویکرد EV یا همون مقدار انتظاری که گفتید
و دوم رویکرد برنامه ریزی تصادفی سناریومحور (یا همون SP)

حالا برای ارزیابی پاسخ رویکرد SP شما دو تا حالت زیر رو میتونید انجام بدید.

1- معیار VSS رو به صورت زیر محاسبه کنید
VSS= Z_SP - Z_EV

و در مسئله min این مقدار همواره بیشتر یا مساوی 0 است. هرچی بیشتر باشه نشون میده رویکرد تصادفی با ارزش تر است.


2- مقدار بهترین حالت هر سناریو که اصطلاحا Waite and See یا WS میگن رو برای هر سناریو محاسبه کنید و بهترین مقدار میانگین رو بدست بیارید. حالا ارزش اطلاعات کامل رو به یکی از دو صورت زیر محاسبه کنید

حالت الف)
EVPI= Z_SP - Z_WS

حالت ب)
EVPI= Z_EV - Z_WS
که هرچه این مقادیر بیشتر باشن نشون میده که داشتن اطلاعات در مورد اینکه دقیقا کدوم سناریو میخواد رخ بده، باارزش تر است. من خودم شخصا معیار ب رو بیشتر ترجیح میدم ولی در کتب و مقالات معمولا همون الف رو مینویسن.

دیگه اینا رو از این بیشتر و بهتر نمیشه در گروه توضیح داد 😉

الگوریتم تجزیه بندرز (Benders Decomposition) کلاسیک برای مسائلی MILP ارائه شده و تجزیه بر اساس نوع متغیرها صورت میگیره و مستلزم اونه که یک زیر مسئله کاملا پیوسته باشه. اما در توسعه الگوریتم بندرز، تجزیه میتونه بر اساس ساختار ماتریس فتی نیز صورت بگیره. این حالت دوم میتونه برای هر نوع مسئله باشه. در حالتی که مسئله کاملا پیوسته باشد به الگوریتم L-Shaped معروف هست. برای مسائل کاملا عدد صحیح هم حالت دوم مستلزم تجزیه پذیر بودن مسئله بر اساس ساختار ضرایب/ماتریس فنی هست. به مثال زیر توجه کنید

min c1x1 + c2x2 + c3x3

s.t
Ax1 + Bx2<=b
Vx3 + Kx2<=u

x1 , x2 , x3 are integer

در این مسئله، ساختار ضرایب فنی به صورتی است که مسئله نسبت به متغیر x2 کاملا تجزیه پذیر است و به دو زیر مسئله کوچک تر تجزیه میشه. این نوع تجزیه رو هم چون روی متغیر صورت میگیره به افتخار پروفسور بندرز، تجزیه بندرز میگن (هرچند با فرم کلاسیک تجزیه بندرز فرق داره) دقت کنید در این مثال که عرض کردم اگر فرض کنید بعد دسته متغیرهای x1 و x3 زیاد باشه و بعد متغیر x2 کم باشه، واقعا تجزیه میتونه بسیار کارآمد باشه. یک یاداوری هم کنم اینجا اگر متغیرها همگی پیوسته بودن به تجزیه L-shaped میرسیدیم که اون هم الهام گرفته از تجزیه بندرز است و چند سال بعد از مقاله بندرز چاپ شده.

کتاب پروفسور conejo در گروه قرار داد شده که پیشنهاد میکنم مطالعه کنید.

دو مقاله زیر رو مطالعه کنید.

مقاله اول نوشته پروفسر روکافلر و پروفسر یورسایف هست که در سال 1999 برای اولین بار به ضعف VaR اشاره مکینن و یک معیار جدید به اسم CVaR رو معرفی میکنن که ارزش انتظاری مقادیری کمتر از VaR (برای حالت سود) و مقادیر بیشتر از VaR (برای حالت زیان) هست.

مقاله دوم هم که دقیقا در سال 1999 توسط پروفسر آرتزنر و همکارنشون چاپ شده، به معرفی TVaR میپردازه و گرچه در بیان کمی متفاوت هستن، ولی در مفهوم و فرمولاسیون دقیقا همون CVaR هست.

"بنظر بنده اگر تغییر جزیی هم هست مرتبط با استنباط متفاوت خوانندگان و یا نویسندگان مقالات بعدی هست (این دو مقاله بیش از 15هزار ارجاع دارند)". وگرنه مفهوم TVaR و CVaR بر اساس مطالعه بنده از هر دو مقاله، کاملا یکسان هست.

👇🏻👇🏻