בסיס גרייבר

במתמטיקה שימושית, בסיסי גרייבר (Graver bases) מאפשרים פתרונות איטרטיביים של בעיות תכנות בשלמים ליניאריות ולא ליניאריות שונות בזמן פולינומי. הם הוגדרו לראשונה על ידי ג'ק גרייבר.<ref name="Gra">Jack E. Graver: On the foundations of linear and linear integer programming, Mathematical Programming 9:207–226, 1975</ref> ברנד שטורמפלס תיאר את הקשר שלהם לתורת בסיסי גרובנר.<ref name="Stu">Bernd Sturmfels, "Gröbner Bases and Convex Polytopes", American Mathematical Society, xii+162 pp., 1996</ref> התיאוריה האלגוריתמית של בסיסי גרייבר ויישומה לתכנות בשלמים מתוארת על ידי שמואל און.<ref name="Onn">[http://ie.technion.ac.il/~onn Shmuel onn]: [https://books.google.com/books?id=yXvfDzHo-WsC&printsec=frontcover&dq=inauthor:%22Shmuel+Onn%22&hl=en&ei=ccjLToGAPMXLhAep-ZznDQ&sa=X&oi=book_result&ct=result&redir_esc=y#v=onepage&q=inauthor%3A%22Shmuel%20Onn%22&f=false "Nonlinear Discrete Optimization"], European Mathematical Society, x+137 pp., 2010</ref><ref name="MSRI">Shmuel Onn: [http://www.msri.org/web/msri/online-videos/-/video/showSpeaker/200002593 Linear and nonlinear integer optimization], Online Video Lecture Series, Mathematical Sciences Research Institute, Berkeley, 2010</ref>

== הגדרה רשמית ==
בסיס הגרייבר של מטריצה <math>m\times n</math> בשלמים <math>A</math> היא הקבוצה הסופית <math>G(A)</math> של אלמנטים מינימליים בקבוצה

: <math>\{x\in\mathbb{Z}^n : Ax=0,\ x\neq 0\} \, </math>

תחת סדר חלקי על <math>\mathbb{Z}^n</math> המוגדר על ידי <math>x\sqsubseteq y</math> כאשר <math>x_iy_i\geq 0</math> ו- <math>|x_i|\leq |y_i|</math> לכל i. לדוגמה, בסיס גרייבר של <math>A=(1, 2, 1)</math> מורכב מהווקטורים (1&#x2212;,1,0), (1,0&#x2212;,2), (2 ,1&#x2212;,0), (1,1&#x2212;,1) ושליליותיהם.

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

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

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

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

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

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

עם זאת, בהינתן בסיס הגרייבר <math>G(A)</math> של <math>A</math> ניתן לפתור אותה בזמן פולינומי באמצעות האלגוריתם האיטרטיבי הפשוט הבא.<ref name="Onn">[http://ie.technion.ac.il/~onn Shmuel onn]: [https://books.google.com/books?id=yXvfDzHo-WsC&printsec=frontcover&dq=inauthor:%22Shmuel+Onn%22&hl=en&ei=ccjLToGAPMXLhAep-ZznDQ&sa=X&oi=book_result&ct=result&redir_esc=y#v=onepage&q=inauthor%3A%22Shmuel%20Onn%22&f=false "Nonlinear Discrete Optimization"], European Mathematical Society, x+137 pp., 2010</ref><ref name="HOW">Raymond Hemmecke, Shmuel Onn, Robert Weismantel: A polynomial oracle-time
algorithm for convex integer minimization, Mathematical Programming
126:97–117, 2011</ref> נניח תחילה כי ניתנת איזו נקודה <math>x</math> אפשרית ראשונית. כל עוד הדבר אפשרי, חזור על האיטרציה הבאה: מצא מספר שלם חיובי <math>q</math> ואלמנט <math>g</math> ב-<math>G(A)</math> כך ש-<math>x+qg</math> אינו מפר את החסמים ומעניק שיפור מיטבי; עדכן <math>x:=x+qg</math> והמשך לאיטרציה הבאה. הנקודה האחרונה <math>x</math> היא אופטימלית ומספר האיטרציות הוא פולינומי. כדי למצוא נקודה אפשרית ראשונית ניתן להגדיר ולפתור בעיית עזר מתאימה בה יש נקודה ראשונית טריביאלית ולפתור אותה באופן דומה.

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

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

ניתנת לפתרון באמצעות בסיס גרייבר <math>G(A)</math> בזמן פולינומי למספר פונקציות מטרה לא ליניאריות, כולל:
* פונקציות קמורות פריקות מהצורה <math>f(x)=\sum_{i=1}^n f_i(x_i)</math> ;
* בפרט ה- p-norm <math>f(x)=\|x\|_p</math> עבור כל מספר שלם חיובי <math>p</math> ;
* פונקציות מורכבות קעורות <math>f(x)=g(Wx)</math>, כאשר <math>W</math> היא מטריצה <math>d\times n</math> בשלמים, <math>d</math> קבוע, ו-<math>g</math> פונקציה קעורה של <math>d</math> משתנים;
* מחלקות מסוימות של פונקציות ריבועיות ופולינומיות מדרגות גבוהות יותר.

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

: <math>\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}\}\ ,</math>

