Integer programming — תכנות שלמים

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

המקרה הפרטי הנחקר ביותר הוא תכנות לינארי שלם (תל"ש; באנגלית integer linear programming, ILP), שבו פונקציית המטרה וההגבלות הן לינאריות. בניגוד לתכנות לינארי, שבו המשתנים יכולים לקבל כל ערך ממשי, דרישת השלמות הופכת את בעיות ת"ש למורכבות הרבה יותר לפתרון.

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

הגדרה וטרמינולוגיה

בעיית התכנות הלינארי השלם הכללית ניתן לרשום כך:

מצא וקטור $x$, אשר:

ממקסם (או ממזער) את $c^{T}x$

בכפוף לתנאים:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{\mathbb{Z}}}^n$ (כל רכיבי הוקטור $x$ — מספרים שלמים)

כאשר $x$ — וקטור המשתנים, $c$ ו-$b$ — וקטורים, ו-$A$ — מטריצת מקדמים.

בהתאם לדרישות מהמשתנים, מבחינים בסוגי הבעיות הבאים:

• תכנות שלם מלא: כל המשתנים חייבים להיות שלמים.
• תכנות שלם מעורב (באנגלית mixed-integer programming, MIP): רק חלק מהמשתנים חייבים להיות שלמים.
• תכנות בוליאני (0-1): המשתנים מקבלים ערכים 0 או 1 בלבד, מה שמאפשר לדגמן החלטות לוגיות מסוג "כן/לא".

תכונות מרכזיות ומורכבות

מורכבות חישובית

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

הקשר לתכנות לינארי (רלקסציית ת"ל)

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

1. ניתן למצוא אותו במהירות רבה יותר (בזמן פולינומי).
2. הערך האופטימלי של פונקציית המטרה ברלקסציית ת"ל נותן חסם (חסם עליון לבעיית מיקסום וחסם תחתון לבעיית מיזעור) לערך האופטימלי של בעיית השלמים המקורית.

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

תכונת אוניממודולריות מלאה

קיים מחלקה חשובה של בעיות תל"ש הנפתרות בקלות כמו רלקסציות ת"ל שלהן. אלו הן בעיות שבהן מטריצת ההגבלות $A$ היא אוניממודולרית לחלוטין (כלומר, הדטרמיננטה של כל תת-מטריצה ריבועית שלה שווה ל-0, +1 או −1). אם המטריצה $A$ היא אוניממודולרית לחלוטין והוקטור $b$ שלם, אזי כל קודקודי הפוליהדרון של הפתרונות הישימים של רלקסציית ת"ל יהיו אוטומטית שלמים. לפיכך, הפתרון שנמצא בשיטת הסימפלקס יהיה שלם. דוגמאות לבעיות כאלה הן בעיית ההובלה ובעיית השיבוץ.

שיטות פתרון

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

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

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

פותרים מודרניים משתמשים בדרך כלל באלגוריתמים היברידיים, כגון שיטת הענפים והחתכים (באנגלית Branch and Cut), המשלבת את יתרונות שתי הגישות.

דוגמאות ותחומי יישום

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

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

בזכות גמישותו, ת"ש הוא אחד הכלים המבוקשים ביותר בחקר ביצועים ומוצא שימוש בתחומים כגון:

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

ראו גם

• תכנות לינארי
• שיטת הענפים והגבולות

הערות

</references>