פותרנים ומנועי אופטימיזציה

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

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

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

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

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

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

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

אני אנסה להתייחס לשפות התכנות הנפוצות לפותרנים / למנועים הללו בהמשך.

במה אתם משתמשים? למה דווקא? מה השיקולים שלכם? מה חסר לכם בפותרנים שאתם משתמשים בהם ומה הייתם רוצים שיהיה אפשרי וזמין ונוח?

פותרנים ומנועי אופטימיזציה

דברו איתי:

שלמה יונה

מייסד ומדען ראשי, מתמטיקאי מחקר ופיתוח בע"מ

053-7326360

shlomo.yona@mathematic.ai 

https://mathematic.ai

פודקאסט על החברה ועליי, שלמה יונה, ואופן העבודה שלנו ואיתנו: A technical deep dive about