חוקרים מתקרבים למגבלת מהירות חדשה לבעיות זרע | מגזין קוונטה

בעיית איש המכירות הנוסע היא אחת השאלות החישוביות הידועות ביותר. הוא מבקש את המסלול האידיאלי דרך רשימה מסוימת של ערים, תוך צמצום הקילומטראז'. למרות שהבעיה נראית פשוטה, ידועה לשמצה קשה. אמנם אתה יכול להשתמש בכוח גס כדי לבדוק את כל המסלולים האפשריים עד שתמצא את הנתיב הקצר ביותר, אבל אסטרטגיה כזו הופכת לבלתי נסבלת לאחר קומץ ערים בלבד. במקום זאת, אתה יכול ליישם מודל מתמטי קפדני הנקרא תכנות לינארי, שמקרוב את הבעיה כמערכת של משוואות ובודק באופן שיטתי את השילובים האפשריים כדי למצוא את הפתרון הטוב ביותר.

אבל לפעמים, אתה צריך לבצע אופטימיזציה לבעיות הכרוכות בסכומים של מספר שלם. מה תועלת תוכנית ייעול מפעל שמייצרת ספות 500.7? לשם כך, החוקרים פונים לרוב לגרסה של תכנות ליניארי הנקראת תכנות ליניארי מספר שלם (ILP). זה פופולרי ביישומים הכוללים החלטות בדידות, כולל תכנון ייצור, תזמון צוותי חברות תעופה וניתוב כלי רכב. "ביסודו של דבר, ILP הוא הלחם והחמאה של מחקר תפעול הן בתיאוריה והן בפרקטיקה", אמר סנטוש וומפלה, מדען מחשבים במכון הטכנולוגי של ג'ורג'יה.

מאז שהם ניסחו לראשונה את ILP לפני למעלה מ -60 שנים, חוקרים גילו אלגוריתמים שונים הפותרים בעיות ILP, אך כולם היו איטיים יחסית מבחינת מספר השלבים הנדרשים. הגרסה הטובה ביותר שהם יכלו להמציא - סוג של הגבלת מהירות - מגיעה מהמקרה הטריוויאלי שבו משתני הבעיה (כגון אם איש מכירות מבקר בעיר או לא) יכולים לקבל רק ערכים בינאריים (אפס או 1). במקרה זה, ל-ILP יש זמן ריצה שמתרחב באופן אקספוננציאלי עם מספר המשתנים, הנקרא גם הממד. (אם יש רק משתנה אחד, נדרשים שני שלבים בלבד כדי לבדוק כל שילוב אפשרי ולפתור את הבעיה; שני משתנים פירושם ארבעה שלבים, שלושה פירושם שמונה שלבים, וכן הלאה.)

למרבה הצער, ברגע שהמשתנים מקבלים ערך מעבר לאפס ו-1 בלבד, זמן הריצה של האלגוריתם גדל הרבה יותר. חוקרים תהו זה מכבר אם הם יכולים להתקרב לאידיאל הטריוויאלי. ההתקדמות הייתה איטית, עם ה שיא מתרחש בשנות ה-1980 ורק בשלבים מתקדמים שיפורים נעשה מאז.

אבל לאחרונה לעבוד by ויקטור רייס, כיום במכון ללימודים מתקדמים, ו תומס רוטבוס, באוניברסיטת וושינגטון, עשתה את הקפיצה הגדולה ביותר בזמן הריצה מזה עשרות שנים. על ידי שילוב כלים גיאומטריים כדי להגביל את הפתרונות האפשריים, הם יצרו אלגוריתם חדש ומהיר יותר לפתרון ILP כמעט באותו זמן כמו המקרה הבינארי הטריוויאלי. התוצאה זכתה בפרס המאמר הטוב ביותר ב-2023 יסודות מדעי המחשב וְעִידָה.

"האלגוריתם החדש הזה מרגש ביותר", אמר נועה סטפנס-דוידוביץ, מתמטיקאי ומדען מחשבים באוניברסיטת קורנל. "זה מייצג את השיפור הראשון [הגדול] לפותרי ILP מזה כמעט 40 שנה."

ILP פועלת על ידי הפיכת בעיה נתונה לקבוצה של משוואות ליניאריות שצריכות לספק כמה אי-שוויון. המשוואות הספציפיות מבוססות על פרטי הבעיה המקורית. אבל בעוד שפרטים אלה עשויים להיות שונים, ההרכב הבסיסי של בעיות ILP נשאר זהה, מה שנותן לחוקרים דרך אחת לתקוף מספר רב של בעיות.

זה לא אומר שזו עבודה קלה. רק ב-1983 המתמטיקאי הנדריק לנסטרה הוכיח שהבעיה הכללית אפילו ניתנת לפתרון, וסיפקה את האלגוריתם הראשון שיכול לעשות זאת. לנסטרה חשבה על ILP מבחינה גיאומטרית. ראשית, הוא הפך את אי השוויון בלב ה-ILP לצורה קמורה, כמו כל מצולע רגיל. צורה זו מייצגת את האילוצים של הבעיה הפרטנית שאתה פותר, בין אם זה ייצור ספות או תזמון של חברת תעופה, כך שהצורה הפנימית תואמת את כל הערכים האפשריים שיכולים לפתור את אי השוויון, ובכך את הבעיה. לנסטרה כינה את הצורה הזו הגוף הקמור. ממד הבעיה משפיע על הממד של צורה זו: עם שני משתנים היא לובשת צורה של מצולע שטוח; בתלת מימד זה א מוצק אפלטוני, וכן הלאה.

