Package google.research.optimization.v1.mathopt

فهرست مطالب

BasisProto

یک توصیف ترکیبی برای یک راه حل برای یک برنامه خطی.

روش سیمپلکس برای حل برنامه‌های خطی همیشه یک «راه‌حل عملی اساسی» را برمی‌گرداند که می‌توان آن را به‌صورت ترکیبی با یک پایه توصیف کرد. یک پایه یک BasisStatusProto را برای هر متغیر و محدودیت خطی اختصاص می دهد.

به عنوان مثال یک فرم استاندارد LP را در نظر بگیرید: min c * x st A * x = bx >= 0 که دارای متغیرهای بیشتری نسبت به محدودیت ها و دارای ردیف کامل A است.

فرض کنید n تعداد متغیرها و m تعداد قیود خطی باشد. یک مبنای معتبر برای این مشکل می‌تواند به صورت زیر ساخته شود: * همه محدودیت‌ها وضعیت پایه ثابت دارند. * m متغیرها را طوری انتخاب کنید که ستون های A به صورت خطی مستقل باشند و وضعیت BASIC را تعیین کنید. * وضعیت AT_LOWER را برای متغیرهای n - m باقی مانده اختصاص دهید.

راه‌حل اصلی برای این مبنا، راه‌حل منحصربه‌فرد A * x = b است که همه متغیرها با وضعیت AT_LOWER به کران‌های پایین‌شان (همه صفر) ثابت هستند. راه حل به دست آمده در صورتی که x>= 0 را نیز برآورده کند، راه حل اساسی عملی نامیده می شود.

زمینه های
constraint_status

SparseBasisStatusVector

وضعیت پایه محدودیت

الزامات: * constraint_status.ids برابر با LinearConstraints.ids است.

variable_status

SparseBasisStatusVector

وضعیت پایه متغیر

الزامات: * constraint_status.ids برابر با VariablesProto.ids است.

basic_dual_feasibility

SolutionStatusProto

این یک ویژگی پیشرفته است که توسط MathOpt برای توصیف امکان‌سنجی راه‌حل‌های LP کمتر از حد بهینه استفاده می‌شود (راه‌حل‌های بهینه همیشه وضعیت SOLUTION_STATUS_FEASIBLE را خواهند داشت).

برای LP های یک طرفه باید با وضعیت امکان سنجی راه حل دوگانه مرتبط برابر باشد. برای LP های دو طرفه ممکن است در برخی از موارد لبه متفاوت باشد (مثلاً حل های ناقص با سیمپلکس اولیه).

اگر پایه شروع را از طریق ModelSolveParametersProto.initial_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

جهت بهبود نامحدود به دو مسئله بهینه سازی. به طور معادل، گواهی عدم امکان پذیری اولیه.

به عنوان مثال، جفت برنامه خطی دوتایی اولیه را در نظر بگیرید: (اولیه) (دوگانه) min c * x max b * y st A * x >= b st y * A + r = cx >= 0 y، r >= 0. پرتو دوگانه جفت (y, r) راضی کننده است: b * y > 0 y * A + r = 0 y, r >= 0 توجه کنید که افزودن مضرب مثبت (y, r) به راه حل امکان پذیر دوگانه امکان سنجی دوگانه را حفظ می کند و هدف را بهبود می بخشد (اثبات دوگانه نامحدود است). پرتو دوگانه همچنین ثابت می کند که مشکل اولیه غیرممکن است.

در پیام DualRay زیر، y dual_values ​​و r کاهش_هزینه است.

زمینه های
dual_values

SparseDoubleVectorProto

الزامات: * dual_values.ids عناصر LinearConstraints.ids هستند. * dual_values.values ​​همه باید محدود باشند.

reduced_costs

SparseDoubleVectorProto

الزامات: * reduce_costs.ids عناصر VariablesProto.ids هستند. * values_costs.deduced همگی باید محدود باشند.

DualSolutionProto

راه حلی برای مسئله دوگانه بهینه سازی.

به عنوان مثال، جفت برنامه خطی دوتایی اولیه را در نظر بگیرید: (اولیه) (دوگانه) min c * x max b * y st A * x >= b st y * A + r = cx >= 0 y، r >= 0. راه حل دوگانه جفت (y, r) است. در صورتی امکان پذیر است که محدودیت های (Dual) بالا را برآورده کند.

در پیغام زیر، y مقدار_دوگانه، r کاهش_هزینه ها و b*y مقدار هدف است.

زمینه های
dual_values

SparseDoubleVectorProto

الزامات: * dual_values.ids عناصر LinearConstraints.ids هستند. * dual_values.values ​​همه باید محدود باشند.

reduced_costs

SparseDoubleVectorProto

الزامات: * reduce_costs.ids عناصر VariablesProto.ids هستند. * values_costs.deduced همگی باید محدود باشند.

feasibility_status

SolutionStatusProto

وضعیت امکان سنجی راه حل با توجه به حل کننده اساسی.

objective_value

double

تاکید Proto

سطح تلاش برای یک کار اختیاری در حین حل اعمال می شود (برای استفاده به SolveParametersProto مراجعه کنید).

تاکید برای پیکربندی یک ویژگی حل کننده به صورت زیر استفاده می شود: * اگر یک حل کننده از ویژگی پشتیبانی نمی کند، فقط UNSPECIFIED همیشه معتبر خواهد بود، هر تنظیم دیگری معمولاً یک خطای آرگومان نامعتبر خواهد داشت (بعضی از حل کننده ها ممکن است OFF را نیز بپذیرند). * اگر حل کننده از این ویژگی پشتیبانی می کند: - وقتی روی نامشخص تنظیم می شود، پیش فرض زیربنایی استفاده می شود. - هنگامی که ویژگی غیرفعال نمی شود، OFF با خطا مواجه می شود. - اگر ویژگی به طور پیش فرض فعال باشد، پیش فرض حل کننده معمولاً به MEDIUM نگاشت می شود. - اگر این ویژگی پشتیبانی شود، LOW، MEDIUM، HIGH و 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 Solver ادعا می کند که این مشکل غیر ممکن است.

IndicatorConstraintProto

داده هایی برای نشان دادن یک محدودیت نشانگر منفرد از فرم: متغیر(indicator_id) = (activate_on_zero ? 0 : 1) ⇒ low_bound <= عبارت <= upper_bound.

