בסיס גרייבר

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

הגדרה רשמית

בסיס הגרייבר של מטריצה $m\times n$ בשלמים $A$ היא הקבוצה הסופית $G(A)$ של אלמנטים מינימליים בקבוצה

$\{x\in \mathbb {Z} ^{n}:Ax=0,\ x\neq 0\}\,$

תחת סדר חלקי על $\mathbb {Z} ^{n}$ המוגדר על ידי $x\sqsubseteq y$ כאשר $x_{i}y_{i}\geq 0$ ו- $|x_{i}|\leq |y_{i}|$ לכל i. לדוגמה, בסיס גרייבר של $A=(1,2,1)$ מורכב מהווקטורים (1−,1,0), (1,0−,2), (2 ,1−,0), (1,1−,1) ושליליותיהם.

פתרון תכנות בשלמים באמצעות בסיסי גרייבר

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

$\min\{f(x)\ :\ x\in \mathbb {Z} ^{n},\ Ax=b,\ l\leq x\leq u\}\ .$

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

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

המקרה הנחקר ביותר, הוא של תכנות ליניארי בשלמים,

$\min\{wx\ :\ x\in \mathbb {Z} ^{n},\ Ax=b,\ l\leq x\leq u\}\ .$

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

עם זאת, בהינתן בסיס הגרייבר $G(A)$ של $A$ ניתן לפתור אותה בזמן פולינומי באמצעות האלגוריתם האיטרטיבי הפשוט הבא. נניח תחילה כי ניתנת איזו נקודה $x$ אפשרית ראשונית. כל עוד הדבר אפשרי, חזור על האיטרציה הבאה: מצא מספר שלם חיובי $q$ ואלמנט $g$ ב-$G(A)$ כך ש-$x+qg$ אינו מפר את החסמים ומעניק שיפור מיטבי; עדכן $x:=x+qg$ והמשך לאיטרציה הבאה. הנקודה האחרונה $x$ היא אופטימלית ומספר האיטרציות הוא פולינומי. כדי למצוא נקודה אפשרית ראשונית ניתן להגדיר ולפתור בעיית עזר מתאימה בה יש נקודה ראשונית טריביאלית ולפתור אותה באופן דומה.

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

עבור פונקציות מטרה כלליות $f$, אם המשתנים אינם חסומים אז הבעיה עלולה להיות בלתי ניתנת לחישוב: מהפתרון של הבעיה העשירית של הילברט עולה כי אין אלגוריתם אשר בהינתן פולינום $f$ עם מקדמים שלמים מדרגה 8 ב־58 משתנים, מחליט אם הערך המינימלי של $f$ על כל הווקטורים השלמים ממימד 58 הוא 0. לעומת זאת, כאשר המשתנים חסומים, הבעיה

$\min\{f(x)\ :\ x\in \mathbb {Z} ^{n},\ Ax=b,\ l\leq x\leq u\}$

ניתנת לפתרון באמצעות בסיס גרייבר $G(A)$ בזמן פולינומי למספר פונקציות מטרה לא ליניאריות, כולל:

• פונקציות קמורות פריקות מהצורה $f(x)=\sum _{i=1}^{n}f_{i}(x_{i})$ ;
• בפרט ה- p-norm $f(x)=\|x\|_{p}$ עבור כל מספר שלם חיובי $p$ ;
• פונקציות מורכבות קעורות $f(x)=g(Wx)$, כאשר $W$ היא מטריצה $d\times n$ בשלמים, $d$ קבוע, ו-$g$ פונקציה קעורה של $d$ משתנים;
• מחלקות מסוימות של פונקציות ריבועיות ופולינומיות מדרגות גבוהות יותר.

מספר יישומים

טבלאות רב ממדיות

נתבונן בבעיית האופטימיזציה הבאה על טבלאות תלת־ממדיות עם סכומי קוים נתונים,

$\min\{wx\ :\ x\in {\mathbb {Z} }_{+}^{l\times m\times n}\,,\ \sum _{i}x_{i,j,k}=a_{j,k}\,,\ \sum _{j}x_{i,j,k}=b_{i,k}\,,\ \sum _{k}x_{i,j,k}=c_{i,j}\}\ ,$

