lrsfourier - מקוון בענן

תָכְנִית:

שֵׁם

lrslib - המר בין חזרות של פוליהדרות קמורות.

תַקצִיר

LRS input.ine

LRS input.ine | lrsbuffer

lrsfourier file.ine [fileout]

מיותר input.ine

תיאור

ניתן לתאר פולידרון על ידי רשימה של אי שוויון (H-ייצוג) או לפי רשימה
של הקודקודים והקרניים הקיצוניות שלו (ייצוג V). LRS היא תוכנית C הממירה א
H-ייצוג של פולידרון לייצוג ה-V שלו, ולהיפך. הבעיות הללו
ידועים בהתאמה ב- קָדקוֹד ספירה ו קמור לְקַלֵף בעיות.

של פוקודה שאלות נפוצות עמוד[1] מכיל מבוא מפורט יותר לבעיה, יחד עם
עצות שימושיות רבות למשתמש החדש.

lrsbuffer יכול להסיר פלט כפול כלשהו. מיותר מוצא אי שוויון מיותרים ב
קֶלֶט.

קובץ פורמטים

פורמטים של קבצים פותחו במשותף עם Komei Fukuda והם תואמים CDD[2].

הקלט עבור LRS הוא ייצוג H- או V- של פוליטופ.

שם
{קו ייצוג}
{אפשרויות}
{לינאריות[3]}
להתחיל
mn רציונלי
{מטריצת קלט}
סוף
{אפשרויות}

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

שם הוא שם שסופק על ידי המשתמש עבור הפוליטופ. נציגות קו הוא או
"ייצוג H" או "ייצוג V". אם מושמט, מניחים ייצוג H. ה
מקדמי קלט נקראים בפורמט חופשי, ואינם מסומנים עבור סוג. מקדמים הם
מופרדים על ידי רווח לבן. m הוא מספר השורות ו-n מספר העמודות של הקלט
מטריקס.

H-ייצוג
המספר השלם m הוא מספר האי-שוויון, והמספר השלם n הוא הממד של ה
קלט 1+. רשימה של אי-שוויון מכילה את מקדמי אי-השוויון של הצורה

a0 + a1x1+ ... + an-1 xn-1 >= 0.

אי שוויון זה מוקלט בתור הקו

a0 a1... an-1

ניתן להזין את המקדמים כמספרים שלמים או רציונלים בתבנית x/y.

ייצוג V
המספר השלם m הוא מספר הקודקודים והקרניים, והמספר השלם n הוא הממד של
הקלט +1. כל קודקוד ניתן בטופס

1 v0 v 1... vn-1

כל קרן ניתנת בצורה

0 r0 r 1... rn-1

כאשר r0 r 1... rn-1 היא נקודה על הקרן.

חייב להיות קודקוד אחד לפחות בכל קובץ. עבור polyhedra תחום לא יהיה
נכנסו קרניים. ניתן להזין את המקדמים כמספרים שלמים או רציונלים בתבנית x/y.

