• אופטימיזציה של מספר שלם

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

המשתנים האלה יכולים להופיע בכמה דרכים:

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

  • משתנים בוליאניים שמייצגים החלטות עם ערכי 0-1.
    לדוגמה, חשבו על בעיה שקשורה להקצאת עובדים למשימות (ראו הקצאה). כדי להגדיר בעיה מהסוג הזה, אפשר להגדיר משתנים בוליאניים xi,j ששווה ל-1 אם העובד i מוקצה למשימה j, ו-0 אם לא.

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

כלים

Google מציעה מספר דרכים לפתרון בעיות MIP:

  • MPSolver: קובץ wrapper לכמה פתרוןי MIP של צד שלישי, שמשתמשים בשיטות סטנדרטיות של הסתעפות וכריכה.
  • פותר בעיות CP-SAT: פותר של תכנות אילוצים שמשתמש בשיטות SAT (שביעות רצון).
  • פותר הבעיות CP מקורי: פתרון של תיכנות אילוצים.

באיזה פותר כדאי להשתמש?

אין כלל חד-משמעי להחליט אם להשתמש בפתרון MIP או בפותר CP-SAT. ליתר ביטחון:

  • פתרוןי MIP מתאימים יותר לבעיות שאפשר להגדיר כ-LP סטנדרטי, אבל עם משתנים שרירותיים של מספרים שלמים, כמו בדוגמה הראשונה שלמעלה.
  • הפותר CP-SAT מתאים יותר לבעיות שבהן רוב המשתנים הם בוליאניים, כמו בדוגמה השנייה שלמעלה.

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

במאמר פתרון בעיות בהקצאה ובחלקים אחרים של ההקצאות, תוכלו לראות דוגמאות לשימוש גם בפתרונות MIP וגם בפתרונות CP-SAT.

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