Package google.research.optimization.v1.mathopt

אינדקס

BasisProto

אפיון קומבינטורי לפתרון לתוכנית לינארית.

השיטה החד-כיוונית לפתרון תוכניות ליניאריות תמיד מחזירה "פתרון בר-ביצוע בסיסי" שניתן לתאר אותו באופן משולב באמצעות בסיס. בסיס מקצה את BasisStatusProto לכל משתנה ואילוץ לינארי.

לדוגמה, ניקח לדוגמה תבנית סטנדרטית LP: min c * x s.t. A * x = b x >= 0 שיש בו יותר משתנים מאילוצים ועם דירוג שורה מלא A.

תן n למספר המשתנים, ו-m את מספר האילוצים הלינאריים. ניתן לבנות בסיס חוקי לבעיה הזו באופן הבא: * סטטוס הבסיס של כל האילוצים יהיה 'מתוקן'. * בוחרים m משתנים כך שהעמודות של A הן בלתי תלויות באופן לינארי ומקצים את הסטטוס BASIC. * הקצה את הסטטוס AT_LOWER עבור n - m המשתנים הנותרים.

הפתרון הבסיסי לבסיס זה הוא הפתרון הייחודי של A * x = b, שכל המשתנים שהסטטוס שלהם הוא AT_LOWER קבועים בגבולות הנמוכים שלהם (כל אפס). הפתרון שמתקבל נקרא פתרון בר-ביצוע בסיסי אם הוא עונה גם על x >= 0.

שדות
constraint_status

SparseBasisStatusVector

סטטוס בסיס האילוץ.

דרישות: * Restrict_status.ids שווה ל-linConstraints.ids.
variable_status

SparseBasisStatusVector

סטטוס בסיס משתנה.

דרישות: * האילוץ 'אילוץ_status.ids' שווה ל-VariablesProto.ids.
basic_dual_feasibility

SolutionStatusProto

זוהי תכונה מתקדמת שבה משתמשת MathOpt כדי לאפיין את ההיתכנות של פתרונות LP לא אופטימליים (הסטטוס של פתרונות אופטימליים תמיד יהיה SOLUTION_STATUS_FEASIBLE).

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

אם אתם מספקים בסיס התחלתי דרך ModelSolveParametersProto.first_basis, המערכת תתעלם מהערך הזה. היא רלוונטית רק לבסיס שהוחזר על ידי SolutionProto.basis.

BasisStatusProto

הסטטוס של משתנה/אילוץ על בסיס LP.

טיפוסים בני מנייה (enums)
BASIS_STATUS_UNSPECIFIED ערך שומר שמייצג 'אין סטטוס'.
BASIS_STATUS_FREE המשתנה/האילוץ הוא חופשי (אין לו גבולות מוגבלים).
BASIS_STATUS_AT_LOWER_BOUND המשתנה/האילוץ נמצא בגבול התחתון שלו (שחייב להיות סופי).
BASIS_STATUS_AT_UPPER_BOUND המשתנה/האילוץ נמצא בגבול העליון שלו (שחייב להיות סופי).
BASIS_STATUS_FIXED_VALUE למשתנה/לאילוץ יש גבול עליון ותחתון זהה.
BASIS_STATUS_BASIC המשתנה/האילוץ הוא בסיסי.

DualRayProto

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

לדוגמה, ניקח לדוגמה את זוג התוכניות הלינאריות הכפולות הראשוניות: (Primal) (Dual) min c * x max b * y s.t. A * x >= b s.t. y * A + r = c x >= 0 y, r >= 0. הקרן הכפולה היא הצמד (y, r) שעומד בתנאים: b * y > 0 y * A + r = 0 y, r >= 0 חשוב לשים לב שהוספת הכפולה החיובית של (y, r) לפתרון ההתכלית הכפולה שומרת על ההיתכנות הכפולה ומשפרת את התכלית (ההוכחה לכך היא משימה לא מוגבלת). השימוש בקרני הכפולות מוכיח גם שהבעיה הראשונית היא בלתי מעשית.

בהודעה DualRay למטה, y הוא dual_values ו-r הוא מופחת_costs.

שדות
dual_values

SparseDoubleVectorProto

דרישות: * dual_values.ids הם רכיבים של לינאריConstraints.ids. * Dual_values.values חייבים להיות סופיים.
reduced_costs

SparseDoubleVectorProto

דרישות: * low_costs.ids הם אלמנטים של VariablesProto.ids. * below_costs.values חייבים להיות סופיים.

DualSolutionProto

פתרון לכפול של בעיית אופטימיזציה.

לדוגמה, ניקח לדוגמה את זוג התוכניות הלינאריות הכפולות הראשוניות: (Primal) (Dual) min c * x max b * y s.t. A * x >= b s.t. y * A + r = c x >= 0 y, r >= 0. הפתרון הכפול הוא הצמד (y, r). זה בר ביצוע אם הוא עומד במגבלות של (Dual) שלמעלה.

בהודעה הבאה, y הוא ערך כפול, r הוא ערך מופחת ו-b * y הוא ערך אובייקטיבי.

שדות
dual_values

SparseDoubleVectorProto

דרישות: * dual_values.ids הם רכיבים של לינאריConstraints.ids. * Dual_values.values חייבים להיות סופיים.
reduced_costs

SparseDoubleVectorProto

דרישות: * low_costs.ids הם אלמנטים של VariablesProto.ids. * below_costs.values חייבים להיות סופיים.
feasibility_status

SolutionStatusProto

סטטוס ההיתכנות של הפתרון לפי הפותר הבסיסי.
objective_value

double

EmphasisProto

רמת המאמץ שהוחלה על משימה אופציונלית בזמן פתרון (יש לעיין ב-SolveParametersProto לשימוש).

ההדגשה משמשת להגדרת תכונת פתרון באופן הבא: * אם הפותר לא תומך בתכונה, רק UNSPECIFIED תמיד יהיה תקף, כל הגדרה אחרת תהיה בדרך כלל שגיאת ארגומנט לא חוקית (חלק מהפותרים עשויים גם לקבל את האפשרות 'מושבת'). * אם הפותר תומך בתכונה: - כשהאפשרות מוגדרת ל-UNSPECIFIED, ייעשה שימוש בברירת המחדל הבסיסית. - אם לא ניתן להשבית את התכונה, הכיתוב 'כבוי' יחזיר הודעת שגיאה. - אם התכונה מופעלת כברירת מחדל, ברירת המחדל של הפותר ממופה בדרך כלל ל-MEDIUM. - אם התכונה נתמכת, הערכים LOW, MEDIUM, גבוה ו-VERY high אף פעם לא יספקו שגיאה, והם ימופו לפי ההתאמה הטובה ביותר שלהם.

טיפוסים בני מנייה (enums)
EMPHASIS_UNSPECIFIED
EMPHASIS_OFF
EMPHASIS_LOW
EMPHASIS_MEDIUM
EMPHASIS_HIGH
EMPHASIS_VERY_HIGH

