حل پیشرفته LP

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

این راهنما مفاهیم را معرفی می‌کند و مثال‌هایی ارائه می‌کند تا به شما کمک کند بیشترین عملکرد و قابلیت اطمینان را از حل‌کننده‌های LP داشته باشید.

مفاهیم

این بخش مفاهیم کلیدی برای استفاده پیشرفته از حل کننده های LP را ارائه می دهد. ما فرض می کنیم که خوانندگان با مفهوم دوگانگی در LP آشنا هستند.

خانواده الگوریتم های LP

کلاس های زیر از الگوریتم های LP از طریق OR-Tools قابل دسترسی هستند.

  1. الگوریتم Simplex اولین الگوریتم عملی LP بود و همچنان محبوب ترین الگوریتم است. الگوریتم در امتداد رئوس (نقاط گوشه) منطقه امکان پذیر حرکت می کند و به طور مکرر مقدار تابع هدف را تا رسیدن به یک جواب بهینه بهبود می بخشد. دو نوع الگوریتم سیمپلکس وجود دارد:

    1. سیمپلکس اولیه در امتداد رئوس ناحیه امکان پذیر اولیه قدم برمی دارد. این نوع به ویژه در حل دنباله ای از مسائل LP با توابع هدف متفاوت، یعنی جایی که منطقه امکان پذیر اولیه ثابت است، موثر است.
    2. دو سیمپلکس در امتداد رئوس ناحیه دوگانه امکان پذیر گام برمی دارد. این نوع به ویژه در حل دنباله ای از مسائل LP که در آن منطقه امکان پذیر دوگانه ثابت است، برای مثال، زمانی که فقط کران های متغیرها تغییر می کنند، موثر است. به همین دلیل، دو سیمپلکس به طور گسترده در حل کننده های MIP استفاده می شود.

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

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

جدول زیر حل کننده های LP موجود در OR-Tools را فهرست می کند و نشان می دهد که کدام یک از سه خانواده الگوریتم در هر حل کننده پیاده سازی شده است.

حل کننده سیمپلکس مانع سفارش اول
Clp ایکس ایکس
CPLEX L ایکس ایکس
گلوپ جی ایکس
GLPK ایکس ایکس
گوروبی ال ایکس ایکس
PDLP G ایکس
Xpress L ایکس ایکس

G نشان می دهد که حل کننده توسط گوگل توسعه یافته است. L نشان می دهد که حل کننده نیاز به مجوز صادر شده توسط توسعه دهنده شخص ثالث مربوطه دارد.

به توصیه‌هایی برای پیشنهادات مربوط به حل‌کننده‌ها و الگوریتم‌هایی که باید استفاده کنید، مراجعه کنید.

واقعا حل کردن یعنی چی؟

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

تحمل ها

حل‌کننده‌های LP تقریباً همیشه از محاسبات ممیز شناور استفاده می‌کنند و جواب‌های خود را در معرض عدم دقت عددی قرار می‌دهند. برای توضیح این موضوع، و برای بهبود عملکرد با اجتناب از تلاش بر روی راه‌حل‌هایی که قبلاً به اندازه کافی خوب هستند، حل‌کننده‌ها راه‌حل‌ها را می‌پذیرند - و ادعا می‌کنند که یک مشکل را حل کرده‌اند - زمانی که این راه‌حل‌ها شرایطی را تا حد تحمل معین برآورده می‌کنند.

مسئله برنامه ریزی خطی را در نظر بگیرید

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

و مشکل دوگانه مربوط به آن

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

این جفت مسئله دارای یک راه حل اولیه بهینه منحصر به فرد $ x_1 = 1، x_2 = 0 $ و راه حل دوگانه $ y = -2 $ است. کدام راه حل ها می توانند توسط یک حل کننده به عنوان بهینه پذیرفته شوند؟ برای پاسخ به این، مقادیر زیر را تعریف می کنیم:

  • شکاف دوگانگی تفاوت بین مقدار هدف اولیه و مقدار هدف دوگانه است، در این مورد، $ |(-2x_1 - x_2) - y| $.
  • عدم امکان‌پذیری اولیه، نقض محدودیت‌های اولیه است، در این مورد، $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2 , 0\}) $.
  • عدم امکان‌پذیری‌های دوگانه ، نقض محدودیت‌های دوگانه هستند، در این مورد، $ (\max\{ 2 + y، 0 \}، \max\{ 1 + y، 0 \}، \max\{ y، 0 \} ) دلار.

