בסיס גרייבר

במתמטיקה שימושית, בסיסי גרייבר (Graver bases) מאפשרים פתרונות איטרטיביים של בעיות תכנות בשלמים ליניאריות ולא ליניאריות שונות בזמן פולינומי. הם הוגדרו לראשונה על ידי ג'ק גרייבר.Jack E. Graver: On the foundations of linear and linear integer programming, Mathematical Programming 9:207–226, 1975 ברנד שטורמפלס תיאר את הקשר שלהם לתורת בסיסי גרובנר.Bernd Sturmfels, "Gröbner Bases and Convex Polytopes", American Mathematical Society, xii+162 pp., 1996 התיאוריה האלגוריתמית של בסיסי גרייבר ויישומה לתכנות בשלמים מתוארת על ידי שמואל און.Shmuel onn: "Nonlinear Discrete Optimization", European Mathematical Society, x+137 pp., 2010Shmuel Onn: Linear and nonlinear integer optimization, Online Video Lecture Series, Mathematical Sciences Research Institute, Berkeley, 2010

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



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

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



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

 תכנות ליניארי בשלמים 
המקרה הנחקר ביותר, הוא של תכנות ליניארי בשלמיםAlexander Schrijver: "Theory of Linear and Integer Programming", Wiley, xii+471 pp., 1986,



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

עם זאת, בהינתן בסיס הגרייבר  של  ניתן לפתור אותה בזמן פולינומי באמצעות האלגוריתם האיטרטיבי הפשוט הבא.Shmuel onn: "Nonlinear Discrete Optimization", European Mathematical Society, x+137 pp., 2010Raymond Hemmecke, Shmuel Onn, Robert Weismantel: A polynomial oracle-time
algorithm for convex integer minimization, Mathematical Programming
126:97–117, 2011 נניח תחילה כי ניתנת איזו נקודה  אפשרית ראשונית. כל עוד הדבר אפשרי, חזור על האיטרציה הבאה: מצא מספר שלם חיובי  ואלמנט  ב- כך ש- אינו מפר את החסמים ומעניק שיפור מיטבי; עדכן  והמשך לאיטרציה הבאה. הנקודה האחרונה  היא אופטימלית ומספר האיטרציות הוא פולינומי. כדי למצוא נקודה אפשרית ראשונית ניתן להגדיר ולפתור בעיית עזר מתאימה בה יש נקודה ראשונית טריביאלית ולפתור אותה באופן דומה.

 תכנות לא ליניארי בשלמים 
עבור פונקציות מטרה כלליות , אם המשתנים אינם חסומים אז הבעיה עלולה להיות בלתי ניתנת לחישוב: מהפתרון של הבעיה העשירית של הילברטYuri V. Matiyasevich: "Hilbert's Tenth Problem", MIT Press, xxiv+264 pp., 1993 עולה כי אין אלגוריתם אשר בהינתן פולינום  עם מקדמים שלמים מדרגה 8 ב־58 משתנים, מחליט אם הערך המינימלי של  על כל הווקטורים השלמים ממימד 58 הוא 0. לעומת זאת, כאשר המשתנים חסומים, הבעיה



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

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