FeasibilityStatusProto

סטטוס ההיתכנות של הבעיה כפי שנתבע על ידי הפותר (פותר אינו נדרש להחזיר אישור עבור התביעה).

טיפוסים בני מנייה (enums)
FEASIBILITY_STATUS_UNSPECIFIED ערך שומר שמייצג 'אין סטטוס'.
FEASIBILITY_STATUS_UNDETERMINED הפותר לא טוען לסטטוס.
FEASIBILITY_STATUS_FEASIBLE המפתח טוען שהבעיה אפשרית.
FEASIBILITY_STATUS_INFEASIBLE פותר טוען שהבעיה בלתי אפשרית.

IndicatorConstraintProto

נתונים שמייצגים אילוץ של מדד יחיד בצורת: Variable(indicator_id) = (activate_on_zero ? 0 : 1) <!-- below_bound <= ביטוי <= עליון_bound.

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

שדות
activate_on_zero

bool

אם True, אז אם משתנה המדד מקבל את הערך 0, האילוץ המשתמע חייב להחזיק. אחרת, אם משתנה המדד מקבל ערך 1, האילוץ המשתמע חייב להישאר בתוקף.
expression

SparseDoubleVectorProto

חייב להיות ביטוי לינארי חוקי ביחס למודל המכיל: * כל התנאים שצוינו ב-SparseDoubleVectorProto, * כל הרכיבים של expression.values חייבים להיות סופיים, * expression.ids הם קבוצת משנה של VariablesProto.ids.
lower_bound

double

חייב להיות ערך בטווח [ -inf, inf); לא יכול להיות NaN.
upper_bound

double

חייב להיות ערך ב-(-inf, inf]; לא יכול להיות NaN.
name

string

ייתכן שלהודעות ההורה יהיו דרישות ייחודיות בשדה הזה. למשל, ניתן לראות את ModelProto.indicator_constraints ואת IndicatorConstraintUpdatesProto.new_constraints.
indicator_id

int64

מזהה שתואם למשתנה בינארי, או לא מוגדר. אם המדיניות לא מוגדרת, המערכת תתעלם מהאילוץ של האינדיקטור. אם היא מוגדרת, אנחנו דורשים: * VariablesProto.integers[indicator_id] = true, * VariablesProto.lower_bounds[indicator_id] >= 0, * VariablesProto.upper_bounds[indicator_id] <= 1. התנאים האלה לא אומתו על ידי MathOpt, אבל אם לא מתקיימים התנאים האלה, הפותר יחזיר שגיאה לאחר הפתרון.

LPAlgorithmProto

בחירת אלגוריתם לפתרון תוכניות ליניאריות.

טיפוסים בני מנייה (enums)
LP_ALGORITHM_UNSPECIFIED
LP_ALGORITHM_PRIMAL_SIMPLEX השיטה (ראשית) חד-כיוונית. בדרך כלל יכולות לספק פתרונות ראשוניים וכפולים, קרניים ראשוניות/כפולות על בעיות ראשוניות/כפולות, ובסיס.
LP_ALGORITHM_DUAL_SIMPLEX השיטה הכפולה חד-כיוונית. בדרך כלל יכולות לספק פתרונות ראשוניים וכפולים, קרניים ראשוניות/כפולות על בעיות ראשוניות/כפולות, ובסיס.
LP_ALGORITHM_BARRIER שיטת המחסום, שנקראת גם שיטת נקודה פנימית (IPM). לרוב יכול לתת גם פתרונות ראשוניים וגם פתרונות כפולים. הטמעות מסוימות יכולות גם להפיק קרניים בבעיות לא תקינות או בלתי מעשיות. לא ניתן בסיס, אלא אם הפותר הבסיסי מבצע "מעבר קרוסאובר" ומסתיים בביטוי חד-כיווני.
LP_ALGORITHM_FIRST_ORDER אלגוריתם שמבוסס על שיטה מסדר ראשון. בדרך כלל הם יפיקו פתרונות ראשוניים וכפולים, ואולי גם אישורים של יכולת ראשונית ו/או כפולה. שיטות מסדר ראשון בדרך כלל יספקו פתרונות ברמת דיוק נמוכה יותר, ולכן על המשתמשים להגדיר פרמטרים של איכות פתרון (למשל, סבילות) ולאמת את הפתרונות.

LimitProto

כאשר פונקציית Solve() מפסיקה מוקדם עם FinishReasonProto FEASIBLE או NO_SOLUTION_FOUND, המגבלה הספציפית שהתקבלה.

טיפוסים בני מנייה (enums)
LIMIT_UNSPECIFIED משמש כערך אפסי במקרים שבהם אנחנו מסיימים את השימוש ללא הגבלה (למשל, QUERYINATION_REASON_OPTIMAL).
LIMIT_UNDETERMINED הפותר הבסיסי לא חושף את המגבלה שכבר הגיעה למגבלה.
LIMIT_ITERATION אלגוריתם איטרטיבי הופסק אחרי ביצוע מספר איטרציות מקסימלי (למשל, איטרציות חד-פעמיות או מחסום).
LIMIT_TIME האלגוריתם הופסק לאחר זמן חישוב שצוין על ידי המשתמש.
LIMIT_NODE אלגוריתם של הסתעפות ושיוך הופסק כי הוא בחן את מספר הצמתים המקסימלי בעץ ההסתעפות.
LIMIT_SOLUTION האלגוריתם הפסיק לפעול כי הוא מצא את מספר הפתרונות הנדרש. משתמשים בה לעיתים קרובות ב-MIP כדי לגרום לפותר להחזיר את הפתרון האפשרי הראשון שהוא נתקל בו.
LIMIT_MEMORY האלגוריתם הפסיק לפעול כי הזיכרון שלו אזל.
LIMIT_CUTOFF הפותר הופעל עם סף (למשל, SolveParameters.cutoff_limit הוגדר) לגבי המטרה, במצב שמציין שהמשתמש לא היה מעוניין בפתרון גרוע יותר מהמועד האחרון, והפותר הגיע למסקנה שאין פתרונות שטובים לפחות כמו המועד האחרון. לרוב לא מסופק מידע נוסף על פתרון.
LIMIT_OBJECTIVE האלגוריתם הפסיק לפעול כי הוא מצא פתרון או גבול שהוא טוב יותר מהמגבלה שהוגדרה על ידי המשתמש (פרטים נוספים זמינים ב-SolveParameters.objective_limit ו-SolveParameters.best_bound_limit).
LIMIT_NORM האלגוריתם הפסיק לפעול כי הנורמה של חזרה נעשתה גדולה מדי.
LIMIT_INTERRUPTED האלגוריתם הופסק עקב אות הפרעה או בקשת הפרעה של משתמש.
LIMIT_SLOW_PROGRESS האלגוריתם הפסיק לפעול כי הוא לא הצליח להמשיך להתקדם במציאת הפתרון.
LIMIT_OTHER

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

