אופטימיזציה של אילוצים, או תכנות אילוצים (CP), הוא השם שניתן לזיהוי פתרונות אפשריים מתוך קבוצה גדולה מאוד של מועמדים, שבה ניתן ליצור מודל לבעיה במונחים של אילוצים שרירותיים. בעיות שקשורות לקורונה (CP) נפוצות בתחומים רבים של מדע והנדסה. (המילה "תכנות" קצת שגויה, בדומה לאופן שבו "מחשב" היה בעבר "אדם שמחשב". במקרה הזה, המונח 'תכנות' מתייחס לסידור של תוכנית ולא לתכנות בשפת מחשב).
הבדיקה מבוססת על היתכנות (מציאת פתרון בר-ביצוע) ולא על אופטימיזציה (מציאת פתרון אופטימלי), ומתמקדת באילוצים ובמשתנים ולא בפונקציה למטרה. למעשה, לבעיה ב-CP אין אפילו פונקציית מטרה – ייתכן שהמטרה היא לצמצם קבוצה גדולה מאוד של פתרונות אפשריים לקבוצת משנה יותר מנוהלת, על ידי הוספת מגבלות לבעיה.
דוגמה לבעיה שמתאימה במיוחד ל-CP היא תזמון עובדים.
הבעיה מתרחשת כשחברות שפועלות באופן רציף, כמו מפעלים, צריכות ליצור לוחות זמנים שבועיים לעובדים שלהן. הנה דוגמה פשוטה מאוד: חברה מפעילה שלוש משמרות של 8 שעות ביום, ומקצה שלושה מתוך ארבעה עובדים למשמרות שונות בכל יום, ובמקביל נותנת את היום הרביעי ליום חופשי. גם במקרה קטן כל כך, מספר לוחות הזמנים האפשריים הוא עצום: בכל יום יש 4! = 4 * 3 * 2 * 1 = 24 הקצאת עובדים אפשרית, כך שמספר לוחות הזמנים השבועיים הוא 24 מיליארד, כלומר 247.
בדרך כלל יש אילוצים אחרים שמצמצמים את מספר הפתרונות האפשריים, למשל, של כל עובד יש לפחות מספר מינימלי של ימים בשבוע. שיטת ה-CP עוקבת אחרי אילו פתרונות אפשר להוסיף כשמוסיפים אילוצים חדשים, וכך היא כלי עוצמתי לפתרון בעיות גדולות שקשורות ללוח הזמנים בפועל.
ל-CP יש קהילה גדולה ופעילה מאוד ברחבי העולם, עם כתבי עת מדעיים ייעודיים, כנסים ומאגר של שיטות פתרון שונות. ה-CP יושם בהצלחה בתכנון, בתזמון ובמספר דומיינים נוספים עם אילוצים הטרוגניים.
כלים
Google מספקת כמה דרכים לפתרון בעיות CP:
- CP-SAT Solr: פותר בעיות של תכנות אילוצים שמשתמש בשיטות SAT (שביעות רצון).
- פותר הבעיות CP מקורי: פותר בעיות של תיכנות אילוצים בספריית הניתובים.
אם אפשר ליצור מודל לבעיה בעזרת מטרה לינארית והגבלות לינאריות, אז יש לכם בעיה שקשורה לתכנות לינארי וכדאי לשקול את הבקשה ל-MPSolver. (עם זאת, כדי לפתור בעיות שקשורות לתכנון מסלול, בדרך כלל מומלץ לפתור אותן באמצעות ספריית מסלולים לרכב שלנו, גם אם אפשר לייצג אותן באמצעות מודל לינארי.)
דוגמאות
בקטע הבא מתואר פותר הבעיות של CP-SAT, הפותר הראשי של OR-Tools לתכנות אילוצים. (פירוש הקיצור SAT הוא שביעות רצון: הפותר משתמש בטכניקות לפתרון בעיות SAT בשילוב עם שיטות CP).
לפניכם כמה דוגמאות לבעיות עם לוח זמנים שמותאמות היטב לפותר הבעיות CP-SAT:
שתי בעיות CP קלאסיות הן בעיית N-queens וחידות קריפטמטיות.