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

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

معرفی‌شده توسط
Ralph Gomory (branch-and-bound cuts, 1958); Land & Doig (branch-and-bound, 1960)
سال
1958–1960
نوع
Mathematical optimization
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

بسیاری از مسائل بهینه‌سازی واقعی شامل تصمیماتی هستند که قابل تقسیم نیستند — شما یا یک تأسیسات را باز می‌کنید یا نمی‌کنید، دقیقاً یک کارگر را به یک شیفت اختصاص می‌دهید، یا واحدهای کامل را سفارش می‌دهید. برنامه‌ریزی خطی پیوسته این واقعیت‌ها را نادیده می‌گیرد و می‌تواند پاسخ‌های کسری غیرقابل اجرا تولید کند. MIP مستقیماً یکپارچگی را در مدل اعمال می‌کند. حل‌کننده از طریق شاخه و کران، فضای راه‌حل‌های صحیح شدنی را به طور سیستماتیک کاوش می‌کند: زیرمسائل پیوسته ریلکس شده را برای کران‌دار کردن بهترین راه‌حل ممکن در هر ناحیه حل می‌کند، نواحی‌ای را که نمی‌توانند بهترین راه‌حل صحیح یافت شده تاکنون را بهبود بخشند، حذف می‌کند، و صفحات برشی را برای تنگ کردن جستجو اضافه می‌کند. نتیجه یک طرح بهینه یا نزدیک به بهینه اثبات‌شده است.

تاریخ

بنیان‌های برنامه‌ریزی عدد صحیح توسط رالف گوموری، که روش صفحه برشی را در سال ۱۹۵۸ معرفی کرد، و توسط لند و دویگ، که شاخه و کران را در سال ۱۹۶۰ رسمی کردند، پایه‌گذاری شد. دهه‌های بعدی شاهد توسعه نظریه ریلکساسیون LP، ترکیبیات چندوجهی (ادموندز، پادبرگ، گروتسل) بود و تا دهه ۱۹۹۰ حل‌کننده‌های تجاری، MIP در مقیاس بزرگ را عملی کردند. این حوزه به طور جامع در نمهاوزر و ولسای (۱۹۸۸) و ولسای (۱۹۹۸) مورد بررسی قرار گرفته است.

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

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

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

  • پیچیدگی بدترین حالت NP-hard است؛ زمان حل می‌تواند به صورت نمایی با تعداد متغیرهای صحیح افزایش یابد.
  • نیاز به فرمول‌بندی دقیق ریاضی دارد؛ مدل‌های بد فرمول‌بندی شده حتی زمانی که مسئله زیربنایی قابل مدیریت است، می‌توانند غیرقابل حل باشند.
  • عناصر غیرمحدب یا غیرخطی نیاز به خطی‌سازی اضافی یا حل‌کننده‌های تخصصی دارند که پیچیدگی مدل را افزایش می‌دهد.
  • هزینه‌های مجوز حل‌کننده برای ابزارهای تجاری می‌تواند قابل توجه باشد، اگرچه جایگزین‌های متن‌باز با کیفیت بالا وجود دارند.
  • نتایج فقط به خوبی مدل هستند: مشخصات نادرست محدودیت منجر به بهینه‌های بی‌معنی می‌شود.

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

نقاط قوت

  • راه‌حل‌های بهینه اثبات‌شده با شکاف بهینگی قابل کمّی‌سازی تولید می‌کند که امکان توجیه دقیق تصمیمات را فراهم می‌آورد.
  • متغیرهای دودویی و صحیح عمومی را به طور بومی مدیریت می‌کند و محدودیت‌های تجزیه‌ناپذیری و منطقی دنیای واقعی را در بر می‌گیرد.
  • حل‌کننده‌های مدرن (Gurobi، CPLEX، SCIP) از شاخه و کران پیشرفته، صفحات برشی و پیش‌حل برای مدیریت کارآمد نمونه‌های بزرگ بهره می‌برند.
  • فرمول‌بندی شفاف مدل، مفروضات را صریح و قابل حسابرسی توسط کارشناسان حوزه می‌سازد.
  • از تحلیل حساسیت و مطالعات پارامتریک برای درک چگونگی تغییر راه‌حل‌ها با داده‌های ورودی پشتیبانی می‌کند.
  • به طور گسترده توسط زبان‌های مدل‌سازی (AMPL، GAMS، Pyomo، JuMP) پشتیبانی می‌شود که نمونه‌سازی سریع را امکان‌پذیر می‌سازد.

کاربردها

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

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

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

1

مدل بهینه‌سازی را تعریف کنید: یک تابع هدف (ترکیب خطی متغیرهای تصمیم برای کمینه‌سازی یا بیشینه‌سازی)، محدودیت‌های نابرابری و تساوی خطی، و الزامات یکپارچگی. متغیرهای پیوسته مقادیر کسری را مدیریت می‌کنند؛ متغیرهای دودویی (۰/۱) یا صحیح عمومی تصمیمات گسسته را مدیریت می‌کنند.

فرمول
\min_{x,y}\; c^\top x + d^\top y \quad \text{s.t.}\; Ax + By \leq b,\; x \geq 0,\; y \in \mathbb{Z}^p
2