FinishProto.detail עשוי להכיל מידע נוסף על המגבלה.

LinearConstraintsProto

כפי שנעשה בהמשך, אנחנו מגדירים "#לינארי אילוצים" = size(לינאריConstraintsProto.ids).

שדות
ids[]

int64

חייב להיות מספר לא שלילי ולהיות במגמת עלייה. לא ניתן להשתמש בערך המקסימלי(int64).
lower_bounds[]

double

האורך צריך להיות שווה ל- #לינארי, הערכים בטווח [-inf, inf).
upper_bounds[]

double

האורך צריך להיות שווה ל- #לינארי אילוצים, והערכים ב-(-inf, inf].
names[]

string

אם הפרמטר לא מוגדר, ההנחה היא שכל המחרוזות הריקות. אחרת, האורך שלו צריך להיות שווה ל- #לינארי אילוצים.

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

LinearExpressionProto

ייצוג מועט של ביטוי לינארי (סכום משוקלל של משתנים, עם קיזוז קבוע).

שדות
ids[]

int64

המזהים של משתנים. יש למיין (בסדר עולה) כאשר כל הרכיבים ייחודיים.
coefficients[]

double

חייבים להיות באורך זהה למזהים. הערכים חייבים להיות סופיים, ולא יכולים להיות NaN.
offset

double

חייב להיות סופי ולא יכול להיות NaN.

ModelProto

בעיית אופטימיזציה. MathOpt תומך ב: - משתני החלטה רציפים ומספרים שלמים עם גבולות סופיים אופציונליים. - יעדים לינאריים וריבועיים (יעדים יחידים או מרובים), ממוזערים או מוגדלים. - מספר סוגי אילוצים, כולל: * אילוצים לינאריים * אילוצים ריבועיים * אילוצים בקונוס מסדר שני * אילוצים לוגיים > אילוצים מסוג חירום1 ו-SOS2 > אילוצי אינדיקטור

כברירת מחדל, האילוצים מיוצגים במפות "id-to-data". עם זאת, אנחנו מייצגים מגבלות לינאריות בפורמט יעיל יותר של "struct-of-arrays".

שדות
name

string
variables

VariablesProto
objective

ObjectiveProto

המטרה העיקרית של המודל.
auxiliary_objectives

map<int64, ObjectiveProto>

יעדי עזר לשימוש במודלים מרובי מטרות.

מזהים של מפתחות מפה חייבים להיות באותיות [0, max(int64)). כל עדיפות, וכל שם שאינו ריק, חייבים להיות ייחודיים ונפרדים מה-objective הראשי.
linear_constraints

LinearConstraintsProto
linear_constraint_matrix

SparseDoubleMatrixProto

מקדמי המשתנים של האילוצים הליניאריים.

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

דרישות: * קווים לינאריים_constraint_matrix.row_id הם רכיבים של לינארי_constraints.id. * לינארי_constraint_matrix.column_id הם אלמנטים של משתנים. * ערכי המטריצה שלא צוינו הם אפס. * לינארי_constraint_matrix.values חייבים להיות סופיים.
quadratic_constraints

map<int64, QuadraticConstraintProto>

מגבלות ריבועיות במודל.
second_order_cone_constraints

map<int64, SecondOrderConeConstraintProto>

אילוצים של חרוטים מסדר שני במודל.
sos1_constraints

map<int64, SosConstraintProto>

אילוצים מסוג חירום1 במודל, שמגבילים את הערך של expression אחד לכל היותר להיות שונה מאפס. הרשומות האופציונליות weights הן פרטי יישום שמשמשים את הפותר כדי (בתקווה) להתמזג מהר יותר. בפירוט רב יותר, יכול להיות שהפותרים ישתמשו (או לא) במשקלים האלה כדי לבחור החלטות הסתעפות שיוצרות צמתים "מאוזן" ברמת הצאצא.
sos2_constraints

map<int64, SosConstraintProto>

אילוצים מסוג SMB2 במודל, שמגבילים את האפשרות של שתי רשומות לכל היותר של expression להיות לא אפס, ועליהן להיות סמוכות לסדר שלהן. אם לא תספקו ערכי weights, הסדר הזה יהיה הסדר הלינארי שלהם ברשימה expressions. אם יוצגו ערכי weights, הסדר נלקח ביחס לערכים האלה בסדר עולה.
indicator_constraints

map<int64, IndicatorConstraintProto>

אילוצים של אינדיקטורים במודל, שאוכפים אותם, אם "משתנה אינדיקטור" בינארי מוגדר ל-1, אז "אילוץ משתמע" חייב להתקיים.

ModelSolveParametersProto

שדות
variable_values_filter

SparseVectorFilterProto

מסנן שמוחל על כל הקונטיינרים הדלילים שהוחזרו באמצעות משתנים ב-PrimalSolutionProto וב-PrimalRayProto (PrimalSolutionProto.variable_values, PrimalRayProto.variable_values).

דרישות: * filter_ids הם רכיבים של VariablesProto.ids.
dual_values_filter

SparseVectorFilterProto

מסנן שמוחל על כל הקונטיינרים הדלילים שהוחזרו, שמקשים על בסיס אילוצים לינאריים ב-DualSolutionProto וב-DualRay (DualSolutionProto.dual_values, DualRay.dual_values).

דרישות: * filter_id (מזהים) הם רכיבים של LCtraints.ids.
reduced_costs_filter

SparseVectorFilterProto

מסנן שמוחל על כל הקונטיינרים האיטיים שהוחזרו, שקודדו על ידי משתנים ב-DualSolutionProto וב-DualRay (DualSolutionProto.reduced_costs, DualRay.reduced_costs).

דרישות: * filter_ids הם רכיבים של VariablesProto.ids.
initial_basis

BasisProto

בסיס ראשוני אופציונלי לפותרי בעיות LP חד-פעמיות במצב ביניים (warm start). אם היא מוגדרת, היא צפויה להיות תקפה לפי ValidateBasis בvalidators/solution_validator.h עבור ModelSummary הנוכחי.
solution_hints[]

SolutionHintProto

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

SparseInt32VectorProto

אפשרויות עדיפות להסתעפות. משתנים עם ערכים גבוהים יותר יסתעפו קודם. משתנים שלא הוגדרו עבורם עדיפויות מקבלים את עדיפות ברירת המחדל של הפותר (בדרך כלל אפס).

דרישות: * branching_priorities.values חייבים להיות סופיים. * branching_priorities.id חייב להיות רכיבים של VariablesProto.ids.

ObjectiveBoundsProto

גבול של ערך המטרה האופטימלי.

שדות
primal_bound

double