اگر متغیری که در این محدودیت دخیل است (اعم از نشانگر یا ظاهر شده در expression ) حذف شود، به گونه ای رفتار می شود که گویی روی صفر تنظیم شده است. به طور خاص، حذف متغیر نشانگر به این معنی است که اگر activate_on_zero نادرست باشد، محدودیت نشانگر خالی است، و اگر activate_on_zero درست باشد، معادل یک محدودیت خطی است.

زمینه های
activate_on_zero

bool

اگر درست باشد، اگر متغیر نشانگر مقدار 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() زود با TerminationReasonProto FEASIBLE یا NO_SOLUTION_FOUND متوقف می شود، محدودیت خاصی که به آن رسیده است.

Enums
LIMIT_UNSPECIFIED زمانی که از یک محدودیت (مانند TERMINATION_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_UNDETERMINED زمانی استفاده می‌شود که دلیل آن قابل تعیین نباشد، و LIMIT_OTHER زمانی استفاده می‌شود که دلیل مشخص باشد اما در هیچ یک از گزینه‌های فوق مناسب نباشد.

TerminationProto.detail ممکن است حاوی اطلاعات اضافی درباره محدودیت باشد.

LinearConstraintsProto

همانطور که در زیر استفاده می شود، "# محدودیت های خطی" = اندازه (LinearConstraintsProto.ids) را تعریف می کنیم.

زمینه های
ids[]

int64

باید غیرمنفی و به شدت افزایش یابد. مقدار max(int64) را نمی توان استفاده کرد.

lower_bounds[]

double

باید طولی برابر با #محدودیت های خطی داشته باشد، مقادیر در [-inf، inf).

upper_bounds[]

double

باید دارای طول برابر با #محدودیت های خطی، مقادیر در (-inf، inf] باشد.

names[]

string

اگر تنظیم نشده باشد، فرض می شود که همه رشته ها خالی هستند. در غیر این صورت، باید طولی برابر با #قیود خطی داشته باشد.

همه نام‌های خالی باید متمایز باشند.

LinearExpressionProto

یک نمایش پراکنده از یک عبارت خطی (مجموع وزنی متغیرها، به اضافه یک افست ثابت).

زمینه های
ids[]

int64

شناسه متغیرها باید (در ترتیب افزایشی) با همه عناصر متمایز مرتب شود.

coefficients[]

double

باید طول برابر با شناسه داشته باشد. مقادیر باید محدود باشند ممکن است NaN نباشند.

offset

double

باید محدود باشد و ممکن است NaN نباشد.

ModelProto

یک مشکل بهینه سازی MathOpt پشتیبانی می کند: - متغیرهای تصمیم گیری پیوسته و صحیح با کران های محدود اختیاری. - اهداف خطی و درجه دوم (منفرد یا چند هدف)، به حداقل یا حداکثر. - تعدادی از انواع محدودیت ها، از جمله: * محدودیت های خطی * محدودیت های درجه دوم * محدودیت های مخروط مرتبه دوم * محدودیت های منطقی > محدودیت های SOS1 و SOS2 > محدودیت های شاخص

به طور پیش فرض، محدودیت ها در نقشه های "id-to-data" نشان داده می شوند. با این حال، ما محدودیت های خطی را در قالب کارآمدتر "ساختار آرایه ها" نشان می دهیم.

زمینه های
name

string

variables

VariablesProto

objective

ObjectiveProto

هدف اصلی در مدل

auxiliary_objectives

map<int64, ObjectiveProto >

اهداف کمکی برای استفاده در مدل های چند هدفه.

شناسه های کلید نقشه باید در [0, max(int64)) باشد. هر اولویت و هر نام خالی باید منحصر به فرد و همچنین از objective اصلی متمایز باشد.

linear_constraints

LinearConstraintsProto

linear_constraint_matrix

SparseDoubleMatrixProto

ضرایب متغیر برای محدودیت های خطی.

اگر متغیری که در این محدودیت دخیل است حذف شود، به گونه ای رفتار می شود که گویی روی صفر تنظیم شده است.

الزامات: * linear_constraint_matrix.row_ids عناصر linear_constraints.ids هستند. * linear_constraint_matrix.column_ids عناصر variables.ids هستند. * ورودی های ماتریسی که مشخص نشده اند صفر هستند. * linear_constraint_matrix.values ​​همه باید محدود باشند.

quadratic_constraints

map<int64, QuadraticConstraintProto >

محدودیت های درجه دوم در مدل.

second_order_cone_constraints

map<int64, SecondOrderConeConstraintProto >

محدودیت های مخروطی مرتبه دوم در مدل.

sos1_constraints

map<int64, SosConstraintProto >

محدودیت های SOS1 در مدل، که محدود می کنند که حداکثر یک expression می تواند غیر صفر باشد. ورودی های weights اختیاری جزییات پیاده سازی هستند که توسط حل کننده برای همگرایی سریعتر (امیدوارم) استفاده می شود. با جزئیات بیشتر، حل‌کننده‌ها ممکن است (یا ممکن است) از این وزن‌ها برای انتخاب تصمیمات شاخه‌ای که گره‌های فرزند «متعادل» تولید می‌کنند استفاده کنند.

sos2_constraints

map<int64, SosConstraintProto >

محدودیت‌های SOS2 در مدل، که محدود می‌کنند که حداکثر دو ورودی expression می‌توانند غیر صفر باشند و باید در ترتیب خود مجاور باشند. اگر weights ارائه نشده باشد، این ترتیب، ترتیب خطی آنها در فهرست expressions است. اگر weights ارائه شوند، ترتیب با توجه به این مقادیر به ترتیب افزایشی گرفته می شود.

indicator_constraints

map<int64, IndicatorConstraintProto >

محدودیت‌های شاخص در مدل، که اعمال می‌کنند، اگر یک "متغیر شاخص" باینری روی یک تنظیم شود، "محدودیت ضمنی" باید برقرار باشد.

ModelSolveParametersProto

زمینه های
variable_values_filter

SparseVectorFilterProto

فیلتری که برای همه ظروف پراکنده برگشتی که توسط متغیرهای PrimalSolutionProto و PrimalRayProto کلید می‌خورند (PrimalSolutionProto.variable_values، PrimalRayProto.variable_values) اعمال می‌شود.

الزامات: * filtered_ids عناصر VariablesProto.ids هستند.

dual_values_filter

SparseVectorFilterProto

فیلتری که روی همه ظروف پراکنده برگشتی اعمال می‌شود که با محدودیت‌های خطی در DualSolutionProto و DualRay (DualSolutionProto.dual_values، DualRay.dual_values) کلید شده‌اند.

الزامات: * filtered_ids عناصر LinearConstraints.ids هستند.

reduced_costs_filter

SparseVectorFilterProto

فیلتری که برای همه ظروف پراکنده برگشتی که توسط متغیرهای DualSolutionProto و DualRay کلید می‌خورند (DualSolutionProto.reduced_costs، DualRay.reduced_costs) اعمال می‌شود.

الزامات: * filtered_ids عناصر VariablesProto.ids هستند.

initial_basis

BasisProto

مبنای اولیه اختیاری برای حلگرهای LP سیمپلکس با شروع گرم. در صورت تنظیم، انتظار می رود مطابق ValidateBasis در validators/solution_validator.h برای ModelSummary فعلی معتبر باشد.

solution_hints[]

SolutionHintProto

نکات راه حل اختیاری اگر حل کننده اصلی فقط یک اشاره را بپذیرد، از اولین اشاره استفاده می شود.

branching_priorities

SparseInt32VectorProto

اولویت های انشعاب اختیاری ابتدا متغیرهایی با مقادیر بالاتر منشعب می شوند. متغیرهایی که اولویت برای آنها تنظیم نشده است، اولویت پیش فرض حل کننده (معمولاً صفر) را دریافت می کنند.

الزامات: * branching_priorities.values ​​باید محدود باشد. * branching_priorities.ids باید عناصر VariablesProto.ids باشد.

ObjectiveBoundsProto

حدود مقدار هدف بهینه.

زمینه های
primal_bound

double

حل‌کننده ادعا می‌کند که مقدار بهینه برابر یا بهتر است (کوچک‌تر برای کمینه‌سازی و بزرگ‌تر برای حداکثر کردن) از primal_bound تا حل‌کننده‌ها تحمل امکان‌سنجی اولیه (به هشدار زیر مراجعه کنید): * primal_bound بی‌اهمیت است (+inf برای کمینه‌سازی و -inf حداکثر کردن) زمانی که حل‌کننده ادعا نمی کند که چنین محدودیتی دارد. * primal_bound می تواند به مقدار بهینه نزدیکتر از هدف بهترین راه حل اولیه اولیه باشد. به طور خاص، primal_bound ممکن است حتی زمانی که هیچ راه‌حل امکان‌پذیر اولیه برگردانده نمی‌شود، بی‌اهمیت باشد. هشدار: ادعای دقیق این است که یک راه حل اولیه وجود دارد که: * از نظر عددی امکان پذیر است (یعنی تا حد تحمل حل کننده ها امکان پذیر است)، و * دارای یک مقدار هدف primal_bound است. این راه حل عددی امکان پذیر می تواند کمی غیر قابل اجرا باشد، در این صورت primal_bound می تواند کاملاً بهتر از مقدار بهینه باشد. ترجمه یک تلورانس امکان سنجی اولیه به یک تلورانس در primal_bound، به ویژه زمانی که تحمل امکان سنجی نسبتاً زیاد است (مثلاً هنگام حل با PDLP) غیر ضروری است.

dual_bound

double

حل‌کننده ادعا می‌کند که مقدار بهینه برابر یا بدتر است (بزرگ‌تر برای کمینه‌سازی و کوچک‌تر برای حداکثر کردن) از dual_bound تا حل‌کننده تحمل امکان‌سنجی دوگانه (به هشدار زیر مراجعه کنید): * dual_bound بی‌اهمیت است (-inf برای کمینه‌سازی و +inf حداکثر کردن) زمانی که حل‌کننده ادعا نمی کند که چنین محدودیتی دارد. مشابه primal_bound، این ممکن است برای برخی از حل‌کننده‌ها حتی در زمان بازگشت بهینه اتفاق بیفتد. حل کننده های MIP معمولاً یک کران را گزارش می کنند حتی اگر نادقیق باشد. * برای مسائل پیوسته dual_bound می تواند به مقدار بهینه نزدیکتر از هدف بهترین راه حل امکان پذیر دوگانه باشد. برای MIP یکی از اولین مقادیر غیر ضروری برای dual_bound اغلب مقدار بهینه آرامش LP MIP است. * dual_bound باید بهتر باشد (برای کمینه سازی کوچکتر و برای حداکثرسازی بزرگتر) از primal_bound تا تلورانس های حل کننده (به هشدار زیر مراجعه کنید). هشدار: * برای مسائل پیوسته، ادعای دقیق این است که یک راه حل دوگانه وجود دارد که: * از نظر عددی امکان پذیر است (یعنی تا حد تحمل حل کننده ها امکان پذیر است)، و * دارای مقدار هدف dual_bound است. این راه حل عددی امکان پذیر می تواند کمی غیر قابل اجرا باشد، در این صورت dual_bound می تواند به شدت بدتر از مقدار بهینه و primal_bound باشد. مشابه مورد اولیه، ترجمه یک تحمل امکان‌سنجی دوگانه به یک تلورانس در dual_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

اصطلاحات ObjectiveProto که در متغیرهای تصمیم خطی هستند.

الزامات: * linear_coefficients.ids عناصر VariablesProto.ids هستند. * VariablesProto مشخص نشده با صفر مطابقت دارد. * linear_coefficients.values ​​باید همه محدود باشند. * linear_coefficients.values ​​می تواند صفر باشد، اما این فقط فضا را هدر می دهد.

quadratic_coefficients

SparseDoubleMatrixProto

اصطلاحات عینی که در متغیرهای تصمیم درجه دوم هستند.

الزامات علاوه بر موارد موجود در پیام های SparseDoubleMatrixProto: * هر عنصر quadratic_coefficients.row_ids و هر عنصر quadratic_coefficients.column_ids باید عنصری از VariablesProto.ids باشد. * ماتریس باید مثلث بالایی باشد: برای هر i، quadratic_coefficients.row_ids[i] <= quadratic_coefficients.column_ids[i].

نکات: * عباراتی که به صراحت ذخیره نشده اند دارای ضریب صفر هستند. * عناصر ضریب_کوادراتیک می تواند صفر باشد، اما این فقط فضا را هدر می دهد.

name

string

پیام‌های والدین ممکن است الزامات منحصربه‌فردی در این زمینه داشته باشند. به عنوان مثال، ModelProto.objectives و AuxiliaryObjectivesUpdatesProto.new_objectives را ببینید.

priority

int64

برای مسائل چند هدفه، اولویت این هدف نسبت به سایرین (پایین تر مهمتر است). این مقدار باید غیر منفی باشد. علاوه بر این، هر اولویت هدف در مدل باید در زمان حل متمایز باشد. این شرط در سطح پروتو تایید نشده است، بنابراین مدل‌ها ممکن است به طور موقت اهدافی با همان اولویت داشته باشند.

PrimalRayProto

جهت بهبود نامحدود به یک مسئله بهینه سازی؛ به طور معادل، گواهی عدم امکان برای مسئله دوگانه بهینه سازی.

به عنوان مثال یک برنامه خطی ساده را در نظر بگیرید: min c * x st A * x >= bx >= 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 st A * x >= bx >= 0. یک راه حل اولیه مقادیری است که به x نسبت داده می شود. در صورتی امکان پذیر است که A * x >= b و x >= 0 را از بالا برآورده کند. در پیام PrimalSolutionProto زیر، variable_values ​​x و object_value c * x است.

زمینه های
variable_values

SparseDoubleVectorProto

الزامات: * variable_values.ids عناصر VariablesProto.ids هستند. * variable_values.values ​​همه باید محدود باشند.

objective_value

double

مقدار عینی که توسط حل کننده اصلی محاسبه می شود. نمی تواند بی نهایت یا NaN باشد.

auxiliary_objective_values

map<int64, double>

مقادیر هدف کمکی که توسط حل کننده اصلی محاسبه می شود. کلیدها باید شناسه هدف کمکی معتبر باشند. مقادیر نمی توانند بی نهایت یا NaN باشند.

feasibility_status

SolutionStatusProto

وضعیت امکان سنجی راه حل با توجه به حل کننده اساسی.

ProblemStatusProto

وضعیت امکان سنجی مسئله اولیه و دوگانه آن (یا دوگانه آرامش مداوم) همانطور که توسط حل کننده ادعا شده است. حل کننده ملزم به بازگرداندن گواهی برای ادعا نیست (مثلاً حل کننده ممکن است بدون برگرداندن یک راه حل امکان پذیر اولیه ادعای امکان سنجی اولیه کند). این وضعیت ترکیبی توصیف جامعی از ادعاهای یک حل کننده در مورد امکان سنجی و نامحدود بودن مسئله حل شده را ارائه می دهد. برای مثال،

  • وضعیت امکان پذیر برای مسائل اولیه و دوگانه نشان می دهد که اولیه امکان پذیر و محدود است و احتمالاً راه حل بهینه ای دارد (تضمین شده برای مسائل بدون محدودیت های غیر خطی).
  • یک وضعیت امکان پذیر اولیه و یک وضعیت غیرقابل اجرا دوگانه نشان می دهد که مشکل اولیه نامحدود است (یعنی راه حل های دلخواه خوب دارد).

توجه داشته باشید که یک وضعیت غیرقابل اجرا دوگانه به خودی خود (یعنی همراه با یک وضعیت اولیه نامشخص) به این معنی نیست که مشکل اولیه نامحدود است زیرا ممکن است هر دو مشکل غیرقابل اجرا باشند. همچنین، در حالی که یک وضعیت امکان پذیر اولیه و دوگانه ممکن است به وجود یک راه حل بهینه دلالت کند، اما تضمین نمی کند که حل کننده چنین راه حل بهینه ای را پیدا کرده است.

زمینه های
primal_status

FeasibilityStatusProto

وضعیت برای مشکل اولیه

dual_status

FeasibilityStatusProto

وضعیت برای مشکل دوگانه (یا برای دوگانه آرامش مداوم).

primal_or_dual_infeasible

bool

اگر درست باشد، حل‌کننده ادعا می‌کند که مشکل اولیه یا دوگانه غیرممکن است، اما نمی‌داند کدام (یا هر دو غیرممکن هستند). فقط زمانی درست است که primal_problem_status = dual_problem_status = kUndetermined. این اطلاعات اضافی اغلب زمانی مورد نیاز است که پیش پردازش مشخص می کند که راه حل بهینه ای برای مشکل وجود ندارد (اما نمی توان تعیین کرد که آیا به دلیل غیرممکن بودن، نامحدود بودن یا هر دو است).

QuadraticConstraintProto

یک قید درجه دوم به شکل: lb <= sum{linear_terms} + sum{quadratic_terms} <= ub.

اگر متغیری که در این محدودیت دخیل است حذف شود، به گونه ای رفتار می شود که گویی روی صفر تنظیم شده است.

زمینه های
linear_terms

SparseDoubleVectorProto

اصطلاحاتی که در متغیرهای تصمیم خطی هستند.

علاوه بر الزامات پیام‌های SparseDoubleVectorProto، ما نیاز داریم که: * linear_terms.ids عناصر VariablesProto.ids باشد. * linear_terms.values ​​باید همه محدود باشند و NaN نباشند.

نکات: * شناسه های متغیر حذف شده دارای ضریب مربوطه صفر هستند. * linear_terms.values ​​می تواند صفر باشد، اما این فقط فضا را هدر می دهد.

quadratic_terms

SparseDoubleMatrixProto

اصطلاحاتی که در متغیرهای تصمیم گیری درجه دوم هستند.

علاوه بر الزامات پیام‌های SparseDoubleMatrixProto، ما نیاز داریم که: * هر عنصر quadratic_terms.row_ids و هر عنصر quadratic_terms.column_ids باید عنصری از VariablesProto.ids باشد. * ماتریس باید مثلث بالایی باشد: برای هر i، quadratic_terms.row_ids[i] <= quadratic_terms.column_ids[i].

نکات: * عباراتی که به صراحت ذخیره نشده اند دارای ضریب صفر هستند. * عناصر quadratic_terms.coefficients می توانند صفر باشند، اما این فقط فضا را هدر می دهد.

lower_bound

double

باید مقدار [-inf، inf) داشته باشد و کمتر یا مساوی با upper_bound باشد.

upper_bound

double

باید مقدار (-inf، inf] داشته باشد و بزرگتر یا مساوی با lower_bound باشد.

name

string

پیام‌های والدین ممکن است الزامات منحصربه‌فردی در این زمینه داشته باشند. به عنوان مثال، ModelProto.quadratic_constraints و QuadraticConstraintUpdatesProto.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 مبتنی بر Simplex معمولاً یک مبنای اولیه را به یک اشاره راه‌حل ترجیح می‌دهند (آنها برای تبدیل راهنمایی به یک راه‌حل اساسی اساسی نیاز به متقاطع دارند در غیر این صورت).

زمینه های
variable_values

SparseDoubleVectorProto

یک انتساب احتمالاً جزئی از مقادیر به متغیرهای اولیه مسئله. الزامات مستقل از حل کننده برای این پیام فرعی عبارتند از: * variable_values.ids عناصر VariablesProto.ids هستند. * variable_values.values ​​همه باید محدود باشند.

dual_values

SparseDoubleVectorProto

تخصیص (بالقوه جزئی) مقادیر به قیود خطی مسئله.

الزامات: * dual_values.ids عناصر LinearConstraintsProto.ids هستند. * dual_values.values ​​همه باید محدود باشند.

SolutionProto

آنچه در راه حل گنجانده می شود به نوع مشکل و حل کننده بستگی دارد. الگوهای رایج فعلی 1 هستند. حل کننده های MIP فقط یک راه حل اولیه را برمی گرداند. 2. حل کننده های ساده LP اغلب یک مبنا و راه حل های اولیه و دوگانه مرتبط با این مبنا را برمی گردانند. 3. سایر حل کننده های پیوسته اغلب یک راه حل اولیه و دوگانه را که به شکلی وابسته به حل کننده به هم متصل هستند، برمی گردانند.

الزامات: * حداقل یک فیلد باید تنظیم شود. یک راه حل نمی تواند خالی باشد

زمینه های
primal_solution

PrimalSolutionProto

dual_solution

DualSolutionProto

basis

BasisProto

SolutionStatusProto

امکان سنجی یک راه حل اولیه یا دوگانه همانطور که توسط حل کننده ادعا شده است.

Enums
SOLUTION_STATUS_UNSPECIFIED مقدار گارد نشان دهنده وضعیتی نیست.
SOLUTION_STATUS_UNDETERMINED حل کننده وضعیت امکان سنجی را ادعا نمی کند.
SOLUTION_STATUS_FEASIBLE Solver ادعا می کند که راه حل امکان پذیر است.
SOLUTION_STATUS_INFEASIBLE Solver ادعا می کند که راه حل غیر ممکن است.

SolveParametersProto

پارامترهایی برای کنترل یک حل واحد.

شامل هر دو پارامتر مشترک برای همه حل کننده ها به عنوان مثال time_limit، و پارامترهای یک حل کننده خاص، به عنوان مثال gscip. اگر مقداری هم در فیلد مشترک و هم در فیلد مخصوص حل کننده تنظیم شود، از تنظیم خاص حل کننده استفاده می شود.

پارامترهای رایجی که اختیاری و تنظیم نشده یا یک عدد با مقدار نامشخص هستند، نشان می‌دهند که از پیش‌فرض حل‌کننده استفاده می‌شود.

پارامترهای خاص حل کننده برای حل کننده هایی غیر از مورد استفاده نادیده گرفته می شوند.

پارامترهایی که به مدل بستگی دارند (به عنوان مثال اولویت انشعاب برای هر متغیر تنظیم شده است) در ModelSolveParametersProto ارسال می شوند.

زمینه های
time_limit

Duration

حداکثر زمانی که یک حل کننده باید برای مسئله صرف کند (یا بی نهایت اگر تنظیم نشده باشد).

این مقدار محدودیت سختی نیست، زمان حل ممکن است کمی بیشتر از این مقدار باشد. این پارامتر همیشه به حل کننده اصلی ارسال می شود، پیش فرض حل کننده استفاده نمی شود.

enable_output

bool

چاپ ردپای پیاده سازی حل کننده را فعال می کند. مکان آن آثار به حل کننده بستگی دارد. برای SCIP و Gurobi این جریان خروجی استاندارد خواهد بود. برای Glop و CP-SAT این LOG (INFO) خواهد بود.

توجه داشته باشید که اگر حل کننده از callback پیام پشتیبانی می کند و کاربر برای آن یک callback ثبت می کند، این مقدار پارامتر نادیده گرفته می شود و هیچ اثری چاپ نمی شود.

lp_algorithm

LPAlgorithmProto

الگوریتم حل یک برنامه خطی اگر LP_ALGORITHM_UNSPECIFIED، از الگوریتم پیش فرض حل کننده استفاده کنید.

برای مسائلی که برنامه‌های خطی نیستند اما برنامه‌نویسی خطی یک زیر روال است، حل‌کننده‌ها ممکن است از این مقدار استفاده کنند. به عنوان مثال، حل کننده های MIP معمولاً از این فقط برای حل ریشه LP استفاده می کنند (و در غیر این صورت از دو سیمپلکس استفاده می کنند).

presolve

EmphasisProto

قبل از شروع الگوریتم اصلی یا سطح تلاش پیش‌فرض حل‌کننده در صورت EMPHASIS_UNSPECIFIED، سعی کنید مشکل را ساده کنید.

cuts

EmphasisProto

در صورت EMPHASIS_UNSPECIFIED، برای ایجاد آرامش LP قوی‌تر (فقط MIP)، یا سطح تلاش پیش‌فرض حل‌کننده تلاش کنید.

توجه: غیرفعال کردن برش‌ها ممکن است مانع از فرصتی برای افزودن برش‌ها در MIP_NODE شود، این رفتار مخصوص حل‌کننده است.

heuristics

EmphasisProto

تلاش برای یافتن راه‌حل‌های امکان‌پذیر فراتر از راه‌حل‌هایی که در روش جستجوی کامل (فقط MIP)، یا سطح تلاش پیش‌فرض حل‌کننده در صورت EMPHASIS_UNSPECIFIED مواجه می‌شوند.

scaling

EmphasisProto

در صورت EMPHASIS_UNSPECIFIED، تلاش برای تغییر مقیاس مسئله برای بهبود پایداری عددی، یا سطح تلاش پیش‌فرض حل‌کننده.

iteration_limit

int64

محدودیت در تکرارهای الگوریتم زیربنایی (مثلاً محورهای سیمپلکس). رفتار خاص به حل کننده و الگوریتم مورد استفاده بستگی دارد، اما اغلب می تواند یک حد تعیین کننده حل ارائه دهد (ممکن است پیکربندی بیشتری مورد نیاز باشد، به عنوان مثال یک رشته).

به طور معمول توسط حل کننده های LP، QP و MIP پشتیبانی می شود، اما برای حل کننده های MIP نیز به node_limit مراجعه کنید.

node_limit

int64

محدودیت در تعداد زیرمسائل حل شده در جستجوی شمارشی (به عنوان مثال شاخه و کران). برای بسیاری از حل‌کننده‌ها، می‌توان از آن برای محدود کردن محاسبات به طور قطعی استفاده کرد (ممکن است پیکربندی بیشتری مورد نیاز باشد، مثلاً یک رشته).

به طور معمول برای حل کننده های MIP، iteration_limit را نیز ببینید.

cutoff_limit

double

اگر بتواند ثابت کند که هیچ راه حل اولیه ای حداقل به خوبی قطعی وجود ندارد، حل کننده زود متوقف می شود.

در توقف اولیه، حل کننده دلیل خاتمه NO_SOLUTION_FOUND و با محدودیت CUTOFF را برمی گرداند و نیازی به ارائه اطلاعات راه حل اضافی ندارد. اگر توقف اولیه وجود نداشته باشد، تأثیری بر مقدار بازگشتی ندارد.

توصیه می شود در صورتی که می خواهید راه حل هایی با هدف دقیقاً برابر با برش بازگردانده شوند، از تلورانس استفاده کنید.

برای جزئیات بیشتر و مقایسه با best_bound_limit به راهنمای کاربر مراجعه کنید.

objective_limit

double

حل کننده به محض اینکه راه حلی حداقل به این خوبی پیدا کند زود متوقف می شود، با دلیل خاتمه عملی و محدودیت هدف.

best_bound_limit

double

به محض اینکه ثابت کرد بهترین کران حداقل این خوب است، با دلیل خاتمه FEASIBLE یا NO_SOLUTION_FOUND و محدودیت OBJECTIVE، حل کننده زود متوقف می شود.

برای جزئیات بیشتر و مقایسه با cutoff_limit به راهنمای کاربر مراجعه کنید.

solution_limit

int32

حل‌کننده پس از یافتن این تعداد راه‌حل امکان‌پذیر، با دلیل خاتمه امکان پذیر و راه حل محدود، زود متوقف می‌شود. در صورت تنظیم باید بزرگتر از صفر باشد. اغلب از آن استفاده می شود تا حل کننده در اولین راه حل عملی یافت شده متوقف شود. توجه داشته باشید که هیچ تضمینی در مورد مقدار هدف برای هیچ یک از راه حل های برگشتی وجود ندارد.

حل‌کننده‌ها معمولاً راه‌حل‌های بیشتری از حد راه‌حل را بر نمی‌گردانند، اما این مورد توسط 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 است). - GLOP: [0:2147483647] (همانطور که در بالا) در همه موارد، حل کننده مقداری برابر با: MAX(0، MIN(MAX_VALID_VALUE_FOR_SOLVER، random_seed)) دریافت می کند.

