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

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

معرفی‌شده توسط
Ralph E. Gomory
سال
1958
نوع
Exact combinatorial optimization
خانواده
Simulation / optimization

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

اندازه قلم

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

برنامه‌ریزی عدد صحیح قطعی (DIP) یک رویکرد بهینه‌سازی ریاضی است که بهترین راه‌حل را برای مسائلی که در آن‌ها برخی یا همه متغیرهای تصمیم باید مقادیر صحیح را بگیرند، با فرض داده‌های کامل شناخته‌شده (قطعی) تابع هدف و قیود پیدا می‌کند. این شکل کلاسیک و غیرتصادفی برنامه‌ریزی عدد صحیح است که از اواخر دهه ۱۹۵۰، پایه‌گذار تحقیق در عملیات و بهینه‌سازی ترکیبی بوده است.

شهود پشت روش

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

تاریخ

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

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

هنگامی از برنامه‌ریزی عدد صحیح قطعی استفاده کنید که: (۱) متغیرهای تصمیم ذاتاً گسسته هستند (تخصیص، زمان‌بندی، مکان‌یابی تسهیلات، بسته‌بندی جعبه، طراحی شبکه)؛ (۲) تمام پارامترهای مسئله با قطعیت شناخته شده‌اند یا می‌توانند به طور قابل اعتماد به عنوان مقادیر نقطه‌ای تخمین زده شوند؛ (۳) یک راه‌حل بهینه دقیق به جای یک تقریب ابتکاری (heuristic) مورد نیاز است. هنگامی استفاده نکنید که: پارامترها نامشخص یا وابسته به سناریو هستند (به جای آن از برنامه‌ریزی عدد صحیح تصادفی یا قوی استفاده کنید)؛ مقیاس مسئله آنقدر بزرگ است که انشعاب و کران از نظر محاسباتی غیرقابل حل است و روش‌های ابتکاری قابل قبول هستند؛ متغیرها واقعاً پیوسته هستند (از LP استفاده کنید)؛ یا چندین هدف متناقض باید به طور همزمان متعادل شوند (از برنامه‌ریزی عدد صحیح چندهدفه استفاده کنید).

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

  • فرض می‌کند تمام پارامترهای مسئله دقیقاً شناخته شده‌اند — عدم قطعیت دنیای واقعی به طور عمدی نادیده گرفته می‌شود.
  • در حالت کلی NP-hard است؛ زمان حل در بدترین حالت به صورت نمایی با اندازه مسئله افزایش می‌یابد.
  • مسائل ترکیبی بزرگ ممکن است حتی با حل‌کننده‌های مدرن، ساعت‌ها یا روزها محاسبه نیاز داشته باشند.
  • کیفیت فرمول‌بندی مدل (تنگنای قیود، شکست تقارن) به شدت بر زمان حل تأثیر می‌گذارد.

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

نقاط قوت

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

کاربردها

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

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

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

1

مدل بهینه‌سازی را تعریف کنید: یک تابع هدف برای کمینه‌سازی (یا بیشینه‌سازی) به عنوان ترکیبی خطی از متغیرهای تصمیم عدد صحیح، تحت مجموعه‌ای از قیود نامساوی یا مساوی خطی. تمام ضرایب (c, A, b) ثابت و شناخته‌شده هستند — این همان چیزی است که فرمول‌بندی را قطعی می‌کند. متغیرهای دودویی (۰/۱) یک حالت خاص برای تصمیمات بله/خیر هستند.

فرمول
\min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0,\; x \in \mathbb{Z}^n
2

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

فرمول
\text{Solve LP relaxation: } \min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0
3

یک متغیر کسری از راه‌حل آرام‌سازی خطی را انتخاب کنید و ناحیه شدنی را با افزودن یک قید سقف (x_j <= floor value) در یک شاخه و یک قید کف (x_j >= ceil value) در شاخه دیگر، تقسیم کنید و دو زیرمسئله را برای حل بازگشتی تولید کنید.