یک حل کننده یک راه حل را بهینه اعلام می کند اگر شکاف دوگانگی، عدم امکان پذیری اولیه، و عدم امکان پذیری دوگانه کوچکتر از تحمل معین باشد. 1

قابل ذکر است، کاربرد تلورانس ها به دلایل طبیعی و خاص در حل کننده ها و الگوریتم ها متفاوت است. برای مثال، شکاف دوگانگی در الگوریتم سیمپلکس تنها با عدم دقت عددی هدایت می‌شود، در حالی که عدم امکان‌پذیری اولیه و دوگانه حتی در محاسبات دقیق نیز وجود دارد. برخی روش‌ها مستقیماً محدودیت‌های کران را اعمال می‌کنند. برای برخی از حل کننده ها، تحمل ها مطلق هستند. یعنی یک پارامتر $ \epsilon $ وجود دارد، و اگر شکاف دوگانگی و همه ناتوانی‌های اولیه و دوگانه کمتر یا مساوی $ \epsilon $ باشند، راه‌حل‌ها بهینه در نظر گرفته می‌شوند. برای حل‌کننده‌های دیگر، تحمل‌ها نسبی هستند، به این معنی که با اندازه ضرایب در مسئله مقیاس می‌شوند.

برای مثالی از تأثیر تلورانس ها، تحمل مطلق $ \epsilon = \frac{1}{2} $ را در نظر بگیرید که برای جفت اولیه-دوگانه فوق اعمال می شود. راه حل $ x_1 = 1.5، x_2 = 0، y = -3 $ دارای شکاف دوگانگی صفر و غیرممکن است که همگی کمتر یا مساوی $ \epsilon $ هستند، بنابراین یک حل کننده ممکن است این راه حل را "بهینه" اعلام کند. با این حال، مقدار هدف آن (-3) با مقدار هدف بهینه واقعی 2- 1 متفاوت است. مقادیر پیش‌فرض معمولی $ \epsilon $ بین $10^{-6}$ و $10^{-8}$ است، که این مثال‌های شدید را نادر اما غیرممکن می‌سازد.

انواع راه حل ها

مسائل LP می توانند بیش از یک راه حل بهینه داشته باشند، حتی بیشتر در هنگام محاسبه تلورانس ها. ما به طور خلاصه در مورد خواص راه حل های بازگشتی توسط سه خانواده مختلف از الگوریتم های LP ارائه شده در بالا بحث می کنیم.

الگوریتم های ساده همیشه رئوس یا نقاط گوشه ای از ناحیه امکان پذیر را برمی گرداند. این راه‌حل‌ها در برخی موقعیت‌ها ترجیح داده می‌شوند، زیرا معمولاً پراکنده‌تر هستند.

روش های مانع و مرتبه اول به طور کلی رئوس را بر نمی گرداند. (تئوری خصوصیات دیگری را ارائه می دهد که خارج از محدوده این راهنما هستند.)

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

توصیه ها

ما توصیه های زیر را برای استفاده پیشرفته از حل کننده های LP ارائه می کنیم.

مقیاس بندی داده های مشکل

حل کننده ها به دلیل مسائل عددی می توانند همگرایی آهسته یا شکست را در مدل ها تجربه کنند. چنین مسائلی می تواند به دلایل زیادی ایجاد شود. در اینجا یک مثال می زنیم.

معمول است که ثابت های عددی بسیار کوچک یا بزرگ در مدل های LP ظاهر شوند. با بسط دادن مثال بالا، اگر \(x_1\) و \(x_2\) نشان دهنده کسری از مشتریان تخصیص داده شده به "ارائه دهنده 1" یا "ارائه دهنده 2" باشند، و اگر بخواهیم از ارائه خدمات به این مشتریان سود را به حداکثر برسانیم، ممکن است تابع هدف زیر را بنویسیم. ،