absolute_gap_tolerance

double

یک تحمل بهینه مطلق (در درجه اول) برای حل کننده های MIP.

GAP مطلق قدر مطلق تفاوت بین: * مقدار عینی بهترین راه حل ممکن یافت شده، * کران دوگانه تولید شده توسط جستجو است. حل‌کننده می‌تواند زمانی که GAP مطلق در حداکثر absolute_gap_tolerance (زمانی که تنظیم شده است) متوقف شود و TERMINATION_REASON_OPTIMAL را برگرداند.

در صورت تنظیم باید >= 0 باشد.

همچنین relative_gap_tolerance را ببینید.

relative_gap_tolerance

double

تحمل بهینه نسبی (در درجه اول) برای حل کننده های MIP.

شکاف نسبی یک نسخه عادی از شکاف مطلق (تعریف شده در Absolute_gap_tolerance) است ، جایی که عادی سازی وابسته به حل کننده است ، به عنوان مثال شکاف مطلق تقسیم بر مقدار عینی بهترین راه حل امکان پذیر است.

حل کننده می تواند متوقف شود که شکاف نسبی حداکثر nexation_gap_tolerance (هنگام تنظیم) باشد ، و Termination_Reason_optimal را برگردانید.

در صورت تنظیم باید> = 0 باشد.

