בעיית אריזה בדליים

במדעי המחשב, בעיית אריזה בדליים (bin packing) היא בעיית אופטימיזציה חשובה, בה יש לארוז חפצים במספר מינימלי של דליים. הבעיה היא NP-קשה.

הגדרה

נתונים $n$ חפצים, לכל אחד מהם נפח: $a_{1},...,a_{n}$. בנוסף נתונים מספר לא מוגבל של דליים, שכל אחד מהם בנפח $C$ ומתקיים $C\geq a_{i}$ לכל i (אחרת אי אפשר לארוז אותם בשום דרך). יש לארוז את החפצים במספר מינימלי של דליים, כך שבכל דלי הנפח הכולל של החפצים לא יעלה על נפח הדלי. באופן פורמלי, יש לחלק את המספרים $a_{1},...,a_{n}$ למספר מינימלי של קבוצות זרות, שסכום כל קבוצה לא יעלה על $C$.

סיבוכיות

הבעיה היא NP-קשה, והצגתה כבעיית הכרעה: "האם ניתן לארוז בפחות מ-k דליים?" היא NP-שלמה. הבעיה היא גם NP קשה חזקה, כלומר גם קבלת הקלט בכתיב אונארי היא NP קשה (בניגוד לבעיית תרמיל הגב למשל).

יתרה מכך, בהנחה ש-P שונה מ-NP, אין גם אלגוריתם קירוב ביחס יותר טוב מ 1.5. ניתן לראות זאת על ידי רדוקציה מבעיית החלוקה: בהינתן וקטור $a_{1},...,a_{n}$, נקח $C={\frac {\sum a_{i}}{2}}$ ואז בעיית האריזה בדליים תתן פתרון עם שני דליים אם ורק אם בעיית החלוקה פתירה, אחרת 3 דליים ומעלה.

אלגוריתמים

תכנון ליניארי בשלמים

ניתן לפתור את הבעיה באמצעות תכנון ליניארי בשלמים. המשתנים הם $x_{ij}$ שמציין "הפריט ה-i נכנס לדלי ה-j" וכן $y_{j}$ שמציין "הדלי ה-j נמצא בשימוש" (צריך רק n משתנים כאלה, כי תמיד אפשר לפתור ב-n דליים - להכניס כל פריט לדלי אחר).

כעת המשוואות הן:

$\sum x_{ij}a_{i}\leq y_{j}C$

לכל j, וכן

$\sum _{j}x_{ij}=1$

לכל i (הפריט נכנס לבדיוק דלי 1) ובנוסף אילוצים שכופים על כל המשתנים להיות בינאריים. פונקציית המטרה היא למזער את $\sum _{j}y_{j}$.

אלגוריתם חמדן

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