בסיס גרייבר

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

הגדרה רשמיתעריכה

בסיס הגרייבר של מטריצה   בשלמים   היא הקבוצה הסופית   של אלמנטים מינימליים בקבוצה

 

תחת סדר חלקי על   המוגדר על ידי   כאשר   ו-   לכל i. לדוגמה, בסיס גרייבר של   מורכב מהווקטורים (1−,1,0), (1,0−,2), (2 ,1−,0), (1,1−,1) ושליליותיהם.

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

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

 

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

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

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

 

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

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

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

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

 

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

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

מספר יישומיםעריכה

טבלאות רב ממדיותעריכה

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

 

כאשר  ,  ,   מספרים שלמים אי-שליליים (שערכם המרבי חוסם באופן מרומז את כל המשתנים מלמעלה). נסמן ב-  את המטריצה   המגדירה מערכת זו. שים לב שמטריצה זו בדרך כלל "אינה" מודולרית לחלוטין . עם זאת, הוכח ב-[8] כי לכל   ו-  קבועים, בסיס הגרייבר   ניתן לחישוב בזמן שהוא פולינום ב-  . לכן התוצאות שהוזכרו לעיל מאפשרות לפתור בעיה זו בזמן פולינומי עבור   ו-  קבועים ו-  משתנה. נעיר שאם רק צד אחד   של הטבלה הוא קבוע (אפילו עם  ) בעוד ש-  ו-  משתנים, הבעיה קשה ב-NP[9]. באופן כללי יותר, תוצאות חיוביות דומות תקפות בבעיות טבלאות מממדים גבוהים יותר[10]: עבור כל   ו-  קבועים, אופטימיזציה (לא) ליניארית מעל טבלאות   עם   משתנה ושוליים נתונים ניתנת לבצוע בזמן פולינומי. לבעיות אלה יש בפרט יישומים לבעיות אבטחה ופרטיות במסדי נתונים סטטיסטיים.

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

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

יישומים אחריםעריכה

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

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

כל בעיית תכנות בשלמים (חסומה) שקולה בדיוק לבעיית טבלאות   שנדונה לעיל עבור   ו-  וסכומי קוים כלשהם[12]. לפיכך, בעיות טבלאות אלה הן אוניברסליות עבור תכנות בשלמים. יתר על כן, עבור כל   קבוע, ניתן לפתור את המחלקה המתקבלת של בעיות תכנות בשלמים בזמן פולינומי כמתואר לעיל. לפיכך רוחב הטבלה   מספק פרמטריזציה של כל בעיות התכנות בשלמים.

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

סיבוכיות הזמן של פתרון חלק מהיישומים שנדונו לעיל, כמו בעיות הטבלאות הרב ממדיות, בעיות הזרימה מרובות הסחורות ובעיות תכנות N-fold בשלמים, נשלטת על ידי מספר האיברים בבסיס הגרייבר הרלוונטי, שהוא פולינום   מדרגה גדולה בדרך כלל, הנקראת מורכבות הגרייבר   של המערכת. אולם, קיים אלגוריתם מהיר בהרבה, שמוצא בכל איטרציה את השיפור הטוב ביותר   כאשר   שלם חיובי ו-   אלמנט ב-  מבלי לבנות במפורש את בסיס הגרייבר, בזמן מעוקב   ללא קשר למערכת[13]. במונחים של סיבוכיות פרמטרית, תוצאה זו מראה שכל הבעיות הללו עם פרמטריזציה מתאימה, ובפרט בעיות בטבלאות תלת ממדיות   כאשר   ו-  פרמטרים, הן fixed parameter tractable.

הערות שולייםעריכה

  1. ^ Jack E. Graver: On the foundations of linear and linear integer programming, Mathematical Programming 9:207–226, 1975
  2. ^ Bernd Sturmfels, "Gröbner Bases and Convex Polytopes", American Mathematical Society, xii+162 pp., 1996
  3. ^ 1 2 Shmuel onn: "Nonlinear Discrete Optimization", European Mathematical Society, x+137 pp., 2010
  4. ^ Shmuel Onn: Linear and nonlinear integer optimization, Online Video Lecture Series, Mathematical Sciences Research Institute, Berkeley, 2010
  5. ^ Alexander Schrijver: "Theory of Linear and Integer Programming", Wiley, xii+471 pp., 1986
  6. ^ 1 2 Raymond Hemmecke, Shmuel Onn, Robert Weismantel: A polynomial oracle-time algorithm for convex integer minimization, Mathematical Programming 126:97–117, 2011
  7. ^ Yuri V. Matiyasevich: "Hilbert's Tenth Problem", MIT Press, xxiv+264 pp., 1993
  8. ^ Jesús A. De Loera, Raymond Hemmecke, Shmuel Onn, Robert Weismantel: "N"-fold integer programming, Discrete Optimization, 5:231–241, 2008
  9. ^ Jesús A. De Loera, Shmuel Onn: The complexity of three-way statistical tables, SIAM Journal on Computing, 33:819–836, 2004
  10. ^ Theodore S. Motzkin: The multi-index transportation problem, Bulletin of the American Mathematical Society 58:494, 1952
  11. ^ Raymond Hemmecke, Matthias Köppe, Robert Weismantel: A polynomial-time algorithm for optimizing over "N"-fold 4-block decomposable integer programs, IPCO 14, 2010
  12. ^ Jesus A. De Loera, Shmuel Onn: All linear and integer programs are slim 3-way transportation programs, SIAM Journal on Optimization, 17:806–821, 2006
  13. ^ Raymond Hemmecke, Shmuel Onn, Lyubov Romanchuk: "N"-fold integer programming in cubic time, Mathematical Programming, 137:325–341, 2013