לאחר מכן דמיין לנסטרה את כל המספרים השלמים כקבוצה אינסופית של נקודות רשת, המכונה במתמטיקה סריג. גרסה דו מימדית נראית כמו ים של נקודות, ובתלת מימד היא נראית כמו הנקודות שבהן מתחברות קורות פלדה בבניין. מימד הסריג תלוי גם במימד של בעיה נתונה.

כדי לפתור בעיית ILP נתונה, לנסטרה הראה שאתה פשוט מחפש היכן הפתרונות האפשריים עומדים בקבוצת המספרים השלמים: במפגש של הגוף הקמור והסריג. והוא המציא אלגוריתם שיוכל לחפש את החלל הזה בצורה ממצה - אבל כדי להיות יעיל, לפעמים זה היה צריך לפרק את הבעיה לחתיכות של ממדים קטנים יותר, ולהוסיף שלבים רבים לזמן הריצה.

בשנים הבאות, כמה חוקרים בחנו כיצד לגרום לאלגוריתם הזה לפעול מהר יותר. בשנת 1988 הציגו רבי קאנן ולאסלו לובאש מושג שנקרא רדיוס הכיסוי, שָׁאוּל מהמחקר של קודים לתיקון שגיאות, כדי לעזור לגוף הקמור ולסריג להצטלב בצורה יעילה יותר. בערך, רדיוס הכיסוי מוודא שהגוף הקמור מכיל תמיד לפחות נקודה שלמה אחת, לא משנה היכן אתה מציב אותו על הסריג. כתוצאה מכך, גודל רדיוס הכיסוי קובע גם באיזו יעילות תוכל לפתור את בעיית ה-ILP.

אז הכל הסתכם בקביעת גודל רדיוס הכיסוי האידיאלי. למרבה הצער, זו התבררה כבעיה קשה בפני עצמה, והמיטב שקנאן ולובאש יכלו לעשות היה לצמצם ערך אפשרי על ידי חיפוש גבולות עליונים ותחתונים. הם הראו שהגבול העליון - הגודל המרבי של רדיוס הכיסוי - גדל בצורה ליניארית עם הממד. זה היה די מהיר, אבל לא מספיק כדי להאיץ משמעותית את זמן הריצה של ILP. במהלך 30 השנים הבאות, חוקרים אחרים יכלו להשתפר רק מעט.

מה שבסופו של דבר עזר לרייס ולרוטבוס לפרוץ דרך הייתה תוצאה מתמטית לא קשורה שהתמקדה אך ורק בסריגים. בשנת 2016, עודד רגב וסטפנס-דוידוביץ הראה, למעשה, כמה נקודות סריג יכולות להתאים בתוך צורה מסוימת. Reis ו-Rothvoss יישמו זאת על צורות אחרות, מה שאפשר להם להעריך טוב יותר את מספר נקודות הסריג הכלולות ברדיוס המכסה ILP, מה שמנמיך את הגבול העליון. "פריצת הדרך האחרונה הגיעה עם ההבנה שאתה באמת יכול לעשות סוגים אחרים של צורות", אמרה רגב.

הגבול העליון וההדוק החדש הזה היה שיפור עצום, ואיפשר ל-Reis ו-Rothvoss להשיג מהירות דרמטית של אלגוריתם ה-ILP הכולל. העבודה שלהם מביאה את זמן הריצה ל- (log n)^O(n), שם n הוא מספר המשתנים ו O (n)פירושו שהוא מקנה קנה מידה ליניארי עם n. (ביטוי זה נחשב "כמעט" זהה לזמן הריצה של הבעיה הבינארית.)

"זהו ניצחון בצומת של מתמטיקה, מדעי המחשב וגיאומטריה", אמר דניאל דדוש של מכון המחקר הלאומי CWI בהולנד, שסייע לחלוץ האלגוריתם שבו השתמשו Reis ו-Rothvoss למדידת זמן הריצה של ILP.

לעת עתה, האלגוריתם החדש לא שימש למעשה לפתרון בעיות לוגיסטיות כלשהן, מכיוון שנדרש יותר מדי עבודה בעדכון התוכניות של היום כדי לעשות בו שימוש. אבל עבור רוטבוס, זה לא לעניין. "זה עוסק בהבנה התיאורטית של בעיה שיש לה יישומים בסיסיים", אמר.

אם ניתן לשפר עוד יותר את היעילות החישובית של ILP, החוקרים עדיין מקווים שהם ימשיכו להתקרב לזמן הריצה האידיאלי - אבל לא בקרוב. "זה ידרוש רעיון חדש ביסודו," אמר ומפלה.