כאשר , ,  מספרים שלמים אי-שליליים (שערכם המרבי חוסם באופן מרומז את כל המשתנים מלמעלה). נסמן ב- את המטריצה  המגדירה מערכת זו. שים לב שמטריצה זו בדרך כלל "אינה" מודולרית לחלוטין . עם זאת, הוכח ב-Jesús A. De Loera, Raymond Hemmecke, Shmuel Onn, Robert Weismantel: "N"-fold integer programming, Discrete
Optimization, 5:231–241, 2008 כי לכל  ו- קבועים, בסיס הגרייבר  ניתן לחישוב בזמן שהוא פולינום ב- . לכן התוצאות שהוזכרו לעיל מאפשרות לפתור בעיה זו בזמן פולינומי עבור  ו- קבועים ו- משתנה. נעיר שאם רק צד אחד  של הטבלה הוא קבוע (אפילו עם ) בעוד ש- ו- משתנים, הבעיה קשה ב-NPJesús A. De Loera, Shmuel Onn: The complexity of
three-way statistical tables, SIAM Journal on Computing, 33:819–836, 2004. באופן כללי יותר, תוצאות חיוביות דומות תקפות בבעיות טבלאות מממדים גבוהים יותרTheodore S. Motzkin: The multi-index transportation
problem, Bulletin of the American Mathematical Society 58:494, 1952: עבור כל  ו- קבועים, אופטימיזציה (לא) ליניארית מעל טבלאות  עם  משתנה ושוליים נתונים ניתנת לבצוע בזמן פולינומי. לבעיות אלה יש בפרט יישומים לבעיות אבטחה ופרטיות במסדי נתונים סטטיסטיים.

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

 יישומים אחרים 
היישומים הרבים של התאוריה האלגוריתמית של בסיסי גרייבר כוללים גם תכנות בשלמים סטוכסטי,Raymond Hemmecke, Shmuel Onn, Robert Weismantel: A polynomial oracle-time
algorithm for convex integer minimization, Mathematical Programming
126:97–117, 2011 תכנות N-fold בשלמים,Raymond Hemmecke, Matthias Köppe, Robert Weismantel: A polynomial-time algorithm for optimizing over "N"-fold 4-block decomposable integer programs, IPCO 14, 2010 אישכול, ושחרור מבוקר במסדי נתונים סטטיסטיים. בחלק מהיישומים הללו לא ניתן לחשב את בסיס הגרייבר הרלוונטי בזמן פולינומי, אך ניתן לגשת אליו באופן עקיף המאפשר להשתמש בו בזמן פולינומי.

 אוניברסליות ופרמטריזציה 
כל בעיית תכנות בשלמים (חסומה) שקולה בדיוק לבעיית טבלאות  שנדונה לעיל עבור   ו- וסכומי קוים כלשהם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. לפיכך, בעיות טבלאות אלה הן אוניברסליות עבור תכנות בשלמים. יתר על כן, עבור כל  קבוע, ניתן לפתור את המחלקה המתקבלת של בעיות תכנות בשלמים בזמן פולינומי כמתואר לעיל. לפיכך רוחב הטבלה  מספק פרמטריזציה של כל בעיות התכנות בשלמים.

 סיבוכיות פרמטרית: מסיבוכיות זמן פולינומית לסיבוכיות זמן מעוקבת 
סיבוכיות הזמן של פתרון חלק מהיישומים שנדונו לעיל, כמו בעיות הטבלאות הרב ממדיות, בעיות הזרימה מרובות הסחורות ובעיות תכנות N-fold בשלמים, נשלטת על ידי מספר האיברים בבסיס הגרייבר הרלוונטי, שהוא פולינום  מדרגה גדולה בדרך כלל, הנקראת מורכבות הגרייבר  של המערכת. אולם, קיים אלגוריתם מהיר בהרבה, שמוצא בכל איטרציה את השיפור הטוב ביותר  כאשר  שלם חיובי ו-  אלמנט ב- מבלי לבנות במפורש את בסיס הגרייבר, בזמן מעוקב  ללא קשר למערכתRaymond Hemmecke, Shmuel Onn, Lyubov Romanchuk: "N"-fold integer programming in cubic time, Mathematical Programming, 137:325–341, 2013. במונחים של סיבוכיות פרמטרית, תוצאה זו מראה שכל הבעיות הללו עם פרמטריזציה מתאימה, ובפרט בעיות בטבלאות תלת־ממדיות  כאשר  ו- פרמטרים, הן fixed parameter tractable.

 הערות שוליים 

קטגוריה:אופטימיזציה מתמטית
קטגוריה:אופטימיזציה בדידה