ریلکساسیون LP را با رها کردن موقت محدودیت‌های یکپارچگی حل کنید. این یک کران پایین (برای کمینه‌سازی) بر روی تابع هدف MIP بهینه و یک راه‌حل کاندید که ممکن است کسری باشد، ارائه می‌دهد.

فرمول
\text{LP relaxation: replace } y \in \mathbb{Z}^p \text{ with } y \geq 0
3

یک متغیر صحیح کسری را از راه‌حل ریلکساسیون LP انتخاب کنید. با افزودن یک محدودیت کف در یکی و یک محدودیت سقف در دیگری، دو زیرمسئله فرزند ایجاد کنید، که فضای شدنی را بدون از دست دادن هیچ نقطه صحیح شدنی، تقسیم می‌کنند.

فرمول
\text{Select fractional } y_j^*; \text{ create subproblems: } y_j \leq \lfloor y_j^* \rfloor \text{ and } y_j \geq \lceil y_j^* \rceil
4

ریلکساسیون LP هر زیرمسئله را حل کنید. اگر کران بدتر از بهترین راه‌حل صحیح یافت شده تاکنون (مُتَکَفِّل) باشد، آن شاخه را هرس کنید. اگر راه‌حل LP تصادفاً صحیح-شدنی باشد، در صورت بهبود تابع هدف، متکفل را به‌روز کنید.

فرمول
\text{Prune node if LP bound} \geq \text{incumbent; update incumbent when integer-feasible solution found}
5

اختیاری: صفحات برشی اضافه کنید — نابرابری‌های معتبری که راه‌حل کسری LP را بدون حذف هیچ نقطه صحیح شدنی، قطع می‌کنند. برش‌های گوموری رویکرد کلاسیک هستند؛ برش‌های خاص مسئله (مانند برش‌هایClique، برش‌های جریان) می‌توانند اندازه درخت را به طور چشمگیری کاهش دهند.

فرمول
\text{Add Gomory or problem-specific cutting planes to tighten LP relaxation before branching}
6

زمانی که درخت شاخه و کران به طور کامل کاوش شد یا زمانی که شکاف بین بهترین راه‌حل صحیح و کران پایین سراسری در یک تلورانس مشخص شده توسط کاربر (مانند ۰.۰۱٪) قرار گرفت، متوقف شوید. راه‌حل متکفل را با گواهی بهینگی آن برگردانید.

فرمول
\text{Stop when all nodes pruned; return incumbent } x^*, y^* \text{ with optimality gap} \leq \epsilon

دام‌های رایج

  • انتخاب تلورانس شکاف بهینگی بیش از حد تنگ می‌تواند باعث شود حل‌کننده به طور نامحدود اجرا شود؛ همیشه یک شکاف عملی (مانند ۱٪) برای نمونه‌های بزرگ تنظیم کنید.
  • تقارن در مدل (مانند تأسیسات قابل تعویض) شاخه‌های اضافی ایجاد می‌کند و درخت جستجو را منفجر می‌کند — از محدودیت‌های شکست تقارن استفاده کنید.
  • ریلکساسیون‌های ضعیف LP (شکاف یکپارچگی بزرگ) منجر به درختان بسیار بزرگ شاخه و کران می‌شود؛ زمان را برای افزودن نابرابری‌های معتبر یا تنگ کردن فرمول‌بندی سرمایه‌گذاری کنید.
  • در نظر گرفتن همه متغیرها به عنوان صحیح زمانی که فقط برخی از آن‌ها نیاز دارند، به طور غیرضروری پرهزینه است؛ از متغیرهای دودویی فقط در جایی که محدودیت‌های منطقی آن‌ها را ایجاب می‌کنند، استفاده کنید.
  • نادیده گرفتن شروع گرم با یک راه‌حل شدنی خوب، زمان حل‌کننده را برای یافتن اولین متکفل تلف می‌کند.

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

MIP چگونه با برنامه‌ریزی خطی (LP) متفاوت است؟

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

چه زمانی باید به جای MIP از هیوریستیک استفاده کنم؟

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

شکاف بهینگی چیست و چقدر باید کوچک باشد؟

شکاف برابر است با (هدف متکفل - کران LP) / کران LP، که به صورت درصد بیان می‌شود. این گواهی می‌دهد که بهترین راه‌حل صحیح شناخته شده چقدر می‌تواند از بهینه واقعی دور باشد. برای اکثر کاربردهای عملی، شکاف ۰.۱ تا ۱ درصد کافی است؛ شکاف‌های تنگ‌تر به زمان نمایی بیشتری از حل‌کننده نیاز دارند.

آیا MIP می‌تواند توابع هدف یا محدودیت‌های غیرخطی را مدیریت کند؟

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

کدام حل‌کننده‌ها برای MIP توصیه می‌شوند؟

تجاری: Gurobi و CPLEX معیارهای صنعت هستند. متن‌باز: SCIP، CBC (از طریق COIN-OR) و HiGHS برای مسائل با اندازه متوسط رقابتی هستند. همه از رابط‌های مدل‌سازی استاندارد مانند AMPL، Pyomo و JuMP پشتیبانی می‌کنند.

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

منابع

  1. Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.

    شابک: 9780471359432
    کپی شد.
  2. Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.

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