פתרון בעיות מתקדם ל-LP

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

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

מושגים

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

משפחות של אלגוריתמים של LP

ניתן לגשת למחלקות הבאות של האלגוריתמים ל-LP דרך OR-Tools.

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

    1. כשמשתמשים ב-Primal Simplex, אפשר לעשות את הצעדים לאורך הקודקודים של האזור הראשוני האפשרי. הווריאנט הזה יעיל במיוחד בפתרון רצף של בעיות LP עם פונקציות אובייקטיביות שונות, כלומר, שבו האזור הראשוני האפשרי קבוע.
    2. כשמשתמשים ב-Dual Simplex, צריך לבצע את הצעדים לאורך הקודקודים של האזור הכפול בר-ביצוע. הווריאנט הזה יעיל במיוחד בפתרון רצף של בעיות ברמת הגמ"ח, שבהן אפשר לתקן את האזור האפשרי הכפול, למשל כשמשנים רק את הגבולות של המשתנים. לכן, דו-כיוונית היא בשימוש נרחב בפתרונות MIP.

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

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

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

פתרון בעיות מתמטיות חד-צדדי מעקה הפרדת נתיבים סדר ראשון
CLP X X
CPLEXL X X
גלופG X
GLPK X X
גורוביל X X
PDLPG X
XpressL X X

G מציין שהפותר פותח על ידי Google. L מציין שהפותר דורש רישיון שהונפק על ידי מפתח הצד השלישי הרלוונטי.

בקטע Recommendations (המלצות) תוכלו למצוא הצעות לפתרון בעיות ולאלגוריתמים שבהם כדאי להשתמש.

מה באמת המשמעות של פתרון?

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

סבילות

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

צריך להביא בחשבון את בעיית התכנות הלינארי

$$ \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 $. אילו פתרונות יתקבלו כאופטימליים על ידי הפותר? כדי לענות על השאלה, אנחנו מגדירים את הכמויות הבאות:

  • פער ה-Duality הוא ההבדל בין הערך המטרה הראשונית לערך היעד הכפול. במקרה הזה, $ |(-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

יש לציין גם שהסבלנות משתנה מסיבות טבעיות וגם מסיבות אידיוסינכרוניות בין כל המפענחים והאלגוריתמים. לדוגמה, הפער באימיילים באלגוריתם החד-כיווני נובע רק מחוסר דיוק מספרי, בעוד שהאי-היתימות הראשונית והכפולה קיימת אפילו בחשבון מדויק. בחלק מהשיטות נאכוף באופן ישיר את האילוצים המוגבלים $ x_1 \ge 0, x_2 \ge 0, $ ו- $ y \le 0 $ . לעומת זאת, בשיטות אחרות הן אוכפות באופן ישיר את המגבלות המוגבלות $x_1 \ge 0, x_2 \ge 0, $ ו- $ y \le 0 $ . לעומת זאת, בשיטות אחרות, המגבלות האלו נחשבות כהפרות של מגבלות גבולות באופן שונה מהפרות של מגבלות לינאריות כמו $x_1 + x_2 \le 1 $. אצל חלק מהפתרונות הכפולים, הסובלנות והפערים הם הפערים האופטימליים, ובאילו פערים, הפערים הם היעילות והמוחלטת.

כדוגמה להשפעה של סובלנות, אפשר להגדיר סובלנות מוחלטת של $ \epsilon = \frac{1}{2} $ שחל על הזוג הפרימאלי-כפול שלמעלה. לפתרון $ x_1 = 1.5, x_2 = 0, y = -3 $ יש פער דואליות של אפס ואי-התייעלות פחות מ-$ \epsilon $ או שווה לו, ולכן הפותר עשוי להכריז שהפתרון הזה הוא 'אופטימלי'. עם זאת, הערך האובייקטיבי שלו (3-) שונה ב-1 מהערך האופטימלי האמיתי של 2-. ערכי ברירת המחדל האופייניים של $ \epsilon $ הם בין $10^{-6}$ ל-$10^{-8}$ ולכן דוגמאות קיצוניות כאלה נדירות אבל לא אפשריות.

סוגי פתרונות

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

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

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

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

המלצות

אנחנו מציעים את ההמלצות הבאות לשימוש מתקדם בפתרוןי 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 $, תנאי ההיתכנות הכפולה הופכים לחלשים יחסית, ולכן אפשר להצהיר שיסודות לא אופטימליים מאוד.

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

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

למידע על הסבילות של 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, אנחנו משווים בין זמני הפתרון של כמה מכונות ששימשו את האנס מיטלמן לפתרוןי בנצ'מרק של LP. המכונות נבחרות באופן מפורש כדי להציג קיצוניות של ביצועים יחסיים, והן לא בהכרח מייצגות את ההתנהגות הטיפוסית.

המערכת משווה בין שיטות ראשוניות וכפולות חד-כיווניות של Glop לבין שיטת המחסום של Gurobi (עם ובלי קרוסאובר, שמוצאת פתרון קודקוד) ו-PDLP, שיטת מסדר ראשון, ברמת דיוק גבוהה ונמוכה. הזמנים בטבלה שבהמשך מתעדכנים בשניות, עם מגבלה של 20 דקות (1,200 שניות).

Instance Glop
סימפלס פרימאלי		 Glop
חד-כיווני		 מחסום גורובי
עם קרוסאובר		 מחסום גורובי
ללא קרוסאובר		 רמת דיוק גבוהה
של PDLP		 רמת דיוק נמוכה
של PDLP
ex10 >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
wide15 >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
גרסת Solver OR-כלים 9.3 OR-כלים 9.3 גורובי 9.0 גורובי 9.0 OR-כלים 9.3 OR-כלים 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

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

  1. אפשר לנסות את Glop. הסיבה: Glop היא הטמעה פנימית של שיטות ראשוניות וכפולות חד-צדדיות ב-Google. Glop הוא קוד פתוח ומהימן לעומסי העבודה של Google בתחום הייצור.
    • אם הביצועים של הגדרת ברירת המחדל (ראשי תיבות של Primex, אתם לא משתמשים באפשרות הזו, כדאי לנסות לעבור לשיטה דו-כיוונית דו-צדדית באמצעות use_dual_simplex: true.
  2. אם יש רישיון זמין, כדאי לנסות פתרון מסחרי (CPLEX, Gurobi או Xpress). ניסויים בשיטות חד-משמעיות ושיטות חסימה. הסיבה: הפתרונות האלה הם תקן המקובל בתחום שעברו אופטימיזציה גבוהה. בנוסף, שיטות המחסום משלימות את האלגוריתמים החד-כיווניים שמוצעים על ידי Glop.
    • אם משתמשים במחסום, משביתים את האפשרות "Crossover" אם לא צריך פתרון קודקוד.
  3. כדאי לנסות PDLP. כווננו את סובלנות ההתכנסות לאפליקציה שלכם. הסיבה: PDLP תוכנן לטיפול בבעיות החמורות ביותר, שבהן שיטות חד-פעמיות ומחסום מכות במגבלות הזיכרון או שהן איטיות מדי. השימוש ב-PDLP מניב את הביצועים הטובים ביותר כשעדיף להשתמש בפתרון משוער אך מהיר על פני פתרון מדויק אבל איטי.
  4. אם הגעת עד כה, עכשיו אתה משתמש מתקדם של LP! לקבלת עזרה נוספת, עיינו באפשרויות התמיכה של OR-Tools.

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