הערות ל CDD משתמשים: LRS משתמש בעצם באותו פורמט קובץ כמו CDD. קבצים שהוכנו עבור
CDD אמור לעבוד עם מעט או ללא שינוי. שים לב כי ייצוג V
מתאימה לאפשרות "גוף" ב CDD. אפשרויות ספציפיות ל CDD ניתן להשאיר בקלט
קבצים ויתעלם על ידי LRS. שימו לב לקבצי הקלט עבור LRS נקראים בפורמט חופשי,
אחרי השורה m n רַצִיוֹנָלִי, LRS יחפש בדיוק m*n רציונלים או מספרים שלמים מופרדים
לפי רווח לבן (ריק, החזרת כרכרה, לשונית וכו'). LRS לא "יפיל" עמודות נוספות של
קלט אם n קטן ממספר העמודות שסופקו.

בסיסי אפשרויות
כמעט כל האפשרויות ממוקמות לאחר הצהרת הסיום, שמירה על תאימות עם CDD.
אם זה לא המצב, זה יוזכר במפורש.

allbases אפשרות זו מורה LRS לרשום כל קודקוד (או פן) עבור כל אחד מהבסיסים שלו.
תְפוּקָה כפילות[4].[5] אפשרות זו משולבת לעתים קרובות עם printcobasis.

קשור x השתמש עם H-representation - עבור lrs או nash או למקסם או למזער
יש לבחור באפשרות. x הוא מספר שלם או רציונל. למקסום (בהתאמה.
מזעור) עץ החיפוש ההפוך נחתך בכל פעם שהערך האובייקטיבי הנוכחי
הוא פחות (לפי יותר) מ-x.

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

באגים בסיס התחלה בסיס סיוםהדפס מעקב סתמי אך מפורט, מילונים וכו'.
מתחיל ב-#B=startingbasis ומסתיים ב-#B=endingbasis. באגים 0 0 נותן שלם
עקבות.

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

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

הערכות k הערך את גודל הפלט. משמש בשילוב עם maxdepth - ראה
אוּמדָן.[6]

גאומטרי // H-representation או voronoi אפשרות בלבד // עם אפשרות זו, כל קרן היא
מודפס יחד עם הקודקוד איתו הוא מתרחש. למידע נוסף ראה
קרניים גיאומטריות פנימה רמזים ו תגובות[5].

שכיחותאפשרות זו מופעלת אוטומטית printcobasis , אז ראה להלן עבור א
תחילה תיאור של אפשרות זו. ניתן להשתמש עם printcobasis n. (Ver 4.2b) .PP For
ייצוג קלט H, מדדים של כל אי-השוויון בקלט המכילים את הקודקוד/קרן ש
עומד להיות פלט. עבור פרצוף פשוט, אין פלט חדש, מאז המדדים האלה
כבר רשומים. אחרת, אי השוויון ההדוק הנוספים רשומים אחרי נקודתיים.
.PP לייצוג V קלט, מדדים של כל קודקודי/קרני הקלט השוכנים על הפן
שעומד להיות פלט. אינדקס מסומן בכוכב מציין שקודקוד זה נמצא גם ב-
cobasis, אך אינו כלול בפן. זה מתעורר עקב פעולת ההרמה שבה נעשה שימוש
עם ייצוגי V קלט.

#שכיחותאותו דבר כמו printcobasis. כלול עבור תאימות עם cdd.

ליניאריות k i1i2 i ... ikהקלט מכיל k ליניאריות בשורות i1i2i ... ikשל
קובץ הקלט הם משוואות. לִרְאוֹת לינאריות.[3]

מקסימום עומק k החיפוש יקוצץ בעומק k. כל הבסיסים עם עומק קטן מ- או
שווה ל-k יחושב. k הוא מספר שלם לא שלילי, ואפשרות זו משמשת עבור
הערכות - ראה אוּמדָן.[6]הערות: עבור ייצוגי H, קרניים בעומק k לא יהיו
דיווח. עבור ייצוגי V, היבטים בעומק k לא ידווחו.

להגדיל a0 a1 ... an-1 // ייצוג H בלבד //

לצמצם a0 a1 ... an-1 // ייצוג H בלבד //

אם נעשה שימוש עם lrs, קודקוד ההתחלה ממקסם (או ממזער) את הפונקציה a0 + a1x1+ ...
+ an-1 xn-1. ייתכן שיהיה צורך באפשרות כפול-הפרעות כדי למנוע ניוון כפול. ראה נאש
שיווי משקל ו לינארי תכנות[7]

maxoutput n מגביל את מספר קווי הפלט שנוצרו (קודקודים+קרניים או היבטים) ל-n

תודעה k המסלול לאחור יסתיים בעומק k, עבור מספר שלם של ka לא שלילי. זֶה
יכול לשמש להפעלת חיפוש הפוך על עצי משנה כתהליכים נפרדים, למשל ב-a
סביבת מחשוב מבוזרת.

לא שלילי // אפשרות זו חייבת לבוא לפני הצהרת begin// //H-representation בלבד
// באג: ניתן להשתמש רק אם המקור הוא קודקוד של הפולידרון לבעיות היכן
הקלט הוא ייצוג H של הצורה b+Ax>=0, x>=0 (כלומר כל המשתנים
לא שלילי, כל האילוצים אי שוויון) אין צורך לתת את הלא שלילי
אילוצים במפורש אם נעשה שימוש באפשרות הלא-שלילית. לא ניתן להשתמש באפשרות זו עבור
ייצוגי V, או עם אפשרות הליניאריות (במקרה זה הלינאריות יהיו
מתייחסים אליו כאל אי שוויון). ניתן להשתמש באפשרות זו עם redund , אך המשתמע
אילוצי אי-שליליות אינם נבדקים בעצמם לגבי יתירות. כדי לבדוק הכל את זה
יש צורך להזין את אילוצי הבלתי-שליליות במפורש בקובץ הקלט. (ב-Ver
4.1, המקור חייב להיות קודקוד).

printcobasis k;שונה ב-lrs 4.0 כל k'th cobasis מודפס. אם k מושמט, ה-
cobasis מודפס עבור כל קודקוד/קרן/פן שמופק. לטווח ארוך זה שימושי
כדי להדפיס את ה-cobas מדי פעם כדי שניתן יהיה להפעיל מחדש את התוכנית במידת הצורך.
ייצוג H: אם הקלט הוא ייצוג H, הקובסיס הוא רשימה של המדדים
אי השוויון מקובץ הקלט שמגדירים את הקודקוד או הקרן הנוכחית. ראה אפשרות
שכיחות לעיל למידע נוסף. עבור קרניים, מודפס גם קובסיס. במקרה הזה
הקו-בסיס הוא הקו-בסיס של הקודקוד שממנו בוקעת הקרן. אחד המדדים
מסומן בכוכב, זה מציין את אי-השוויון שיש להוריד מה-cobase כדי להגדיר את
קֶרֶן. לחילופין, אם ה allbasesנעשה שימוש באפשרות, כל הקובסים יודפסו.
ייצוג V: אם הקלט הוא ייצוג V, ה-cobasis הוא רשימה של הקלט
קודקודים / קרניים המגדירים את הפן הנוכחי. ראה אפשרות שכיחות למעלה לעוד
מֵידָע. ליזום LRS מהפן הזה יש לתת את כל 4 המדדים בסדר הזה
(השמיט את ה*).

printslack חדש בגרסה 4.2; // השתמש עם H-representation // lrs מדפיס רשימה של
מדדים של אי-השוויון הקלט שמסופקים אך ורק עבור הקודקוד הנוכחי, כלומר.
משתנה הרפיון המתאים הוא חיובי. אם מוגדר לא שלילי, הרשימה תהיה גם כן
כלול מדדים n+i עבור כל משתנה החלטה xi שהוא חיובי. פּרוֹיֶקט בשימוש על ידי
lrsfourier[8] בלבד.

הפעלה מחדש V# R# B# עומק {פָּן #s or קודקוד/קרן #s} שונה ב-lrs4.0 LRS יכול להיות
הופעל מחדש מכל בסיס ידוע. החישוב ימשיך לסיום רגיל. את כל
של המידע כלול בפלט מא printcobasis אוֹפְּצִיָה. ה להזמין of
מה היא מדדים is מאוד חָשׁוּב, הזן אותם בדיוק כפי שהם מופיעים בפלט מה-
ריצה שהופסקה בעבר.

startcobasis i1i2i ... ב- 1 זה מאפשר למשתמש לציין בסיס ידוע עבור
מתחילים את החיפוש ההפוך. i1i2i ... ב- 1 היא רשימה של אי השוויון (עבור
H-representation) או קודקודים/קרניים (עבור ייצוג V) המגדירים קו-בסיס. אם זה
לא חוקי, או שהאפשרות הזו לא צוינה, LRS ימצא בסיס התחלתי משלו. ה
עץ החיפוש ההפוך נחתך (גזם) בכל פעם שנתקל בקודקוד חדש. הערה: זה
מציין בהכרח מייצר את קבוצת כל הקודקודים הסמוכים לקודקוד האופטימלי ב
הפוליהדרון, אלא רק תת-קבוצה מהם.

מִלוּלִיהדפס מידע קצת יותר מפורט על הריצה.

כֶּרֶך // ייצוג V בלבד // חישוב נפח - ראה סעיף תכולה חישוב.[9]

voronoi // ייצוג V בלבד - מקום מיד לאחר הצהרת סוף // מחשב
דיאגרמת Voronoi - ראה סעיף וורונוי דיאגרמות.[10]

אורים

1. דף שאלות נפוצות
http://www.ifor.math.ethz.ch/staff/fukuda/polyfaq/polyfaq.html

2. CDD
http://www.cs.mcgill.ca/%7Efukuda/soft/cdd_home/cdd.html

3. לינאריות
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#לינאריות

4. כפילות פלט
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Output%20כפול

5.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Hints%20and%20Comments

6. הערכה.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Estimation

7. תכנות לינארי
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linear%20Programming

8. lrsfourier
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#fourier

9. חישוב נפח.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20Computation

10. דיאגרמות וורונו.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Voronoi%20דיאגרמות

השתמש ב-lrsfourier באינטרנט באמצעות שירותי onworks.net