הפותר טוען שהערך האופטימלי שווה או טוב יותר (קטן יותר למזעור וגדול יותר לאופטימיזציה) מאשר primal_bound בסבילות של היתכנות ראשוני של המפותרים (ראו אזהרה בהמשך): * primal_bound הוא טריוויאלי (+inf for minimization ו-inf maximization) כאשר הפותר לא טוען שיש לו גבול כזה. * primal_bound יכול להיות קרוב יותר לערך האופטימלי מהמטרה של הפתרון הראשוני הטוב ביותר האפשרי. באופן ספציפי, primal_bound עשוי להיות לא טריוויאלי גם אם לא מוחזרים פתרונות ראשוניים אפשריים. אזהרה: הטענה המדויקת היא שקיים פתרון ראשוני: * הוא בר-ביצוע ממוספר (כלומר, עד לסבילות המפותרים), ו-* יש לו ערך אובייקטיבי primal_bound. הפתרון המספרי הזה יכול להיות לא בר-ביצוע, ובמקרה כזה primal_bound יכול להיות טוב יותר מהערך האופטימלי. תרגום של סבילות היתכנות ראשוניות לסבילות ב-primal_bound הוא לא טריוויאלי, במיוחד כאשר סבילות ההיתכנות גדולה יחסית (למשל, בעת פתרון באמצעות PDLP).
dual_bound

double

הפותר טוען שהערך האופטימלי שווה או גרוע יותר (גדול למזעור וקטן יותר לאופטימיזציה) מאשר סבילות של Dual_bound למעלה למתלים של היתכנות כפולה (ראו אזהרה בהמשך): * dual_bound הוא טריוויאלי (-inf for minimization ו-+inf maximization) כשהפותר לא טוען שיש לו גבול כזה. בדומה ל-primal_bound, המצב הזה עשוי לקרות עבור חלק מהפותרים גם כשחוזרים למצב מיטבי. פתרונות MIP בדרך כלל מדווחים על גבול, גם אם הוא לא מדויק. * במקרה של בעיות רציפות, Dual_bound יכול להיות קרוב יותר לערך האופטימלי מאשר המטרה של הפתרון הכפול הטוב ביותר האפשרי. עבור MIP, אחד מהערכים הלא-טריוויאליים הראשונים של dual_bound הוא בדרך כלל הערך האופטימלי של הרגיעה LP של ה-MIP. * Dual_bound צריך להיות טוב יותר (קטן יותר למינימום וגדול יותר לאופטימיזציה) מאשר primal_bound עד לסבילות של הפותרים (ראו אזהרה בהמשך). אזהרה: * במקרה של בעיות מתמשכות, הטענה המדויקת היא שקיים פתרון כפול אשר: * הוא בר-ביצוע ממוספר (כלומר, עד לסבילות של המפתרות), ו-* יש ערך אובייקטיבי מסוג dual_bound. הפתרון המספרי הזה יכול להיות לא בר-ביצוע, ובמקרה כזה dual_bound יכול להיות גרוע לחלוטין מהערך האופטימלי ו-primal_bound. בדומה למקרה הפרימלי, תרגום של סבילות של היתכנות כפולה לסובלות ב-Double_bound הוא לא טריוויאלי, במיוחד כאשר סבילות ההיתכנות גדולה יחסית. עם זאת, חלק מהפותרים מספקים גרסה מתוקנת של Dual_bound שיכולה להיות בטוחה יותר מבחינה מספרית. ניתן לגשת לגרסה המתוקנת הזו דרך הפלט הספציפי של הפותר (למשל, עבור PDLP, pdlp_output.convergence_information. corrected_dual_objective). * עבור פתרוןי MIP, ייתכן ש-Dual_bound יהיה משויך לפתרון כפול לצורך רגיעה מתמשכת מסוימת (למשל, רגיעה בעזרת LP), אבל לרוב מדובר בתוצאה מורכבת של ביצוע הפותרים, ולרוב היא לא מדויקת יותר מהגבולות שמדווחים על ידי פותחי LP.

ObjectiveProto

שדות
maximize

bool

false הוא מזעור, TRUE הוא מקסימום
offset

double

חייב להיות סופי ולא NaN.
linear_coefficients

SparseDoubleVectorProto

מונחים אובייקטיביים שהם לינאריים במשתני ההחלטה.

דרישות: * קווים לינאריים_מקודמים הם אלמנטים של VariablesProto.ids. * הערך של VariablesProto שלא צוין תואם לאפס. * לינארי_cofactors.values חייב להיות סופי. * לינארי_coPromotes.values יכול להיות אפס, אבל הדבר פשוט מבזבז מקום.
quadratic_coefficients

SparseDoubleMatrixProto

מונחים אובייקטיביים שהם ריבועיים במשתני ההחלטה.

דרישות בנוסף לדרישות שבהודעות SparseDoubleMatrixProto: * כל רכיב של quadratic_coadmobs.row_ids וכל רכיב של quadratic_co לאימותs.column_ids חייב להיות רכיב של VariablesProto.ids. * המטריצה צריכה להיות משולשת עליונה: לכל i, quadratic_cos.row_ids[i] <= quadratic_cos.column_ids[i].

הערות: * למונחים שלא אוחסנו באופן מפורש יש מקדם אפס. * אלמנטים של quadratic_coPromotes.coPromotes יכולים להיות אפס, אבל הם פשוט מבזבזים מקום.
name

string

ייתכן שלהודעות ההורה יהיו דרישות ייחודיות בשדה הזה. למשל, אפשר לעיין ב-ModelProto.objectives וב-AuxiliaryObjectivesUpdatesProto.new_objectives.
priority

int64

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

PrimalRayProto

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

דוגמה: נבחן תוכנית לינארית פשוטה: min c * x s.t. A * x >= b x >= 0 קרנית ראשוניות הן x שעונה על הצרכים הבאים: c * x < 0 A * x >= 0 x >= 0 נראה כאילו הוא נותן פתרון אפשרי, כל ערך חיובי שהוא עדיין קיימא, וכל ערך חיובי שהוא עדיין קיימא. קרן ראשונית מוכיחה גם שבעיית האופטימיזציה הכפולה לא ניתנת לביצוע.

בהודעה PrimalRay שבהמשך, הפרמטר variable_values הוא x.

שדות
variable_values

SparseDoubleVectorProto

דרישות: * variable_values.ids הם אלמנטים של VariablesProto.ids. * variable_values.values חייב להיות סופי.

PrimalSolutionProto

פתרון לבעיית אופטימיזציה.

דוגמה לתוכנית לינארית פשוטה: min c * x s.t. A * x >= b x >= 0. פתרון ראשוני הוא הקצאת ערכים ל-x. היא אפשרית אם היא עומדת ב-A * x >= b ו-x >= 0 מלמעלה. בהודעה של PrimalSolutionProto שבהמשך, המשתנה_values הוא x ו-destination_value הוא c * x.

שדות
variable_values

SparseDoubleVectorProto

דרישות: * variable_values.ids הם אלמנטים של VariablesProto.ids. * variable_values.values חייב להיות סופי.
objective_value