כאשר <math>a_{j,k}</math>, <math>b_{i,k}</math>, <math>c_{i,j}</math> מספרים שלמים אי-שליליים (שערכם המרבי חוסם באופן מרומז את כל המשתנים מלמעלה). נסמן ב-<math>A</math> את המטריצה <math>(lmn)\times(lm+ln+mn)</math> המגדירה מערכת זו. שים לב שמטריצה זו בדרך כלל "אינה" מודולרית לחלוטין . עם זאת, הוכח ב-<ref name="DHOW">Jesús A. De Loera, Raymond Hemmecke, Shmuel Onn, Robert Weismantel: "N"-fold integer programming, Discrete
Optimization, 5:231–241, 2008</ref> כי לכל <math>l</math> ו-<math>m</math> קבועים, בסיס הגרייבר <math>G(A)</math> ניתן לחישוב בזמן שהוא פולינום ב- <math>n</math>. לכן התוצאות שהוזכרו לעיל מאפשרות לפתור בעיה זו בזמן פולינומי עבור <math>l</math> ו-<math>m</math> קבועים ו-<math>n</math> משתנה. נעיר שאם רק צד אחד <math>l</math> של הטבלה הוא קבוע (אפילו עם <math>l=3</math>) בעוד ש-<math>m</math> ו-<math>n</math> משתנים, הבעיה קשה ב-NP<ref name="DO1">Jesús A. De Loera, Shmuel Onn: The complexity of
three-way statistical tables, SIAM Journal on Computing, 33:819–836, 2004</ref>. באופן כללי יותר, תוצאות חיוביות דומות תקפות בבעיות טבלאות מממדים גבוהים יותר<ref name="Mot">Theodore S. Motzkin: The multi-index transportation
problem, Bulletin of the American Mathematical Society 58:494, 1952</ref>: עבור כל <math>d</math> ו-<math>m_1, \dots, m_d</math> קבועים, אופטימיזציה (לא) ליניארית מעל טבלאות <math>m_1 \times \cdots \times m_d \times n</math> עם <math>n</math> משתנה ושוליים נתונים ניתנת לבצוע בזמן פולינומי. לבעיות אלה יש בפרט יישומים לבעיות אבטחה ופרטיות במסדי נתונים סטטיסטיים.

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

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

== אוניברסליות ופרמטריזציה ==
כל בעיית תכנות בשלמים (חסומה) שקולה בדיוק לבעיית טבלאות <math>3\times m\times n</math> שנדונה לעיל עבור <math>m</math> ו-<math>n</math> וסכומי קוים כלשהם<ref name="DO2">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</ref>. לפיכך, בעיות טבלאות אלה הן אוניברסליות עבור תכנות בשלמים. יתר על כן, עבור כל <math>m</math> קבוע, ניתן לפתור את המחלקה המתקבלת של בעיות תכנות בשלמים בזמן פולינומי כמתואר לעיל. לפיכך רוחב הטבלה <math>m</math> מספק פרמטריזציה של כל בעיות התכנות בשלמים.

== סיבוכיות פרמטרית: מסיבוכיות זמן פולינומית לסיבוכיות זמן מעוקבת ==
סיבוכיות הזמן של פתרון חלק מהיישומים שנדונו לעיל, כמו בעיות הטבלאות הרב ממדיות, בעיות הזרימה מרובות הסחורות ובעיות תכנות N-fold בשלמים, נשלטת על ידי מספר האיברים בבסיס הגרייבר הרלוונטי, שהוא פולינום <math>O\left(n^g\right)</math> מדרגה גדולה בדרך כלל, הנקראת מורכבות הגרייבר <math>g</math> של המערכת. אולם, קיים אלגוריתם מהיר בהרבה, שמוצא בכל איטרציה את השיפור הטוב ביותר <math>x+qg</math> כאשר <math>q</math> שלם חיובי ו- <math>g</math> אלמנט ב-<math>G(A)</math> מבלי לבנות במפורש את בסיס הגרייבר, בזמן מעוקב <math>O\left(n^3\right)</math> ללא קשר למערכת<ref name="HOR">Raymond Hemmecke, Shmuel Onn, Lyubov Romanchuk: "N"-fold integer programming in cubic time, Mathematical Programming, 137:325–341, 2013</ref>. במונחים של סיבוכיות פרמטרית, תוצאה זו מראה שכל הבעיות הללו עם פרמטריזציה מתאימה, ובפרט בעיות בטבלאות תלת־ממדיות <math>l\times m\times n</math>&nbsp;כאשר <math>l</math> ו-<math>m</math> פרמטרים, הן fixed parameter tractable.

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

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