همچنین به Absolute_gap_Tolerance مراجعه کنید.

solution_pool_size

int32

در هنگام جستجو ، راه حل های solution_pool_size را حفظ کنید. استخر راه حل به طور کلی دارای دو کارکرد است: (1) برای حل کننده هایی که می توانند بیش از یک راه حل را برگردانند ، این محدودیت تعداد راه حل ها را محدود می کند. (2) برخی از حل کننده ها ممکن است اکتشافی را با استفاده از راه حل های استخر محلول اجرا کنند ، بنابراین تغییر این مقدار ممکن است در مسیر الگوریتم تأثیر بگذارد. برای مجبور کردن حل کننده برای پر کردن استخر محلول ، به عنوان مثال با بهترین راه حل ها ، به پیکربندی خاص و حل کننده بیشتر نیاز دارد.

SolveresultProto

قرارداد زمان راه حل های اولیه/دوگانه/پرتوهای پیچیده است ، برای توضیحات کامل به Termination_reasons.md مراجعه کنید.

تا زمانی که یک قرارداد دقیق نهایی نشود ، ایمن ترین است که به سادگی بررسی کنید که آیا یک راه حل/پرتو به جای تکیه بر دلیل خاتمه وجود دارد یا خیر.

زمینه های
termination

TerminationProto

