Skip to content
بازگشت به نتایج جست‌وجو

برنامه‌ریزی عدد صحیح مختلط قوی — بهینه‌سازی با متغیرهای صحیح تحت عدم قطعیت

معرفی‌شده توسط
Ben-Tal & Nemirovski; Bertsimas & Sim
سال
1998–2004
نوع
Deterministic robust reformulation of MIP under uncertainty
خانواده
Simulation / optimization

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

برنامه‌ریزی عدد صحیح مختلط قوی (RMIP) برنامه‌ریزی عدد صحیح مختلط را با بهینه‌سازی قوی ترکیب می‌کند تا راه‌حل‌هایی بیابد که با وجود پارامترهای نامشخص، عملی و تقریباً بهینه باقی می‌مانند. به جای فرض داده‌های ثابت، تصمیمات را در برابر تحقق‌های بدبینانه یا بدترین حالت ورودی‌های نامشخص محافظت می‌کند و از یک مجموعه عدم قطعیت صریح برای کنترل درجه محافظه‌کاری استفاده می‌کند، در حالی که ساختار ترکیبی تصمیمات صحیح را حفظ می‌کند.

شهود پشت روش

برنامه‌های عدد صحیح مختلط کلاسیک فرض می‌کنند که تمام داده‌ها دقیقاً شناخته شده‌اند، اما در عمل هزینه‌ها، تقاضاها و زمان‌های پردازش نوسان می‌کنند. RMIP می‌پرسد: اگر پارامترهای نامشخص بدترین مقادیر قابل قبول خود را در یک محدوده تعریف شده بگیرند، کدام تصمیمات صحیح و پیوسته بهترین هستند؟ با جاسازی عدم قطعیت مستقیماً در مدل بهینه‌سازی، RMIP برنامه‌هایی را تولید می‌کند که بدون توسل به سناریوهای احتمالی متعدد، در برابر تغییرات داده مصون هستند. رویکرد 'بودجه عدم قطعیت' Bertsimas-Sim به متخصصان اجازه می‌دهد تا بین استحکام کامل و کارایی میانگین، انتخاب کنند و بده‌بستان بین حفاظت و هزینه را صریح می‌کند.

تاریخ

بهینه‌سازی قوی به عنوان یک پارادایم قابل پیگیری توسط Ben-Tal و Nemirovski در اواخر دهه 1990 برای مسائل پیوسته تأسیس شد. Bertsimas و Sim (2004) آن را به برنامه‌های خطی با مجموعه بودجه عدم قطعیت که قابلیت پیگیری خطی را حفظ می‌کند، گسترش دادند. کارهای بعدی این چارچوب را با برنامه‌ریزی عدد صحیح ادغام کردند و RMIP را تولید کردند که در تحقیقات زنجیره تأمین، انرژی و حمل و نقل در طول دهه 2010 به طور گسترده پذیرفته شد.

چه زمانی استفاده شود

هنگامی که تصمیمات شامل انتخاب‌های صحیح یا دودویی (مکان‌یابی تسهیلات، تعیین اندازه دسته، طراحی شبکه، زمان‌بندی) هستند و برخی پارامترهای ورودی نامشخص هستند اما توزیع‌های احتمال در دسترس یا قابل اعتماد نیستند، از RMIP استفاده کنید. این روش زمانی مناسب است که نقض محدودیت‌ها غیرقابل قبول باشد (الزامات استحکام سخت) و یک تضمین محافظه‌کارانه اما قطعی به بهینه‌سازی ارزش مورد انتظار ترجیح داده شود. زمانی که توزیع‌های عدم قطعیت به خوبی مشخص شده‌اند و تقریب میانگین نمونه یا MIP تصادفی امکان‌پذیر است؛ زمانی که تمام متغیرهای تصمیم پیوسته هستند (به جای آن از LP قوی استفاده کنید)؛ یا زمانی که مجموعه عدم قطعیت آنقدر بزرگ است که مدل بدون استراتژی‌های تجزیه غیرقابل پیگیری می‌شود، استفاده نکنید.

محدودیت‌ها و ملاحظات

  • به طور پیش‌فرض محافظه‌کار است — هدف بدترین حالت معمولاً بدتر از هدف میانگین برنامه‌ریزی تصادفی است.
  • انتخاب یک مجموعه عدم قطعیت مناسب نیازمند دانش دامنه است؛ یک مجموعه انتخاب شده نادرست منجر به محافظت بیش از حد یا کمبود حفاظت می‌شود.
  • بازسازی‌های قوی می‌توانند اندازه مدل را به طور قابل توجهی افزایش دهند (متغیرها و محدودیت‌های اضافی)، بار محاسباتی را برای نمونه‌های بزرگ افزایش می‌دهند.
  • بیانیه‌های احتمال در مورد عملکرد راه حل ارائه نمی‌دهد؛ MIP تصادفی زمانی که معیارهای ریسک احتمالی مورد نیاز است، مناسب‌تر است.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

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

کاربردها

  • طراحی شبکه زنجیره تأمین تحت تقاضای نامشخص و زمان‌های تحویل
  • برنامه‌ریزی ظرفیت سیستم انرژی با تولید تجدیدپذیر نامشخص
  • مکان‌یابی تسهیلات مراقبت‌های بهداشتی تحت عدم قطعیت تقاضای بیمار
  • زمان‌بندی خدمه خطوط هوایی با تأخیرهای پروازی نامشخص
  • تعیین اندازه دسته تولید تحت هزینه‌ها و زمان‌های پردازش نامشخص
  • مسیریابی شبکه مخابراتی با حجم ترافیک نامشخص

چگونه کار می‌کند

چگونه کار می‌کند