כאשר $a_{j,k}$, $b_{i,k}$, $c_{i,j}$ מספרים שלמים אי-שליליים (שערכם המרבי חוסם באופן מרומז את כל המשתנים מלמעלה). נסמן ב-$A$ את המטריצה $(lmn)\times (lm+ln+mn)$ המגדירה מערכת זו. שים לב שמטריצה זו בדרך כלל "אינה" מודולרית לחלוטין . עם זאת, הוכח ב- כי לכל $l$ ו-$m$ קבועים, בסיס הגרייבר $G(A)$ ניתן לחישוב בזמן שהוא פולינום ב- $n$. לכן התוצאות שהוזכרו לעיל מאפשרות לפתור בעיה זו בזמן פולינומי עבור $l$ ו-$m$ קבועים ו-$n$ משתנה. נעיר שאם רק צד אחד $l$ של הטבלה הוא קבוע (אפילו עם $l=3$) בעוד ש-$m$ ו-$n$ משתנים, הבעיה קשה ב-NP. באופן כללי יותר, תוצאות חיוביות דומות תקפות בבעיות טבלאות מממדים גבוהים יותר: עבור כל $d$ ו-$m_{1},\dots ,m_{d}$ קבועים, אופטימיזציה (לא) ליניארית מעל טבלאות $m_{1}\times \cdots \times m_{d}\times n$ עם $n$ משתנה ושוליים נתונים ניתנת לבצוע בזמן פולינומי. לבעיות אלה יש בפרט יישומים לבעיות אבטחה ופרטיות במסדי נתונים סטטיסטיים.

זרימה מרובת סחורות

נתבונן בבעיית הזרימה מרובת הסחורות בשלמים, של ניתוב $k$ סוגי סחורות בדידות מ-$m$ ספקים ל-$n$ צרכנים בכפוף לאילוצי היצע, צריכה, וקיבולת, כדי למזער את סכום העלויות הליניאריות או הקמורות התלויות בגודש בקשתות. עבור כל $k$ ו-$m$ קבועים, ניתן לחשב את בסיס הגרייבר של המערכת המגדירה, וניתן למזער את העלות, שהיא פונקציה קמורה ופריקה, בזמן שהוא פולינום במספר המשתנה $n$ של הצרכנים ובשאר הנתונים.

יישומים אחרים

היישומים הרבים של התאוריה האלגוריתמית של בסיסי גרייבר כוללים גם תכנות בשלמים סטוכסטי, תכנות N-fold בשלמים, אישכול, ושחרור מבוקר במסדי נתונים סטטיסטיים. בחלק מהיישומים הללו לא ניתן לחשב את בסיס הגרייבר הרלוונטי בזמן פולינומי, אך ניתן לגשת אליו באופן עקיף המאפשר להשתמש בו בזמן פולינומי.

אוניברסליות ופרמטריזציה

כל בעיית תכנות בשלמים (חסומה) שקולה בדיוק לבעיית טבלאות $3\times m\times n$ שנדונה לעיל עבור $m$ ו-$n$ וסכומי קוים כלשהם. לפיכך, בעיות טבלאות אלה הן אוניברסליות עבור תכנות בשלמים. יתר על כן, עבור כל $m$ קבוע, ניתן לפתור את המחלקה המתקבלת של בעיות תכנות בשלמים בזמן פולינומי כמתואר לעיל. לפיכך רוחב הטבלה $m$ מספק פרמטריזציה של כל בעיות התכנות בשלמים.

סיבוכיות פרמטרית: מסיבוכיות זמן פולינומית לסיבוכיות זמן מעוקבת

סיבוכיות הזמן של פתרון חלק מהיישומים שנדונו לעיל, כמו בעיות הטבלאות הרב ממדיות, בעיות הזרימה מרובות הסחורות ובעיות תכנות N-fold בשלמים, נשלטת על ידי מספר האיברים בבסיס הגרייבר הרלוונטי, שהוא פולינום $O\left(n^{g}\right)$ מדרגה גדולה בדרך כלל, הנקראת מורכבות הגרייבר $g$ של המערכת. אולם, קיים אלגוריתם מהיר בהרבה, שמוצא בכל איטרציה את השיפור הטוב ביותר $x+qg$ כאשר $q$ שלם חיובי ו- $g$ אלמנט ב-$G(A)$ מבלי לבנות במפורש את בסיס הגרייבר, בזמן מעוקב $O\left(n^{3}\right)$ ללא קשר למערכת. במונחים של סיבוכיות פרמטרית, תוצאה זו מראה שכל הבעיות הללו עם פרמטריזציה מתאימה, ובפרט בעיות בטבלאות תלת־ממדיות $l\times m\times n$ כאשר $l$ ו-$m$ פרמטרים, הן fixed parameter tractable.