رویکرد محققان به محدودیت سرعت جدید برای مشکل سمینال | مجله کوانتا

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

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

از آنجایی که آنها برای اولین بار ILP را فرموله کردند بیش از 60 سال پیش، محققان الگوریتم های مختلفی را کشف کرده اند که مسائل ILP را حل می کند، اما همه آنها از نظر تعداد مراحل مورد نیاز نسبتا کند بوده اند. بهترین نسخه ای که آنها می توانستند ارائه کنند - نوعی محدودیت سرعت - از یک مورد بی اهمیت ناشی می شود که در آن متغیرهای مشکل (مانند اینکه فروشنده از یک شهر بازدید می کند یا نه) فقط می توانند مقادیر دودویی (صفر یا 1) را فرض کنند. در این مورد، ILP دارای یک زمان اجرا است که به صورت نمایی با تعداد متغیرها مقیاس می شود که بعد نیز نامیده می شود. (اگر فقط یک متغیر وجود داشته باشد، آزمایش هر ترکیب ممکن و حل مشکل فقط دو مرحله طول می کشد؛ دو متغیر به معنای چهار مرحله، سه به معنای هشت مرحله و غیره است.)

متأسفانه، زمانی که متغیرها مقداری فراتر از صفر و 1 می گیرند، زمان اجرای الگوریتم بسیار طولانی تر می شود. محققان مدت‌ها در این فکر بودند که آیا می‌توانند به ایده‌آل بی‌اهمیت نزدیک‌تر شوند. پیشرفت کند بوده است، با رکورد در دهه 1980 و فقط افزایشی ارتقاء ساخته شده از زمان.

اما اخیرا کار by ویکتور ریس، در حال حاضر در موسسه مطالعات پیشرفته، و توماس روثوس، در دانشگاه واشنگتن، بزرگترین جهش زمان اجرا در چند دهه اخیر را داشته است. آنها با ترکیب ابزارهای هندسی برای محدود کردن راه‌حل‌های ممکن، الگوریتمی جدید و سریع‌تر برای حل ILP تقریباً همزمان با حالت باینری بی‌اهمیت ایجاد کردند. نتیجه جایزه بهترین مقاله در سال 2023 را دریافت کرد مبانی علوم کامپیوتر کنفرانس.

گفت: "این الگوریتم جدید بسیار هیجان انگیز است." نوح استفنز-دیویدویتز، ریاضیدان و دانشمند کامپیوتر در دانشگاه کرنل. "این نشان دهنده اولین پیشرفت [عمده] برای حل کننده های ILP در نزدیک به 40 سال است."

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

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

لنسترا سپس تمام اعداد صحیح را به عنوان مجموعه ای نامتناهی از نقاط شبکه تصور کرد که در ریاضیات به عنوان شبکه شناخته می شوند. یک نسخه دو بعدی مانند دریایی از نقاط به نظر می رسد و در سه بعدی مانند نقاطی است که تیرهای فولادی در یک ساختمان به یکدیگر متصل می شوند. بعد شبکه نیز به بعد یک مسئله داده شده بستگی دارد.

برای حل یک مشکل ILP معین، لنسترا نشان داد که شما فقط به دنبال جایی هستید که راه حل های ممکن با مجموعه اعداد صحیح ملاقات می کنند: در تقاطع جسم محدب و شبکه. و او الگوریتمی را ارائه کرد که می‌توانست این فضا را به طور کامل جستجو کند - اما برای موثر بودن، گاهی اوقات مجبور بود مشکل را به قطعات کوچک‌تر تقسیم کند و مراحل زیادی را به زمان اجرا اضافه کند.

در سال‌های بعد، چندین محقق چگونگی اجرای سریع‌تر این الگوریتم را بررسی کردند. در سال 1988، Ravi Kannan و László Lovász مفهومی به نام شعاع پوشش را معرفی کردند. قرض گرفت از مطالعه کدهای تصحیح خطا، برای کمک به تلاقی بیشتر بدنه محدب و شبکه. تقریباً، شعاع پوشش اطمینان می‌دهد که بدنه محدب همیشه حداقل یک نقطه صحیح داشته باشد، مهم نیست آن را در کجا روی شبکه قرار می‌دهید. در نتیجه، اندازه شعاع پوشش نیز تعیین می‌کند که تا چه حد می‌توانید مشکل ILP را حل کنید.

بنابراین همه چیز به تعیین اندازه شعاع پوشش ایده آل ختم شد. متأسفانه، این به خودی خود مشکل سختی بود و بهترین کاری که Kannan و Lovász می توانستند انجام دهند این بود که با جستجوی کرانه های بالا و پایین، یک مقدار ممکن را محدود کنند. آنها نشان دادند که حد بالایی - حداکثر اندازه شعاع پوشش - به صورت خطی با ابعاد بزرگ می شود.. این بسیار سریع بود، اما برای سرعت بخشیدن به زمان اجرای ILP کافی نبود. در طول 30 سال آینده، سایر محققان فقط می توانند کمی بهتر عمل کنند.

چیزی که در نهایت به Reis و Rothvoss کمک کرد یک نتیجه ریاضی نامرتبط بود که صرفاً بر روی شبکه متمرکز بود. در سال 2016، اودد رگو و استفنز-دیویدویتز نشان داددر واقع، چند نقطه شبکه می تواند در یک شکل خاص قرار بگیرد. Reis و Rothvoss این را روی اشکال دیگر اعمال کردند، که به آنها اجازه داد تا تعداد نقاط شبکه موجود در شعاع پوششی ILP را بهتر تخمین بزنند و کران بالایی را پایین بیاورند. رگو گفت: «آخرین پیشرفت با این درک حاصل شد که می‌توانید انواع دیگری از اشکال را انجام دهید.

این کران بالا سفت شده جدید یک پیشرفت بزرگ بود و به Reis و Rothvoss اجازه داد تا به سرعت چشمگیری از الگوریتم کلی ILP دست یابند. کار آنها زمان اجرا را به (log n)^O(n)، که در آن n تعداد متغیرها و O (N)یعنی مقیاس خطی با n. (این عبارت "تقریبا" مانند زمان اجرای مسئله باینری در نظر گرفته می شود.)

گفت: "این یک پیروزی در تقاطع ریاضی، علوم کامپیوتر و هندسه است." دانیال دادوش از مؤسسه ملی تحقیقاتی CWI در هلند، که به پیشگام بودن الگوریتم Reis و Rothvoss برای اندازه‌گیری زمان اجرای ILP کمک کرد.

در حال حاضر، الگوریتم جدید واقعاً برای حل هیچ مشکل لجستیکی مورد استفاده قرار نگرفته است، زیرا به روز رسانی برنامه های امروزی برای استفاده از آن کار زیادی می طلبد. اما برای Rothvoss، این در کنار موضوع است. او گفت: "این در مورد درک نظری یک مسئله است که کاربردهای اساسی دارد."

در مورد اینکه آیا کارایی محاسباتی ILP می تواند بیشتر بهبود یابد، محققان همچنان امیدوارند که به زمان اجرای ایده آل نزدیک شوند - اما نه به این زودی. ومپالا گفت: «این به یک ایده اساساً جدید نیاز دارد.