فرمول
\text{Select fractional variable } x_j^*. \text{ Create two subproblems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceil
4

آرام‌سازی خطی هر زیرمسئله را حل کنید تا یک کران به دست آورید. اگر کران یک گره (node) بدتر از بهترین راه‌حل صحیح شناخته‌شده (incumbent) باشد، آن را هرس کنید (prune). اگر زیرمسئله یک راه‌حل صحیح-شدنی بهتر از incumbent ارائه دهد، incumbent را به‌روزرسانی کنید. این فرآیند یک درخت جستجوی انشعاب و کران (branch-and-bound) را تشکیل می‌دهد.

فرمول
\text{Compute bounds; prune nodes where LP bound} \geq \text{incumbent. Update best integer solution.}
5

روش‌های صفحه برش (cutting-plane methods) — به‌ویژه برش‌های گوموری (Gomory cuts) — نامساوی‌های خطی اضافی را از جدول خطی (LP tableau) استخراج می‌کنند که توسط تمام راه‌حل‌های صحیح ارضا می‌شوند اما توسط راه‌حل خطی کسری فعلی نقض می‌شوند. افزودن این برش‌ها، آرام‌سازی خطی را فشرده‌تر کرده و انشعاب را کاهش می‌دهد. حل‌کننده‌های مدرن، انشعاب و کران را با برش‌ها در یک چارچوب انشعاب و برش (branch-and-cut) ترکیب می‌کنند.

فرمول
\text{Optionally add Gomory cuts or problem-specific valid inequalities to tighten LP relaxation.}
6

الگوریتم زمانی خاتمه می‌یابد که تمام گره‌های باز هرس شده باشند یا راه‌حل‌های صحیح ارائه دهند. incumbent در زمان خاتمه، راه‌حل صحیح بهینه و قابل اثبات است. حل‌کننده‌ها همچنین یک شکاف (gap) بین بهترین کران و incumbent گزارش می‌کنند که می‌تواند به عنوان معیار توقف برای مسائل بزرگ استفاده شود.

فرمول
\text{Return optimal integer solution } x^* \text{ with objective value } z^* = c^\top x^*

دام‌های رایج

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

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

برنامه‌ریزی عدد صحیح قطعی را از برنامه‌ریزی عدد صحیح تصادفی چه چیزی متمایز می‌کند؟

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

آیا برنامه‌ریزی دودویی حالت خاصی از برنامه‌ریزی عدد صحیح است؟

بله. برنامه‌ریزی دودویی (۰-۱) هر متغیر تصمیم را به {۰, ۱} محدود می‌کند. این رایج‌ترین حالت خاص است که برای تصمیمات بله/خیر مانند باز کردن یک تأسیسات، انتخاب یک پروژه یا تخصیص یک کارگر استفاده می‌شود. برنامه‌ریزی عدد صحیح عمومی اجازه هر مقدار صحیح نامنفی را می‌دهد.

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

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

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

برنامه‌ریزی عدد صحیح قطعی کلاسیک خطی بودن را فرض می‌کند (برنامه‌ریزی عدد صحیح خطی). برنامه‌ریزی عدد صحیح غیرخطی وجود دارد اما به طور قابل توجهی دشوارتر است؛ بسیاری از اشکال غیرخطی را می‌توان از طریق متغیرهای دودویی کمکی و فرمول‌بندی‌های big-M خطی کرد. برنامه‌ریزی عدد صحیح درجه دوم (QIP) مستقیماً توسط برخی حل‌کننده‌های مدرن پشتیبانی می‌شود.

در عمل باید از چه حل‌کننده‌ای برای برنامه‌ریزی عدد صحیح قطعی استفاده کنم؟

تجاری: Gurobi یا IBM CPLEX برای بهترین عملکرد. دانشگاهی/متن‌باز: SCIP, CBC (از طریق COIN-OR) یا HiGHS. همه آن‌ها انشعاب و برش را با پیش‌پردازش خودکار پیاده‌سازی می‌کنند. برای کاربران پایتون، PuLP, Pyomo یا scipy.optimize.milp رابط‌های مدل‌سازی مناسبی را ارائه می‌دهند.

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

منابع

  1. Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5), 275-278.

    باز کردن مرجع DOI
    کپی شد.
  2. Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.

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