دلیل متوقف کردن حل کننده.

solutions[]

SolutionProto

قرارداد کلی برای ترتیب راه حل هایی که حل کننده های آینده باید اجرا کنند این است که ترتیب دهید: 1. راه حل ها با یک راه حل امکان پذیر اولیه ، که توسط بهترین هدف اولیه سفارش داده می شود. 2. راه حل هایی با یک راه حل امکان پذیر دوگانه ، سفارش داده شده توسط بهترین هدف دوگانه (هدف دوگانه ناشناخته بدترین است) 3. همه راه حل های باقی مانده به هر ترتیب قابل بازگشت هستند.

primal_rays[]

PrimalRayProto

مسیرهای بهبود اولیه بی حد و حصر یا گواهینامه های دوتایی دوگانه. به طور معمول برای خاتمه دادن

dual_rays[]

DualRayProto

مسیرهای بهبود دوگانه بی حد و حصر ، یا به طور معادل ، گواهینامه های نفوذپذیری اولیه. به طور معمول برای TerminationReasonProto غیرقابل استفاده است.

solve_stats

SolveStatsProto

آمار مربوط به فرآیند حل ، به عنوان مثال زمان اجرا ، تکرارها.

لات

زمینه های
solve_time

Duration

زمان ساعت دیوار سپری شده همانطور که توسط MATH_OPT اندازه گیری می شود ، تقریباً زمان داخل حل کننده :: حل (). توجه: این شامل کار ساخته شده در ساخت مدل نیست.