$$ \min -c_1x_1 - c_2x_2 $$

جایی که:

  • $ c_1 $ مزیت تخصیص مشتریان به ارائه دهنده 1 است
  • $ c_2 $ مزیت تخصیص مشتریان به ارائه دهنده 2 است

دوگانه ای که محدودیت های زیر را برآورده می کنند با تحمل مطلق $ \epsilon $ امکان پذیر در نظر گرفته می شوند:

  • $ y \le -c_1 + \epsilon $،
  • $ y \le -c_2 + \epsilon $.

اگر واحدهای سود $c_1 $ و $ c_2 $ مقادیر کسری کوچکی باشند که اتفاقاً در همان مقیاس $ \epsilon $ باشند، آن‌گاه شرایط امکان‌سنجی دوگانه نسبتاً ضعیف می‌شود، بنابراین یک اولیه بسیار نابهینه ممکن است بهینه اعلام شود.

از سوی دیگر، اگر واحدهای سود «میکرودلار» باشند (1000000 میکرودلار = 1 دلار)، مقادیر مطلق بسیار بزرگ حاصله، دقت بسیار بالایی در راه حل را می طلبد، که احتمالاً با توجه به محدودیت های اعداد ممیز شناور، به طور غیرمنطقی زیاد است. اگر مسئله به این شکل فرموله شود، ممکن است حل کننده ها نتوانند همگرا شوند. به عنوان بخشی از فرمول‌بندی یک مسئله به خوبی طرح‌شده، مدل‌سازان پیشرفته باید در نظر بگیرند که آیا داده‌های مسئله به‌گونه‌ای مقیاس‌بندی شده‌اند که با تلورانس‌های حل‌کننده‌شان سازگار باشد.

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

برای تحمل‌های Glop، primal_feasibility_tolerance ، dual_feasibility_tolerance ، و solution_feasibility_tolerance در GlopParameters ببینید. توجه داشته باشید که primal_feasibility_tolerance و dual_feasibility_tolerance در الگوریتم استفاده می‌شوند، در حالی که solution_feasibility_tolerance پس از حل برای پرچم‌گذاری مسائل عددی بررسی می‌شود. برای PDLP، eps_optimal_absolute و eps_optimal_relative را ببینید.

برای مطالعه بیشتر در مورد این نوع مسائل، به راهنمای Gurobi برای مسائل عددی مراجعه کنید. در حالی که دستورالعمل ها برای کاربران Gurobi نوشته شده است، بسیاری از اصول به طور کلی اعمال می شوند.

انتخاب حل کننده ها و الگوریتم ها

ما با مثالی شروع می کنیم که تاثیر انتخاب حل کننده ها و الگوریتم ها چقدر می تواند باشد و سپس راهنمای انتخاب حل کننده های LP را ارائه می دهیم.

تنوع در عمل

ما تنوع عملکرد را در الگوریتم‌ها و حل‌کننده‌های LP با مقایسه زمان‌های حل در مجموعه‌ای از نمونه‌هایی که توسط Hans Mittelmann برای محک زدن حل‌کننده‌های LP استفاده شده‌اند، نشان می‌دهیم. نمونه ها به صراحت برای نشان دادن افراط در عملکرد نسبی انتخاب شده اند و لزوماً نماینده رفتار معمولی نیستند .

روش‌های سیمپلکس اولیه و دوگانه Glop با روش سد گوروبی (با و بدون متقاطع، که راه‌حل راس را پیدا می‌کند) و PDLP، یک روش مرتبه اول، با دقت بالا و پایین مقایسه می‌شوند. جدول زیر زمان ها را در ثانیه با محدودیت 20 دقیقه (1200 ثانیه) حل می کند.

