אופטימיזציה דיסקרטית הולכת לשנות את חיינו במאה ה-21

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

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

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

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

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

תעשיית התחבורה החכמה
תרוויח הרבה מהאופטימיזציה הדיסקרטית. אילוסטרציה: ג'ייקוב ג'ירסק, BigStock

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

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

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

הכותב הוא מתמטיקאי ומדען בכיר בחברת ויה