problem_status

ProblemStatusProto

وضعیت امکان سنجی برای مشکلات اولیه و دوگانه.

simplex_iterations

int64

barrier_iterations

int64

first_order_iterations

int64

node_count

int64

حلقوی

حل کننده های پشتیبانی شده توسط Mathopt.

Enums
SOLVER_TYPE_UNSPECIFIED
SOLVER_TYPE_GSCIP

حل برنامه های عدد صحیح محدودیت (SCIP) حل کننده (شخص ثالث).

از مشکلات درجه دوم LP ، MIP و Nonconvex پشتیبانی می کند. هیچ داده دوگانه برای LPS بازگردانده نمی شود. GLOP را برای LPS ترجیح دهید.

SOLVER_TYPE_GUROBI

GUROBI SOLVER (شخص ثالث).

از مشکلات درجه دوم LP ، MIP و Nonconvex پشتیبانی می کند. به طور کلی سریعترین گزینه ، اما دارای مجوز ویژه است.

SOLVER_TYPE_GLOP

Google Glop Solver.

LP را با روش های Simplex اولیه و دوگانه پشتیبانی می کند.

SOLVER_TYPE_CP_SAT

حل کننده CP-SAT Google.

مشکلاتی را پشتیبانی می کند که در آن همه متغیرها عدد صحیح و محدود هستند (یا دلالت می کنند که پس از پیش بینی). پشتیبانی آزمایشی برای نجات و تفکیک مشکلات با متغیرهای مداوم.

