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

برنامه‌ریزی عدد صحیح (IP) و برنامه‌ریزی عدد صحیح مختلط (MIP)

معرفی‌شده توسط
Ralph Gomory (cutting planes, 1958); land-and-doig branch-and-bound (1960)
سال
1958
نوع
Mathematical optimisation — exact combinatorial method

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

اندازه قلم

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

برنامه‌ریزی عدد صحیح (IP)، که در مواردی که تنها برخی از متغیرها به اعداد کامل محدود می‌شوند، برنامه‌ریزی عدد صحیح مختلط (MIP) نیز نامیده می‌شود، شاخه‌ای از بهینه‌سازی ریاضی است که در آن برخی یا همه متغیرهای تصمیم باید مقادیر صحیح یا باینری بگیرند. این روش با تکیه بر برنامه‌ریزی خطی، از طریق روش صفحه برش رالف گوموری (1958) و الگوریتم شاخه و کران لند و دویگ (1960) رسمیت یافت و از آن زمان به چارچوب دقیق استاندارد برای مسائل زمان‌بندی، تخصیص، مسیریابی و تخصیص منابع تبدیل شده است.

شهود پشت روش

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

تاریخ

برنامه‌ریزی عدد صحیح در اواخر دهه 1950 زمانی پدیدار شد که محققان به دنبال گسترش برنامه‌ریزی خطی به تصمیمات گسسته بودند. رالف گوموری روش سیستماتیک صفحه برش را در سال 1958 معرفی کرد و ثابت کرد که هر برنامه عدد صحیح را می‌توان اصولاً با افزودن تعداد محدودی برش حل کرد. لند و دویگ (1960) شاخه و کران را رسمیت بخشیدند که به الگوریتم دقیق غالب تبدیل شد. ولسلی (1998) و نمهاوزر و ولسلی (1988) کتاب‌های درسی متعارفی را ارائه دادند که این حوزه هنوز به آنها تکیه دارد. انقلاب عملی با توسعه حل‌کننده‌های شاخه و برش در دهه 1990 رخ داد که هر دو تکنیک را با روش‌های اکتشافی پیشرفته ترکیب کرد و بعدها با انفجار عملکرد حل‌کننده‌های تجاری و متن‌باز که امروزه کاربردهای واقعی در مقیاس بزرگ را امکان‌پذیر می‌سازد.

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

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

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

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

2

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

3

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

4

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

5

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

دام‌های رایج

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

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

تفاوت بین IP و MIP چیست؟

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

چرا برنامه‌ریزی عدد صحیح NP-hard است در حالی که برنامه‌ریزی خطی چندجمله‌ای است؟

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

چگونه بفهمم که راه‌حل من بهینه است؟

حل‌کننده یک شکاف بهینگی — تفاوت درصدی بین بهترین راه‌حل عدد صحیح یافت شده و بهترین کران پایین باقی‌مانده — را گزارش می‌کند. شکاف 0% بهینگی سراسری را تأیید می‌کند. برای مسائل بزرگ می‌توانید یک تلرانس شکاف (مثلاً 1%) تعیین کنید و یک راه‌حل تقریباً بهینه را بپذیرید؛ کران همچنان تضمین می‌کند که بهینه واقعی نمی‌تواند بیش از آن درصد بهتر باشد.

چه چیزی یک فرمول‌بندی «محکم» را ایجاد می‌کند و چرا اهمیت دارد؟

یک فرمول‌بندی محکم فرمول‌بندی است که رهاسازی LP آن یک کران نزدیک به بهینه عدد صحیح را ارائه می‌دهد و یک شکاف صحیح بودن کوچک را باقی می‌گذارد. هنگامی که شکاف کوچک است، شاخه و کران نیاز به بررسی گره‌های کمتری دارد و سریع‌تر خاتمه می‌یابد. افزودن نابرابری‌های معتبر مانند برش‌های گوموری، نابرابری‌های پوشش یا برش‌های کلاستر فرمول‌بندی را محکم‌تر می‌کند و اغلب مؤثرترین راه برای سرعت بخشیدن به یک حل‌کننده است.

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

منابع

  1. Wolsey, L.A. (1998). Integer Programming. Wiley.

    شابک: 9780471283669
    کپی شد.
  2. Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.

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