1

برنامه‌ریزی عدد صحیح مختلط اسمی را فرموله کنید: متغیرهای تصمیم (دودویی یا صحیح y، پیوسته x)، تابع هدف و محدودیت‌ها را شناسایی کنید. پارامترهایی (ضرایب هزینه، مقادیر سمت راست، ورودی‌های ماتریس فناوری) را که نامشخص هستند و باید محافظت شوند، مشخص کنید.

2

یک مجموعه عدم قطعیت U برای پارامترهای نامشخص تعریف کنید. انتخاب‌های رایج عبارتند از مجموعه‌های جعبه‌ای (محدوده‌های بازه برای هر پارامتر)، مجموعه‌های بیضوی (عدم قطعیت همبسته)، یا مجموعه بودجه Bertsimas-Sim (حداکثر Gamma پارامتر به طور همزمان منحرف می‌شوند)، که در آن Gamma محافظه‌کاری را کنترل می‌کند.

3

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

4

برنامه‌ریزی عدد صحیح مختلط بازسازی شده قوی را با یک حل‌کننده استاندارد شاخه و کران یا شاخه و برش حل کنید (به عنوان مثال، CPLEX، Gurobi، SCIP). بازسازی الزامات یکپارچگی را بر روی y حفظ می‌کند. برای نمونه‌های در مقیاس بزرگ، تجزیه بندرز یا روش‌های صفحه برش می‌توانند مسئله را تجزیه کنند.

5

راه حل قوی را با موارد زیر ارزیابی کنید: (الف) محاسبه مقدار هدف آن تحت پارامترهای اسمی و بدترین حالت، (ب) مقایسه با راه حل برنامه‌ریزی تصادفی با استفاده از سناریوهای مونت کارلو، و (ج) گزارش قیمت استحکام — هزینه اضافی پرداختی برای حفاظت در برابر عدم قطعیت.

دام‌های رایج

  • تنظیم Gamma=0 (بودجه عدم قطعیت صفر) MIP اسمی را تکرار می‌کند و هیچ حفاظتی ارائه نمی‌دهد؛ Gamma بیش از حد بزرگ منجر به راه‌حل‌های بیش از حد محافظه‌کارانه و غیرعملیاتی می‌شود.
  • در نظر گرفتن همزمان تمام پارامترها به عنوان نامشخص می‌تواند بازسازی را غیرقابل پیگیری کند — پارامترهای نامشخص حیاتی را برای محافظت انتخابی شناسایی کنید.
  • نادیده گرفتن ساختار همبستگی عدم قطعیت‌ها ممکن است منجر به مجموعه عدم قطعیت بیش از حد بدبینانه شود؛ مجموعه‌های بیضوی در صورت شناخته شدن همبستگی‌ها ترجیح داده می‌شوند.
  • گزارش تنها هدف بدترین حالت بدون مقایسه آن با معیارهای اسمی یا تصادفی، تصویری ناقص از کیفیت راه حل ارائه می‌دهد.

پرسش‌های متداول

RMIP چگونه با برنامه‌ریزی عدد صحیح مختلط تصادفی متفاوت است؟

MIP تصادفی از توزیع‌های احتمال استفاده می‌کند و عملکرد مورد انتظار را در سناریوهای نمونه‌برداری شده بهینه می‌کند، در حالی که RMIP در برابر بدترین حالت در یک مجموعه عدم قطعیت بدون نیاز به اطلاعات توزیعی محافظت می‌کند. RMIP یک راه حل قطعی قوی واحد ارائه می‌دهد؛ MIP تصادفی یک سیاست ارائه می‌دهد که به طور متوسط خوب است.

«قیمت استحکام» چیست و معمولاً چقدر است؟

قیمت استحکام، افزایش درصدی در مقدار هدف در مقایسه با بهینه اسمی (بدون عدم قطعیت) است. Bertsimas و Sim نشان می‌دهند که این مقدار تقریباً به طور خطی با Gamma رشد می‌کند اما برای مقادیر بودجه معمولی، اغلب 5 تا 15 درصد در کاربردهای عملی، همچنان ناچیز است.

آیا RMIP می‌تواند مقادیر سمت راست نامشخص و همچنین ضرایب هزینه نامشخص را مدیریت کند؟

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

آیا RMIP با حل‌کننده‌های استاندارد MIP قابل حل است؟

برای مجموعه بودجه Bertsimas-Sim، بازسازی قوی یک MIP باقی می‌ماند و می‌تواند مستقیماً با حل‌کننده‌هایی مانند CPLEX یا Gurobi حل شود. مجموعه‌های عدم قطعیت بیضوی، برنامه‌های مخروطی مرتبه دوم مختلط (MISOCP) تولید می‌کنند که توسط حل‌کننده‌های مدرن نیز پشتیبانی می‌شوند.

چه زمانی باید مجموعه عدم قطعیت جعبه‌ای را به مجموعه بودجه عدم قطعیت ترجیح دهم؟

مجموعه جعبه‌ای در برابر انحراف همزمان همه پارامترها به نقاط حدی آنها محافظت می‌کند، که اغلب بیش از حد محافظه‌کارانه است. مجموعه بودجه (Gamma) زمانی ترجیح داده می‌شود که انحرافات همزمان بدترین حالت همه پارامترها بعید باشد، زیرا راه‌حل‌های کمتر محافظه‌کارانه و مقرون‌به‌صرفه‌تری را به دست می‌دهد.

روش‌های مرتبط

منابع

  1. Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.

    باز کردن مرجع DOI
    کپی شد.
  2. Ben-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton University Press, Princeton, NJ.

    شابک: 9780691143682
    کپی شد.