SOLVER_TYPE_PDLP

حل کننده PDLP Google.

از LP و اهداف درجه دوم مورخ محدب پشتیبانی می کند. از روشهای مرتبه اول به جای Simplex استفاده می کند. می تواند مشکلات بسیار بزرگی را حل کند.

SOLVER_TYPE_GLPK

کیت برنامه نویسی خطی GNU (GLPK) (شخص ثالث).

از MIP و LP پشتیبانی می کند.

امنیت موضوع: GLPK برای تخصیص حافظه از ذخیره محلی-محلی استفاده کنید. در نتیجه ، نمونه های حل کننده باید در همان نخ ایجاد شوند که ایجاد شده اند یا GLPK خراب می شود. به نظر می رسد تماس با Solver :: Solve () از نخ دیگر از آنچه برای ایجاد حل کننده استفاده می شود ، اما توسط GLPK مستند نشده است و باید از آن اجتناب کرد.

هنگام حل یک LP با پیش بینی ، یک راه حل (و پرتوهای بدون مرز) فقط در صورت یافتن محلول بهینه بازگردانده می شود. در غیر این صورت هیچ چیز بازگردانده نمی شود. برای جزئیات بیشتر به GLPK-5.0/DOC/GLPK.PDF صفحه شماره 40 در دسترس از GLPK-5.0.TAR.GZ مراجعه کنید.

SOLVER_TYPE_OSQP

برنامه Solver (شخص ثالث) اپراتور تقسیم برنامه درجه دوم (OSQP).

از مشکلات مداوم با محدودیت های خطی و اهداف درجه دوم خطی یا محدب پشتیبانی می کند. از یک روش مرتبه اول استفاده می کند.

SOLVER_TYPE_ECOS

حل کننده مخروط تعبیه شده (ECOS) (شخص ثالث).

از مشکلات LP و SOCP پشتیبانی می کند. از روشهای نقطه داخلی (سد) استفاده می کند.

SOLVER_TYPE_SCS

حل کننده مخروط تقسیم کننده (SCS) (شخص ثالث).

از مشکلات LP و SOCP پشتیبانی می کند. از یک روش مرتبه اول استفاده می کند.

SOLVER_TYPE_HIGHS

HIGHS SOLVER (شخص ثالث).

از مشکلات LP و MIP پشتیبانی می کند (QP های محدب مورد نظر نیستند).

SOLVER_TYPE_SANTORINI

اجرای مرجع ماتوپت از یک حل کننده MIP.

آهسته/برای تولید توصیه نمی شود. نه یک حل کننده LP (هیچ اطلاعات دوگانه برگشته است).

SosConstraintProto

داده ها برای نشان دادن یک محدودیت SOS1 یا SOS2.

اگر متغیری درگیر در این محدودیت حذف شود ، به نظر می رسد که بر روی صفر تنظیم شده است.

زمینه های
expressions[]

LinearExpressionProto

عباراتی که برای استفاده از محدودیت SOS: * SOS1: حداکثر یک عنصر مقدار غیرزرو را می گیرد. * SOS2: حداکثر دو عنصر مقادیر غیرزرو را می گیرند و باید در سفارش مکرر مجاور باشند.

weights[]

double

یا خالی یا با طول برابر با عبارات. اگر خالی باشد ، وزن پیش فرض 1 ، 2 ، ... در صورت وجود ، ورودی ها باید بی نظیر باشند.

name

string

پیام های والدین ممکن است نیازهای منحصر به فرد در این زمینه داشته باشند. به عنوان مثال ، به modelproto.sos1_constraints و sosconstraintupdatesproto.new_constraints مراجعه کنید.

پراکنده

بازنمایی پراکنده از یک بردار از وضعیت پایه.

زمینه های
ids[]

int64

باید طبقه بندی شود (در افزایش سفارش) با همه عناصر متمایز.

values[]

BasisStatusProto

باید طول مساوی با شناسه داشته باشد.

پراکنده پراکنده

نمایشی پراکنده از ماتریس دونفره.

ماتریس به عنوان سه گانه از ردیف شناسه ، شناسه ستون و ضریب ذخیره می شود. این سه بردار باید از طول مساوی باشند. برای همه من ، tuple (row_ids [i] ، column_ids [i]) باید متمایز باشد. ورودی ها باید به ترتیب اصلی باشند.

زمینه های
row_ids[]

int64

column_ids[]

int64

coefficients[]

double

ممکن است حاوی نان نباشد.

parsedoublevectorproto

نمایشی پراکنده از یک بردار از دونفره.

زمینه های
ids[]

int64

باید طبقه بندی شود (در افزایش سفارش) با همه عناصر متمایز.

values[]

double

باید طول مساوی با شناسه داشته باشد. ممکن است حاوی نان نباشد.

Plansint32VectorProto

بازنمایی پراکنده از یک بردار INTS.

زمینه های
ids[]

int64

