برنامهریزی عدد صحیح مقاوم — بهینهسازی تحت عدم قطعیت با قیود تمامیت
- معرفیشده توسط
- Bertsimas, D. and Sim, M.
- سال
- 2003
- نوع
- Deterministic robust optimization with integer variables
- خانواده
- Simulation / optimization
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
برنامهریزی عدد صحیح مقاوم (RIP) راهحلهای صحیح یا دودویی را مییابد که در تمام سناریوهای یک مجموعه عدم قطعیت معین، امکانپذیر و نزدیک به بهینه باقی میمانند.
RIP به جای فرض دانش دقیق دادهها، در برابر بدترین حالت تحقق هزینههای نامعلوم یا ضرایب قید، پوشش ریسک میدهد و تصمیماتی را ارائه میدهد که حتی زمانی که ورودیها از مقادیر اسمی خود منحرف میشوند، عملکرد خوبی خواهند داشت.
شهود پشت روش
بسیاری از تصمیمات دنیای واقعی — برنامههای تولید، طراحی شبکه، تخصیص منابع — شامل اعداد صحیح هستند (شما نمیتوانید نیم واحد تولید کنید یا نیم تأسیسات بسازید) و دادههای نامعلوم (هزینهها، تقاضاها، زمانهای سفر نوسان دارند). برنامهریزی عدد صحیح کلاسیک عدم قطعیت را نادیده میگیرد و میتواند راهحلهایی ارائه دهد که هنگام متفاوت بودن ورودیها از تخمینها، به شدت شکست میخورند. برنامهریزی عدد صحیح مقاوم به طور صریح این عدم قطعیت را از طریق یک مجموعه عدم قطعیت مدلسازی میکند و راهحل صحیح را که در بدترین حالت بهترین عملکرد را دارد، مییابد. رویکرد برتسیماس-سیم از پارامتر بودجه عدم قطعیت برای کنترل محافظهکاری استفاده میکند: با بودجه صفر، مسئله به برنامهریزی عدد صحیح قطعی کاهش مییابد؛ با افزایش بودجه، راهحلها به طور فزایندهای در برابر اغتشاشات داده محافظت میشوند، البته با هزینه ارزش هدف.
تاریخ
مطالعه سیستماتیک بهینهسازی گسسته مقاوم توسط برتسیماس و سیم در مقاله سال ۲۰۰۳ آنها که مدل بودجه عدم قطعیت را برای مسائل گسسته معرفی کرد، پیشرفت کرد و بر اساس کارهای قبلی LP مقاوم توسط بن-تال و نمیروفسکی (۱۹۹۸) و ال غاوی و لبرت (۱۹۹۷) بنا شد. برتسیماس و سیم نشان دادند که همتایان مقاوم برنامههای عدد صحیح تحت عدم قطعیت بودجه، MIPهای قابل حل باقی میمانند و باعث کاربرد گسترده در لجستیک، طراحی شبکه و زمانبندی شدند. مونوگراف سال ۲۰۰۹ توسط بن-تال، ال غاوی و نمیروفسکی مبانی نظری بهینهسازی مقاوم را در تنظیمات پیوسته و گسسته تثبیت کرد.
چه زمانی استفاده شود
هنگامی که تصمیمات شامل انتخابهای گسسته (تخصیص دودویی، طراحی شبکه، زمانبندی، اندازهگیری دستهای) هستند و دادههای ورودی نامعلوم اما در یک مجموعه شناخته شده محدود هستند، از برنامهریزی عدد صحیح مقاوم استفاده کنید. این روش زمانی ترجیح داده میشود که توزیع احتمال عدم قطعیت ناشناخته یا غیرقابل اعتماد باشد و تضمین بدترین حالت مورد نیاز باشد. زمانی از RIP استفاده نکنید که عدم قطعیت صرفاً تصادفی با توزیعهای به خوبی تخمین زده شده باشد (به جای آن از برنامهریزی تصادفی استفاده کنید)، زمانی که مسئله صرفاً پیوسته است (از برنامهریزی خطی مقاوم استفاده کنید)، زمانی که مجموعه عدم قطعیت بیش از حد محافظهکارانه است و قیمت مقاومت غیرقابل قبول است، یا زمانی که اندازه مسئله حتی برنامهریزی عدد صحیح اسمی را نیز غیرقابل حل میکند.
محدودیتها و ملاحظات
- جهتگیری بدترین حالت میتواند بیش از حد محافظهکارانه باشد و راهحلهایی با مقادیر هدف به طور قابل توجهی بالاتر از بهینه قطعی تولید کند، حتی زمانی که سناریوهای متخاصم بعید هستند.
- قابلیت حل به انتخاب مجموعه عدم قطعیت بستگی دارد؛ مجموعههای محدب یا غیرمحدب عمومی ممکن است همتای مقاوم را از نظر محاسباتی دشوار کنند.
- اطلاعات احتمال را به طور طبیعی در بر نمیگیرد؛ رویدادهای نادر اما با تأثیر بالا با اغتشاشات محتمل یکسان رفتار میشوند.
- برنامههای عدد صحیح مقاوم در مقیاس بزرگ همچنان میتوانند از نظر محاسباتی پرهزینه باشند، به ویژه برای مسائلی با پارامترهای نامعلوم زیاد.
- انتخاب مجموعه عدم قطعیت و سطح بودجه مناسب نیازمند تخصص دامنه است و میتواند به طور قابل توجهی بر نتایج تأثیر بگذارد.
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- تضمینهای قطعی بدترین حالت را بدون نیاز به دانش توزیع احتمال پارامترهای نامعلوم ارائه میدهد.
- چارچوب بودجه عدم قطعیت برتسیماس-سیم، همتای مقاوم را قابل حل نگه میدارد — اغلب یک MIP استاندارد با اندازهای مشابه مسئله اسمی.
- سطح محافظهکاری از طریق یک پارامتر واحد بودجه Gamma به راحتی کنترل میشود و امکان تحلیل مبادله صریح بین حفاظت و هزینه را فراهم میکند.
- در طیف گستردهای از حوزهها قابل اجرا است: لجستیک، انرژی، مالی، مخابرات، زمانبندی.
- راهحلها از نظر عملی قابل پیادهسازی هستند زیرا بدترین حالت سناریو محدود و قابل تأیید است.
کاربردها
- مکانیابی مقاوم تأسیسات و طراحی شبکه تحت تقاضاهای نامعلوم یا زمانهای سفر
- اندازهگیری دستهای و زمانبندی تولید با زمانهای پردازش نامعلوم یا نرخهای بازده
- بهینهسازی سبد سهام با قیود کاردینالیتی و بازده دارایی نامعلوم
- پاسخ اضطراری و لجستیک بشردوستانه تحت پارامترهای بلایای نامعلوم
- برنامهریزی سیستم انرژی (تعهد واحد، گسترش تولید) با خروجی تجدیدپذیر نامعلوم
- مسیریابی شبکه مخابرات تحت تقاضاهای ترافیک نامعلوم
چگونه کار میکند
چگونه کار میکند
برنامهریزی عدد صحیح را با پارامترهای نامعلوم فرموله کنید: کمینهسازی (یا بیشینهسازی) یک هدف بدترین حالت تحت قیودی که باید برای تمام تحققها در مجموعه عدم قطعیت برقرار باشند. متغیرهای تصمیم x باید صحیح یا دودویی باشند و مسئله به عنوان یک ساختار دوسطحی کمینه-بیشینه (یا بیشینه-کمینه) مطرح میشود که در آن مسئله درونی بدترین حالت سناریو را انتخاب میکند.
فرمول
\min_{x \in \mathcal{X}} \max_{\xi \in \mathcal{U}} c(\xi)^\top x \quad \text{s.t.} \quad A(\xi)x \leq b,\; x \in \mathbb{Z}^nیک مجموعه عدم قطعیت U تعریف کنید که دامنه قابل قبول تغییر پارامتر را در بر میگیرد. انتخابهای رایج شامل مجموعههای جعبهای (حدود بازه مستقل برای هر پارامتر)، مجموعههای بیضوی (عدم قطعیت همبسته) و مجموعه بودجه عدم قطعیت برتسیماس-سیم است که در آن حداکثر Gamma پارامتر به طور همزمان از مقادیر اسمی خود منحرف میشوند. بودجه Gamma اهرم کلیدی محافظهکاری است.
فرمول
\mathcal{U} = \{\xi : \|\xi - \hat{\xi}\|_\infty \leq \Gamma\} \quad (\text{budget-of-uncertainty, Bertsimas-Sim})مسئله درونی بیشینهسازی بدترین حالت را دوگانهسازی یا بازفرموله کنید تا یک برنامهریزی عدد صحیح مختلط تک سطحی به دست آید. تحت مدل بودجه عدم قطعیت، همتای مقاوم متغیرهای پیوسته کمکی و قیود خطی را معرفی میکند و قابلیت حل مسائل استاندارد شاخه و کران یا شاخه و برش را بدون شمارش سناریوی نمایی حفظ میکند.
برنامهریزی عدد صحیح مقاوم بازفرموله شده را با استفاده از یک حلکننده استاندارد MIP (CPLEX، Gurobi، SCIP) یا روش شاخه و کران تخصصی با رویههای کرانبندی مقاوم حل کنید. برای نمونههای بزرگ، روشهای تجزیه مانند تجزیه بندر یا تولید ستون و قید را میتوان برای جداسازی مسئله اصلی عدد صحیح از مسئله فرعی متخاصم به کار برد.
راهحل مقاوم را در برابر بهینه قطعی و در برابر مجموعهای از سناریوهای خارج از نمونه ارزیابی کنید. قیمت مقاومت (شکاف هدف بین راهحلهای مقاوم و اسمی) را گزارش دهید و تأیید کنید که راهحل مقاوم تحت بدترین سناریو تمام قیود را برآورده میکند. تحلیل حساسیت بر روی Gamma، عملیاتکننده را در مبادله سطح حفاظت در برابر هزینه راهحل راهنمایی میکند.
دامهای رایج
- تنظیم بودجه عدم قطعیت Gamma بیش از حد بالا، راهحلهای بسیار محافظهکارانه و عملاً بیفایده تولید میکند؛ کالیبراسیون Gamma بر اساس فراوانی انحراف تاریخی توصیه میشود.
- نادیده گرفتن تأیید اینکه بازفرمولاسیون همتای مقاوم برای مجموعه عدم قطعیت انتخاب شده معتبر است — برخی بازفرمولاسیونها فقط برای انواع خاصی از مجموعهها (به عنوان مثال، مجموعههای بودجه، نه بیضوی) اعمال میشوند.
- اشتباه گرفتن برنامهریزی عدد صحیح مقاوم با برنامهریزی عدد صحیح تصادفی: RIP مقدار مورد انتظار را بهینه نمیکند و به درخت سناریو یا توزیع احتمال نیاز ندارد.
- نادیده گرفتن تحلیل قیمت مقاومت — عملیاتکنندگان باید همیشه مقادیر هدف مقاوم و اسمی را مقایسه کنند تا قضاوت کنند که آیا حفاظت ارزش هزینه را دارد.
- اعمال RIP به مسائلی که در آنها عدم قطعیت بر سمت راست غیرخطی تأثیر میگذارد بدون تأیید اینکه مسئله فرعی حاصل قابل حل باقی میماند.
پرسشهای متداول
برنامهریزی عدد صحیح مقاوم چگونه با برنامهریزی عدد صحیح تصادفی تفاوت دارد؟
برنامهریزی عدد صحیح تصادفی عملکرد مورد انتظار را بر روی یک توزیع احتمال سناریوها بهینه میکند و معمولاً به درختان سناریو نیاز دارد. برنامهریزی عدد صحیح مقاوم عملکرد بدترین حالت را بر روی یک مجموعه عدم قطعیت بهینه میکند و به هیچ توزیع احتمالی نیاز ندارد — فقط به حدود عدم قطعیت. RIP تضمینهای امکانپذیری سخت ارائه میدهد؛ stochastic IP تضمینهای احتمالی ارائه میدهد.
بودجه عدم قطعیت چیست و چگونه آن را انتخاب کنم؟
بودجه Gamma تعداد پارامترهای نامعلومی را که به طور همزمان از مقادیر اسمی خود منحرف میشوند، محدود میکند. هنگامی که Gamma برابر با صفر است، مدل به IP قطعی کاهش مییابد. با افزایش Gamma، راهحلها مقاومتر اما پرهزینهتر میشوند. یک قاعده عملی این است که Gamma را با استفاده از دادههای تاریخی تنظیم کنید: اگر در یک پنجره زمانی حداکثر k پارامتر معمولاً منحرف میشوند، Gamma را برابر با k قرار دهید. به طور متناوب، برتسیماس و سیم حدود احتمالی نقض قید را برای یک Gamma معین ارائه میدهند.
آیا همتای مقاوم یک برنامه عدد صحیح هنوز یک برنامه عدد صحیح است؟
بله. تحت مدل بودجه عدم قطعیت، همتای مقاوم متغیرهای کمکی پیوسته اضافی و قیود خطی را معرفی میکند اما تمامیت متغیرهای تصمیم اصلی را حفظ میکند. نتیجه یک MIP استاندارد است که میتواند با حلکنندههای آماده حل شود.
برنامهریزی عدد صحیح مقاوم چه زمانی از نظر محاسباتی قابل حل است؟
قابلیت حل برای مجموعههای عدم قطعیت که مسائل دوگان آنها دارای راهحلهای فرم بسته یا قابل نمایش با LP هستند، مانند مجموعههای جعبهای، مجموعههای بودجه و مجموعههای چندوجهی، برقرار است. عدم قطعیت بیضوی در برنامههای عدد صحیح منجر به قیود مخروط مرتبه دوم میشود که به طور کلی دشوارتر هستند. مسائل با متغیرهای صحیح زیاد و مجموعههای عدم قطعیت بزرگ ممکن است همچنان به روشهای تجزیه نیاز داشته باشند.
آیا برنامهریزی عدد صحیح مقاوم میتواند اهداف چندگانه را مدیریت کند؟
بله، با گسترش به برنامهریزی عدد صحیح چند هدفه مقاوم، که در آن هر هدف به طور مقاوم در نظر گرفته میشود. این منجر به مرزهای پار تو مقاوم میشود. به طور متناوب، عملیاتکنندگان اهداف را مقیاسبندی میکنند (مجموع وزنی یا اپسیلون-قید) و RIP استاندارد را بر روی مسئله تک هدفه حاصل اعمال میکنند.
روشهای مرتبط
منابع
Bertsimas, D., Sim, M. (2003). Robust discrete optimization and network flows. Mathematical Programming, 98(1-3), 49-71.
باز کردن مرجع DOIکپی شد.Ben-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton University Press, Princeton, NJ.
شابک: 9780691143682کپی شد.