نمونه، مثال گلوپ
سیمپلکس اولیه		 گلوپ
دو سیمپلکس		 سد گوروبی
با کراس اوور		 سد گوروبی
بدون کراس اوور		 PDLP
دقت بالا		 PDLP
دقت پایین
سابق 10 > 1200 > 1200 79.7 63.5 8.2 2.7
nug08-3 > 1200 252.8 144.6 3.2 1.1 0.9
savsched1 > 1200 > 1200 156.0 22.6 46.4 32.4
گسترده 15 > 1200 20.8 > 1200 > 1200 916.4 56.3
انرژی ساختمان 178.4 267.5 12.8 12.3 > 1200 157.2
s250r10 12.1 520.6 15.2 16.4 > 1200 > 1200
نسخه حل کننده OR-Tools 9.3 OR-Tools 9.3 Gurobi 9.0 Gurobi 9.0 OR-Tools 9.3 OR-Tools 9.3
solver_specific_parameters (پیش فرض) use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

از این نتایج به موارد زیر نتیجه می گیریم.

  • عملکرد نسبی الگوریتم‌ها و حل‌کننده‌ها می‌تواند بر اساس مرتبه‌های بزرگی در یک نمونه متفاوت باشد.
  • هیچ الگوریتم و حل کننده ای به طور یکنواخت بهتر از بقیه نیست.
  • متقاطع (به طور پیش فرض فعال است) زمان حل را افزایش می دهد، گاهی اوقات به طور قابل توجهی.
  • PDLP می تواند با دقت پایین گاهی اوقات 10 برابر سریعتر از دقت بالا حل شود.

راهنمای مختصری برای انتخاب حل کننده های LP

با توجه به اینکه هیچ الگوریتم یا حل کننده LP واحدی بهترین نیست، ما مراحل زیر را برای کشف بهترین موارد برای استفاده شما توصیه می کنیم. از مرحله اول شروع کنید و اگر عملکرد کافی نبود به مرحله بعدی بروید.

  1. Glop را امتحان کنید. چرا : Glop پیاده سازی داخلی گوگل از روش های سیمپلکس اولیه و دوگانه است. Glop منبع باز است و برای بارهای کاری تولید Google قابل اعتماد است.
    • اگر پیکربندی پیش‌فرض (primal simplex) خوب عمل نمی‌کند، سعی کنید با استفاده از use_dual_simplex: true به dual simplex بروید.
  2. اگر مجوز در دسترس است، یک حل کننده تجاری (CPLEX، Gurobi، یا Xpress) را امتحان کنید. با روش های سیمپلکس و مانع آزمایش کنید. چرا: این حل کننده ها استاندارد صنعتی و بسیار بهینه هستند. همچنین، روش های مانع مکمل الگوریتم های سیمپلکس ارائه شده توسط Glop هستند.
    • اگر از مانع استفاده می کنید، اگر به حل رأس نیاز ندارید، «تقاطع» را غیرفعال کنید.
  3. PDLP را امتحان کنید. تلورانس های همگرایی را با برنامه خود تنظیم کنید. چرا: PDLP برای بزرگترین مشکلات طراحی شده است، جایی که روش‌های سیمپلکس و مانع به محدودیت‌های حافظه می‌رسند یا خیلی کند هستند. PDLP زمانی بهترین عملکرد را دارد که یک راه حل تقریبی اما سریع به یک راه حل دقیق اما کند ترجیح داده شود.
  4. اگر تا اینجا پیش رفته اید، اکنون یک کاربر پیشرفته LP هستید! لطفاً برای راهنمایی بیشتر گزینه های پشتیبانی OR-Tools را ببینید.

  1. اغلب پیچیده تر از این است. حل‌کننده‌ها معمولاً این شرایط را در یک نسخه تبدیل شده/ساده‌شده از مسئله، به نام مشکل پیش‌فرض بررسی می‌کنند. در برخی موارد، یک راه حل برای مشکل حل شده ممکن است با راه حلی برای مشکل ورودی فاصله زیادی داشته باشد. این وضعیت می‌تواند منجر به وضعیت‌های غیرعادی مانند OptimalInfeas CPLEX یا IMPRECISE Glop شود. ↩