باید طبقه بندی شود (در افزایش سفارش) با همه عناصر متمایز.

values[]

int32

باید طول مساوی با شناسه داشته باشد.

پراکنده فیلیستروپوتو

این پیام اجازه می دهد تا قسمت های خاصی از یک پراکنده پراکنده را پرس و جو/تنظیم کنید. رفتار پیش فرض این نیست که چیزی را فیلتر کنید. استفاده مشترک برای پرس و جو فقط بخش هایی از راه حل ها (فقط مقادیر غیر صفر و/یا فقط یک مجموعه دستی از مقادیر متغیر) است.

زمینه های
skip_zero_values

bool

برای پراکندهبولویکتورپروتو "صفر" false است.

filter_by_ids

bool

هنگامی که درست است ، فقط مقادیر مربوط به شناسه های ذکر شده در filtered_ids را برگردانید.

filtered_ids[]

int64

لیست شناسه ها برای استفاده در هنگام صحیح بودن filter_by_ids. وقتی Filter_By_ids نادرست است باید خالی باشد. توجه: اگر این خالی است ، و filter_by_ids درست است ، شما می گویید که در نتیجه هیچ اطلاعاتی نمی خواهید.

خاتم

کلیه اطلاعات مربوط به دلیل فسخ تماس برای حل ().

زمینه های
reason

TerminationReasonProto

اطلاعات اضافی در limit زمانی که ارزش خاتمه داده شده است_Reason_Feasible یا Termination_Reason_no_solution_found ، برای جزئیات بیشتر به limit مراجعه کنید.

limit

LimitProto

limit_unspecified است ، مگر اینکه دلیل خاتمه باشد_Reason_Feasible یا Termination_Reason_no_solution_found. همه حل کننده ها همیشه نمی توانند حد و مرز ناشی از خاتمه را تعیین کنند ، در صورت عدم تعیین علت ، از حد مجاز استفاده می شود.

detail

string

اطلاعات خاص به طور معمول حل کننده در مورد خاتمه.

problem_status

ProblemStatusProto

وضعیت امکان سنجی برای مشکلات اولیه و دوگانه. از 18 ژوئیه 2023 این پیام ممکن است از دست رفته باشد. در صورت گم شدن ، مشکل_ستاتوس را می توان در solveresultproto.solve_stats یافت.

objective_bounds

ObjectiveBoundsProto

محدودیت در مقدار هدف بهینه. از 18 ژوئیه 2023 این پیام ممکن است از دست رفته باشد. در صورت گم شدن ، uebine_bounds.primal_bound را می توان در solveresultproto.solve.stats.best_primal_bound and upindive_bounds.dual_bound در solveresultproto.solve.stats.best_dual_bound یافت.

TerminationReasonProto

دلیل فراخوانی برای حل () خاتمه می یابد.

Enums
TERMINATION_REASON_UNSPECIFIED
TERMINATION_REASON_OPTIMAL یک راه حل بهینه بهینه (تا تحمل عددی) یافت شده است.
TERMINATION_REASON_INFEASIBLE مشکل اولیه هیچ راه حل امکان پذیر ندارد.
TERMINATION_REASON_UNBOUNDED مشکل اولیه امکان پذیر است و به طور خودسرانه راه حل های خوبی را می توان در امتداد یک پرتوی اولیه یافت.
TERMINATION_REASON_INFEASIBLE_OR_UNBOUNDED مشکل اولیه یا غیرقابل نفوذ یا بی حد و مرز است. جزئیات بیشتر در مورد وضعیت مشکل ممکن است در solve_stats.problem_status در دسترس باشد. توجه داشته باشید که وضعیت بی حد و حصر گوروبی ممکن است در اینجا نقشه برداری شود.
TERMINATION_REASON_IMPRECISE

این مشکل برای یکی از معیارهای فوق (بهینه ، غیرقابل تحمل ، بی حد و مرز یا غیرقابل تحمل) حل شد ، اما یک یا چند تحمل برآورده نشد. برخی از راه حل های/پرتوهای اولیه/دوگانه وجود دارد ، اما یا کمی غیرقابل نفوذ خواهند بود ، یا (اگر مشکل تقریباً بهینه باشد) ممکن است شکاف بین بهترین هدف راه حل و بهترین هدف باشد.

کاربران هنوز هم می توانند از راه حل های ابتدایی/دوگانه/پرتوهای و آمار راه حل استفاده کنند ، اما آنها وظیفه برخورد با عدم دقت عددی را بر عهده دارند.

TERMINATION_REASON_FEASIBLE بهینه ساز به نوعی محدودیت رسید و یک راه حل عملی اولیه بازگردانده می شود. برای توضیحات دقیق از نوع محدودیتی که به دست آمده است ، به SolveresultProto.limit_detail مراجعه کنید.
TERMINATION_REASON_NO_SOLUTION_FOUND بهینه ساز به نوعی محدودیت رسید و یک راه حل عملی اولیه پیدا نکرد. برای توضیحات دقیق از نوع محدودیتی که به دست آمده است ، به SolveresultProto.limit_detail مراجعه کنید.
TERMINATION_REASON_NUMERICAL_ERROR این الگوریتم متوقف شد زیرا با خطای عددی غیرقابل برگشت روبرو شد. هیچ اطلاعات راه حل در دسترس نیست.
TERMINATION_REASON_OTHER_ERROR این الگوریتم به دلیل خطایی که توسط یکی از وضعیت های تعریف شده در بالا پوشیده نشده است متوقف شد. هیچ اطلاعات راه حل در دسترس نیست.

متغیرها

همانطور که در زیر استفاده می شود ، "#variables" = اندازه (متغیرهای proto.ids) را تعریف می کنیم.

زمینه های
ids[]

int64

باید غیر منفی و کاملاً در حال افزایش باشد. از مقدار حداکثر (INT64) استفاده نمی شود.

lower_bounds[]

double

باید دارای طول برابر با #variables ، مقادیر در [-inf ، Inf) باشد.

upper_bounds[]

double

باید دارای طول برابر با #variables ، مقادیر در (-inf ، inf] باشد.

integers[]

bool

باید دارای طول برابر با #variables باشد. مقدار برای متغیرهای مداوم نادرست است و برای متغیرهای عدد صحیح صادق است.

names[]

string

اگر تنظیم نشده باشد ، فرض می شود همه رشته های خالی است. در غیر این صورت ، باید دارای طول برابر با #variables باشد.

همه نامهای غیر خالی باید متمایز باشند.