double

ערך אובייקטיבי כפי שחושב על ידי הפותר הבסיסי. אינו יכול להיות אינסופי או NaN.
auxiliary_objective_values

map<int64, double>

ערכי יעד עזר כפי שמחושבים על ידי הפותר הבסיסי. המפתחות חייבים להיות מזהים תקפים של מטרת עזר. הערכים לא יכולים להיות אינסופיים או NN.
feasibility_status

SolutionStatusProto

סטטוס ההיתכנות של הפתרון לפי הפותר הבסיסי.

ProblemStatusProto

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

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

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

שדות
primal_status

FeasibilityStatusProto

הסטטוס של הבעיה הראשונית.
dual_status

FeasibilityStatusProto

הסטטוס של הבעיה הכפולה (או עבור הכפילות של רגיעה מתמשכת).
primal_or_dual_infeasible

bool

אם הבעיה היא true, הפותר טוען שהבעיה הראשונית או הכפולה אינה ניתנת לביצוע, אבל הוא לא יודע איזו מהן (או אם שתיהן לא ניתנות לביצוע). הערך יכול להיות true רק כאשר primal_problem_status = dual_problem_status = kUndetermined. המידע הנוסף הזה נדרש לעיתים קרובות כשעיבוד מראש קובע שאין פתרון אופטימלי לבעיה (אבל לא יכול לקבוע אם הסיבה היא חוסר היתכנות, חוסר גבולות או שניהם).

QuadraticConstraintProto

אילוץ ריבועי יחיד בצורה הזו: lb <= sum{לינארי_terms} + sum{quadratic_terms} <= ub.

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

שדות
linear_terms

SparseDoubleVectorProto

מונחים לינאריים במשתני ההחלטה.

בנוסף לדרישות לגבי הודעות SparseDoubleVectorProto, אנחנו דורשים שהערכים הבאים יהיו: * ירים_terms.ids הם רכיבים של VariablesProto.ids. * לינארי_terms.values חייבים להיות סופיים ו-not-NaN.

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

SparseDoubleMatrixProto

מונחים שהם ריבועיים במשתני ההחלטה.

בנוסף לדרישות לגבי הודעות SparseDoubleMatrixProto, כל רכיב של quadratic_terms.row_id וכל רכיב של quadratic_terms.column_ids חייב להיות רכיב של VariablesProto.ids. * המטריצה צריכה להיות משולשת עליונה: לכל i, quadratic_terms.row_ids[i] <= quadratic_terms.column_ids[i].

הערות: * למונחים שלא אוחסנו באופן מפורש יש מקדם אפס. * אלמנטים של quadratic_terms.coPromotes יכולים להיות אפס, אבל זה פשוט בזבוז מקום.
lower_bound

double

הערך חייב להיות בטווח [-inf, inf) וקטן מ-upper_bound או שווה לו.
upper_bound

double

חייב להיות ערך בטווח (-inf, inf], וגדול מ-lower_bound או שווה לו.
name

string

ייתכן שלהודעות ההורה יהיו דרישות ייחודיות בשדה הזה. למשל, ניתן לעיין ב-ModelProto.quadratic_constraints ו-QadraticConstraintUpdatesProto.new_constraints.

SecondOrderConeConstraintProto

אילוץ חרוט יחיד מסדר שני מהצורה:

||arguments_to_norm||_2 <= upper_bound,

upper_bound וכל רכיב של arguments_to_norm הם ביטויים ליניאריים.

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

שדות
upper_bound

LinearExpressionProto
arguments_to_norm[]

LinearExpressionProto
name

string

ייתכן שלהודעות ההורה יהיו דרישות ייחודיות בשדה הזה. למשל, ניתן לראות את ModelProto.second_order_cone_constraints ואת SecondOrderConeConstraintUpdatesProto.new_constraints.

SolutionHintProto

פתרון מוצע להתחלה עבור הפותר.

בדרך כלל, פתרוןי MIP רוצים רק מידע ראשוני (variable_values), ואילו פתרוןי LP רוצים גם מידע ראשוני וגם מידע כפול (dual_values).

הרבה פתרונות MIP יכולים לעבוד עם: (1) פתרונות חלקיים שלא מציינים את כל המשתנים, או (2) פתרונות בלתי אפשריים. במקרים כאלה, הפותרים בדרך כלל פותרים את בעיית ה-MIP כדי להשלים/לתקן את הרמז.

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

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

שדות
variable_values

SparseDoubleVectorProto

הקצאה חלקית של ערכים למשתנים הפרימליים של הבעיה. הדרישות הבלתי-תלויות לפותר עבור הודעת המשנה הזו הן: * variable_values.ids הם רכיבים של VariablesProto.ids. * variable_values.values חייב להיות סופי.
dual_values

SparseDoubleVectorProto

הקצאה (שעשויה להיות חלקית) של ערכים למגבלות הליניאריות של הבעיה.

דרישות: * dual_values.ids הם אלמנטים של linConstraintsProto.ids. * Dual_values.values חייבים להיות סופיים.

SolutionProto

מה נכלל בפתרון תלוי בסוג הבעיה ובפותר הבעיות. הדפוסים הנפוצים הנוכחיים הם 1. פתרוןי MIP מחזירים רק פתרון ראשוני. 2. בדרך כלל, פתרוןי ה-Simplex LP מחזירים בסיס ואת הפתרונות הראשוניים והכפולים שמשויכים לבסיס הזה. 3. פתרונות רציפים אחרים בדרך כלל מחזירים פתרונות ראשוניים וכפולים שמחוברים באופן תלוי בפותר.

דרישות: * יש להגדיר שדה אחד לפחות. פתרון לא יכול להיות ריק.

שדות
primal_solution

PrimalSolutionProto
dual_solution

DualSolutionProto
basis

BasisProto

SolutionStatusProto

היתכנות של פתרון ראשוני או כפול כפי שטען הפותר.

טיפוסים בני מנייה (enums)
SOLUTION_STATUS_UNSPECIFIED ערך שומר שמייצג 'אין סטטוס'.
SOLUTION_STATUS_UNDETERMINED הפותר לא טוען לסטטוס היתכנות.
SOLUTION_STATUS_FEASIBLE הפותר טוען שהפתרון בר-ביצוע.
SOLUTION_STATUS_INFEASIBLE הפותר טוען שהפתרון אינו ישים.

SolveParametersProto

פרמטרים שמאפשרים לשלוט בפתרון יחיד.

מכילה את שני הפרמטרים המשותפים לכל הפותרים, למשל time_limit, ופרמטרים של פותר ספציפי, למשל gscip. אם הערך מוגדר גם בשדה נפוץ וגם בשדה הספציפי לפותר, המערכת משתמשת בהגדרה הספציפית לפותר.

הפרמטרים הנפוצים הם אופציונליים ולא מוגדרים, או 'טיפוסים בני מנייה (enum) עם ערך שלא צוין' מציינים שנעשה שימוש בברירת המחדל של הפותר.

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

פרמטרים התלויים במודל (למשל, הוגדרה עדיפות הסתעפות לכל משתנה) מועברים ב-ModelSolveParametersProto.

שדות
time_limit

Duration

משך הזמן המקסימלי שצריך להקדיש לפתרון הבעיה (או זמן אינסופי אם היא לא מוגדרת).

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

bool

מאפשרת להדפיס את עקבות ההטמעה של הפותר. המיקום של העקבות האלה תלוי בפותר. עבור SCIP ו-Gurobi, זו תהיה ברירת המחדל של זרמי הפלט. עבור Glop ו-CP-SAT, הפעולה הזו תבוצע LOG(INFO).

חשוב לשים לב שאם הפותר תומך בקריאה חוזרת (callback) של הודעות והמשתמש מבצע קריאה חוזרת (callback) עבורו, המערכת תתעלם מערך הפרמטר הזה ולא יודפסו עקבות.
lp_algorithm

LPAlgorithmProto

האלגוריתם לפתרון תוכנית לינארית. אם LP_ALGORITHM_UNSPECIFIED, יש להשתמש באלגוריתם ברירת המחדל של הפותר.

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

EmphasisProto

כדאי לנסות לפשט את הבעיה לפני הפעלת האלגוריתם הראשי, או לנסות להגדיר את רמת המאמץ שהוגדרה כברירת מחדל לפותר אם {/8}_UNSPECIFIED.
cuts

EmphasisProto

מאמץ להשגת הרגיעה חזקה יותר של רמת ה-LP (MIP בלבד), או רמת המאמץ שמוגדרת כברירת המחדל של הפותר אם {/8}_UNSPECIFIED.

הערה: השבתת החיתוכים עלולה למנוע אפשרות להוסיף חיתוכים ב-MIP_NODE. התנהגות זו היא ספציפית לפותר.
heuristics

EmphasisProto

מאמץ למצוא פתרונות אפשריים מעבר לאלו שהתקבלו בתהליך החיפוש המלא (MIP בלבד), או רמת המאמץ שהוגדרה כברירת מחדל של הפותר אם {/8}_UNSPECIFIED.
scaling

EmphasisProto

משקיעים מאמצים בשינוי קנה מידה של הבעיה כדי לשפר את היציבות המספרית, או את רמת המאמץ שמוגדרת כברירת המחדל של הפותר אם {/8}_UNSPECIFIED.
iteration_limit

int64

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

בדרך כלל הפתרונות נתמכים ב-LP, QP ו-MIP, אבל בפותרי MIP רואים גם את הכיתוב node_limit.
node_limit

int64

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

בדרך כלל לפותרי MIP, כדאי לעיין גם בערך iteration_limit.
cutoff_limit

double

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

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

מומלץ להשתמש בסבילות אם רוצים שיוחזרו פתרונות עם יעד השווה בדיוק לחיתוך.

כדאי לעיין במדריך למשתמש לקבלת פרטים נוספים והשוואה בין הפרמטר Best_bound_limit.
objective_limit

double

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

double

הפותר מפסיק בשלב מוקדם ברגע שמוכיח שהגבול הטוב ביותר הוא לפחות הטוב הזה, עם סיבת הסיום FEASIBLE או NO_SOLUTION_FOUND ומגביל את ObjectIVE.

כדאי לעיין במדריך למשתמש לפרטים נוספים ולהשוואה עם cutoff_limit.
solution_limit

int32

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

בדרך כלל הפותרים לא יחזירו יותר פתרונות ממגבלת הפתרונות, אבל זה לא נאכף על ידי MathOpt. מידע נוסף זמין גם ב-b/214041169.

כרגע יש תמיכה ב-Gurobi וב-SCIP, וב-CP-SAT בלבד עם ערך 1.
threads

int32

אם הוא מוגדר, הוא צריך להיות >= 1.
random_seed

int32

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

לכל הפותרים יש תפיסה של זרעים, אבל חשוב לזכור שהערכים החוקיים תלויים בפותר בפועל. - Gurobi: [0:GRB_MAXINT] (החל מתאריך Gurobi 9.0 הוא 2x10^9). - GSCIP: [0:2147483647] (שהוא MAX_INT או kint32max או 2^31-1). - גלובלי: [0:2147483647] (כמו למעלה) בכל המקרים, הפותר יקבל ערך השווה ל: MAX(0, MIN(MAX_LEGAL_VALUE_FOR_SOLVER, אירוע אקראי)).
absolute_gap_tolerance

double

סובלנות אבסולוטית מוחלטת (בעיקר) לפותרי MIP.

ה-GAP המוחלט הוא הערך המוחלט של ההבדל בין: * הערך האובייקטיבי של הפתרון האפשרי הטוב ביותר שנמצא, * הגבולות הכפולים שנוצרו על ידי החיפוש. הפותר יכול להפסיק לאחר שה-GAP המוחלט מגיע לכל היותר bolute_gap_tolerance (כאשר ערך מוגדר), ולהחזיר QUERYINATION_REASON_OPTIMAL.

אם מגדירים ערך לפרמטר הזה, הערך חייב להיות >= 0.

אפשר לעיין גם ביחס ליחסי גובה-רוחב של הפער.
relative_gap_tolerance

double

סובלנות יחסית אופטימלית (בעיקר) לפותרי MIP.

ה-GAP היחסי הוא גרסה מנורמלת של ה-GAP המוחלט (מוגדר על ידי bolute_gap_tolerance). הנירמול תלוי בפותר, למשל ה-GAP המוחלט חלקי הערך האובייקטיבי של הפתרון המעשי הטוב ביותר שנמצא.

הפותר יכול להפסיק לאחר ש-GAP היחסי מגיע לכל היותר ביחס לחוסר התאמה (יחסי) (כאשר הוא מוגדר), ולהחזיר QUERYINATION_REASON_OPTIMAL.

אם מגדירים ערך לפרמטר הזה, הערך חייב להיות >= 0.

כדאי לעיין גם בקטע 'bolute_gap_tolerance'.
solution_pool_size

int32

עדכון של עד solution_pool_size פתרונות בזמן החיפוש. באופן כללי, למאגר הפתרונות יש שתי פונקציות: (1) לפותרים שיכולים להחזיר יותר מפתרון אחד, האפשרות הזו מגבילה את מספר הפתרונות שיוחזרו. (2) חלק מהפותרים עשויים להריץ היוריסטיקה באמצעות פתרונות ממאגר הפתרונות, כך ששינוי הערך הזה עשוי להשפיע על נתיב האלגוריתם. כדי לאלץ את הפותר למלא את מאגר הפתרונות, למשל עם n הפתרונות הטובים ביותר, נדרשת הגדרה ספציפית וספציפית לפותר.

SolveResultProto

החוזה של מקרים שבהם פתרונות/קרניים ראשוניות/כפולות הוא מורכב, ראו סיום_reasons.md לתיאור מלא.

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

שדות
termination

TerminationProto

הסיבה שבגללה הפותר הפסיק לפעול.
solutions[]

SolutionProto

החוזה הכללי לגבי סדר הפתרונות שפותרים עתידיים צריכים ליישם הוא הקצאה לפי: 1. הפתרונות עם פתרון ראשוני בר-ביצוע, לפי סדר היעדים הראשוניים הטובים ביותר. 2. הפתרונות עם פתרון כפול בר-ביצוע, המסודרים לפי המטרה הכפולה הטובה ביותר (יעד כפול לא ידוע הוא במקרה הגרוע ביותר) 3. אפשר להחזיר את כל הפתרונות שנותרו בכל סדר.
primal_rays[]

PrimalRayProto

הוראות לשיפור ראשוני ללא הגבלה, או אישורים כפולים של אי היתכנות כפולה. בדרך כלל מסופק ל-EndReasonProtos UNBOUNDED ול-DUAL_INFEASIBLE
dual_rays[]

DualRayProto

הוראות של שיפור כפול ללא גבולות, או אישורים מקבילים של בלתי היתכנות ראשוניות. בדרך כלל סופק ל-FinishReasonProto INFEASIBLE.
solve_stats

SolveStatsProto

נתונים סטטיסטיים על תהליך פתרון, למשל זמן ריצה, איטרציות.

SolveStatsProto

שדות
solve_time

Duration

הזמן שחלף של שעון קיר, כפי שנמדד על ידי Mat_opt, בערך הזמן ב-Solver::Solve(). הערה: הנתון לא כולל את העבודה שמתבצעת בבניית המודל.
problem_status

ProblemStatusProto

סטטוסי היתכנות לבעיות ראשוניות וכפולות.
simplex_iterations

int64
barrier_iterations

int64
first_order_iterations

int64
node_count

int64

SolverTypeProto

הפותרים שנתמכים על ידי MathOpt.

טיפוסים בני מנייה (enums)
SOLVER_TYPE_UNSPECIFIED
SOLVER_TYPE_GSCIP

פתרון בעיות שקשורות לתוכניות של מספרים שלמים (SCIP) (צד שלישי).

תמיכה בבעיות מסוג LP, MIP ובעיות ריבועיות של מספרים שלמים לא-קמורות. עם זאת, לא מוחזרים נתונים כפולים עבור דפי נחיתה. העדפה ל-GLOP ל-LPs.
SOLVER_TYPE_GUROBI

פותר הבעיות של Gurobi (צד שלישי).

תמיכה בבעיות מסוג LP, MIP ובעיות ריבועיות של מספרים שלמים לא-קמורות. בדרך כלל זו האפשרות המהירה ביותר, אבל יש לה רישוי מיוחד.
SOLVER_TYPE_GLOP

פותר Glop של Google.

תומך ב-LP עם שיטות ראשוניות וכפולות חד-כיווניות.
SOLVER_TYPE_CP_SAT

פתרון CP-SAT של Google.

תומכת בבעיות שבהן כל המשתנים הם מספרים שלמים ומוגבלים (או משתמעים שהם אחרי presolve). תמיכה ניסיונית במדידה מחדש ובהבחנה של בעיות עם משתנים רציפים.
SOLVER_TYPE_PDLP

פתרון PDLP של Google.

תומכת בערכי LP ובמטרות ריבועיות קמורות באלכסון. משתמש בשיטות מסדר ראשון במקום בשיטות חד-כיווניות. יכול לפתור בעיות גדולות מאוד.
SOLVER_TYPE_GLPK

ערכת תכנות לינארית של GNU (GLPK) (צד שלישי).

תמיכה ב-MIP וב-LP.

בטיחות בשרשורים: GLPK משתמש באחסון מקומי בשרשור בשביל הקצאות זיכרון. כתוצאה מכך, צריך להשמיד מכונות של Solver באותו thread כפי שהן נוצרות, אחרת ה-GLPK יקרוס. נראה בסדר לקרוא ל-Solver::Solve() מ-thread אחר מזה ששימש ליצירת ה-Solver, אבל הוא לא מתועד על ידי GLPK ויש להימנע מכך.

כשפותרים LP באמצעות המפענח, מוחזרים תמיסה (והקרניים הבלתי מאוגדות) רק אם נמצא פתרון אופטימלי. אחרת לא מוחזרים כלום. לפרטים נוספים, אפשר לעיין בדף glpk-5.0/doc/glpk.pdf #40 הזמין בכתובת glpk-5.0.tar.gz.
SOLVER_TYPE_OSQP

פותר הבעיות של התוכנית המפוצלת של המפעיל (OSQP) (צד שלישי).

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

הפותר בעיות מוטמע (ECOS) (צד שלישי).

תמיכה בבעיות מסוג LP ו-SOCP. משתמש בשיטות של נקודה פנימית (מחסום).
SOLVER_TYPE_SCS

Splitting Conic Solver (SCS) (צד שלישי).

תמיכה בבעיות מסוג LP ו-SOCP. משתמשת בשיטת מסדר ראשון.
SOLVER_TYPE_HIGHS

HiGHS Solver (צד שלישי).

תמיכה בבעיות מסוג LP ו-MIP (בדיקות QP קמורות לא מיושמות).
SOLVER_TYPE_SANTORINI

הטמעת MathOpt של פותר MIP.

איטי/לא מומלץ לייצור. לא פותר LP (לא הוחזר מידע כפול).

SosConstraintProto

נתונים לייצוג של אילוץ חירום יחיד או SD2.

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

שדות
expressions[]

LinearExpressionProto

הביטויים שעליהם יש להחיל את מגבלת ה-SOS: * לכולם 1: לכל היותר רכיב אחד מקבל ערך שהוא לא אפס. * תמיכה ב-SOS2: לכל היותר שני רכיבים יכולים לקבל ערכים שונים מאפס, והם חייבים להיות סמוכים בסדר החוזר.
weights[]

double

ריק או באורך שווה לביטויים. אם השדה ריק, משקלי ברירת המחדל הם 1, 2, ... אם קיים, הערכים חייבים להיות ייחודיים.
name

string

ייתכן שלהודעות ההורה יהיו דרישות ייחודיות בשדה הזה. למשל, אפשר לעיין ב-ModelProto.sos1_constraints ו-SosConstraintUpdatesProto.new_constraints.

SparseBasisStatusVector

ייצוג דל של וקטור של סטטוסים של בסיס.

שדות
ids[]

int64

יש למיין (בסדר עולה) כאשר כל הרכיבים ייחודיים.
values[]

BasisStatusProto

חייבים להיות באורך זהה למזהים.

SparseDoubleMatrixProto

ייצוג מועט של מטריצה של זוגות.

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

שדות
row_ids[]

int64
column_ids[]

int64
coefficients[]

double

עשוי שלא להכיל NaN.

SparseDoubleVectorProto

ייצוג מועט של וקטור של זוגות.

שדות
ids[]

int64

יש למיין (בסדר עולה) כאשר כל הרכיבים ייחודיים.
values[]

double

חייבים להיות באורך זהה למזהים. עשוי שלא להכיל NaN.

SparseInt32VectorProto

ייצוג חלקי של וקטור של int.

שדות
ids[]

int64

צריך למיין (בסדר עולה) כך שכל הרכיבים יהיו ייחודיים.
values[]

int32

חייבים להיות באורך זהה למזהים.

SparseVectorFilterProto

הודעה זו מאפשרת להריץ שאילתה/להגדיר חלקים ספציפיים של SparseXxxxVector. התנהגות ברירת המחדל היא לא לסנן החוצה. אחת הדרכים הנפוצות היא להריץ שאילתות רק על חלקים של פתרונות (רק ערכים שאינם אפס ו/או רק קבוצה של ערכי משתנה שנבחרו ידנית).

שדות
skip_zero_values

bool

עבור SparseBoolVectorProto הערך "אפס" הוא false.
filter_by_ids

bool

אם הערך הוא True, המערכת תחזיר רק את הערכים שתואמים למזהים המפורטים ב-FILTER_id.
filtered_ids[]

int64

רשימת המזהים לשימוש כאשר filter_by_ids הוא TRUE. הערך צריך להיות ריק אם filter_by_ids אינו FALSE. הערה: אם השדה ריק וה-filter_by_ids נכון, הכוונה היא שאינך רוצה לקבל שום מידע בתוצאה.

TerminationProto

כל המידע לגבי הסיבה שבגללה הסתיימה קריאה ל-Solve() .

שדות
reason

TerminationReasonProto

מידע נוסף ב-limit כשהערך הוא termINATION_REASON_FEASIBLE או QUERYINATION_REASON_NO_SOLUTION_FOUND, ניתן למצוא בlimit.
limit

LimitProto

הוא LIMIT_UNSPECIFIED אלא אם הסיבה היא QUERYINATION_REASON_FEASIBLE או QUERYINATION_REASON_NO_SOLUTION_FOUND. לא כל הפותרים יכולים תמיד לקבוע את המגבלה שגרמה לסגירת החשבון. אם לא ניתן לקבוע מהי הסיבה, המערכת משתמשת ב-LIMIT_UNDE הקשורותINED.
detail

string

בדרך כלל מידע ספציפי נוסף לפותר הבעיות לגבי סגירת החשבון.
problem_status

ProblemStatusProto

סטטוסי היתכנות לבעיות ראשוניות וכפולות. החל מ-18 ביולי 2023 ייתכן שההודעה הזו לא תופיע. אם הפרמטר לא נמצא, ניתן למצוא את הבעיה_status ב-SolveResultProto.solve_stats.
objective_bounds

ObjectiveBoundsProto

גבול של ערך המטרה האופטימלי. החל מ-18 ביולי 2023 ייתכן שההודעה הזו לא תופיע. אם חסרים נתונים, object_bounds.primal_bound יימצא ב-SolveResultProto.solve.stats.best_primal_bound ו-Object_bounds.dual_bound יכולים למצוא את SolveResultProto.solve.stats.best_dual_bound

TerminationReasonProto

הסיבה לסיום קריאה ל-Solve() .

טיפוסים בני מנייה (enums)
TERMINATION_REASON_UNSPECIFIED
TERMINATION_REASON_OPTIMAL נמצא פתרון אופטימלי לכאורה (עד סבילות מספרית).
TERMINATION_REASON_INFEASIBLE לבעיה הראשונית אין פתרונות אפשריים.
TERMINATION_REASON_UNBOUNDED הבעיה הפרימלית היא מעשית, ואפשר למצוא פתרונות טובים ושרירותיים לאורך קרן ראשונית.
TERMINATION_REASON_INFEASIBLE_OR_UNBOUNDED הבעיה הראשונית היא בלתי מעשית או בלתי מוגבלת. ייתכן שיהיו פרטים נוספים על סטטוס הבעיה ב-resolve_stats.problem_status. שים לב, ניתן למפות כאן את הסטטוס המלא של Gurobi.
TERMINATION_REASON_IMPRECISE

הבעיה טופלה בהתאם לאחד מהקריטריונים המפורטים למעלה ('אופטימלי', 'לא בר-ביצוע', 'לא מוגבל' או 'InfeasibleOrUnbounded), אבל אין עמידה בתנאים. קיימים מספר פתרונות/קרניים ראשוניות/כפולות, אבל ייתכן שהם יהיו מעט בלתי אפשריים. לחלופין, אם הבעיה הייתה כמעט אופטימלית, ייתכן שיהיו פערים בין המטרה הטובה ביותר של הפתרון הטוב ביותר לבין היעד המתאים ביותר.

המשתמשים עדיין יכולים להריץ שאילתות על פתרונות/קרניים ראשוניים/כפולים ועל נתונים סטטיסטיים של פתרונות, אבל הם אחראים לטפל בחוסר הדיוק המספרי.
TERMINATION_REASON_FEASIBLE האופטימיזציה הגיעה למגבלה מסוימת והוחזר פתרון ראשוני בר-ביצוע. לקבלת תיאור מפורט של סוג המגבלה שהגעת אליה, ראה SolveResultProto.limit_detail.
TERMINATION_REASON_NO_SOLUTION_FOUND האופטימיזציה הגיעה למגבלה מסוימת ולא מצאה פתרון ראשוני בר ביצוע. לקבלת תיאור מפורט של סוג המגבלה שהגעת אליה, ראה SolveResultProto.limit_detail.
TERMINATION_REASON_NUMERICAL_ERROR האלגוריתם הופסק עקב שגיאה מספרית שלא ניתן לשחזר. אין מידע זמין על הפתרון.
TERMINATION_REASON_OTHER_ERROR האלגוריתם הופסק עקב שגיאה שלא נכללת באחד מהסטטוסים שהוגדרו למעלה. אין מידע זמין על הפתרון.

VariablesProto

כפי שנעשה בהמשך, אנחנו מגדירים "#variables" = size(VariablesProto.ids).

שדות
ids[]

int64

חייב להיות מספר לא שלילי ולהיות במגמת עלייה. לא ניתן להשתמש בערך המקסימלי(int64).
lower_bounds[]

double

האורך צריך להיות שווה ל- #variable, הערכים ב-[-inf, inf].
upper_bounds[]

double

האורך צריך להיות שווה ל- #variables, הערכים ב-(-inf, inf].
integers[]

bool

האורך צריך להיות שווה ל- #variables. במשתנים רציפים, הערך יכול להיות FALSE במשתנים עם מספרים שלמים.
names[]

string

אם הפרמטר לא מוגדר, ההנחה היא שכל המחרוזות הריקות. אחרת, האורך צריך להיות שווה ל- #variables.

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