مدل ورودی را حل می کند و نتیجه را یکباره برمی گرداند. زمانی که نیازی به تماس، افزایشی و ردیابی پیشرفت حل ندارید از این استفاده کنید.
درخواست HTTP
POST https://optimization.googleapis.com/v1/mathopt:solveMathOptModel
URL از دستور GRPC Transcoding استفاده می کند.
درخواست بدن
بدنه درخواست حاوی داده هایی با ساختار زیر است:
نمایندگی JSON |
---|
{ "solverType": enum ( |
زمینه های | |
---|---|
solverType | اختیاری. حل کننده برای حل عددی مسئله تایپ کنید. توجه داشته باشید که اگر یک حل کننده از ویژگی خاصی در مدل پشتیبانی نکند، روند بهینه سازی موفقیت آمیز نخواهد بود. |
model | ضروری. یک نمایش ریاضی از مسئله بهینه سازی برای حل. |
parameters | اختیاری. پارامترهایی برای کنترل یک حل واحد. پارامتر enableOutput به طور خاص مدیریت می شود. برای حلکنندههایی که از تماسهای پیامها پشتیبانی میکنند، تنظیم آن بر روی true باعث میشود سرور یک پاسخ تماس پیام را ثبت کند. پیام های به دست آمده در SolveMathOptModelResponse.messages بازگردانده می شوند. برای حل کننده های دیگر، تنظیم enableOutput روی true منجر به خطا می شود. |
modelParameters | اختیاری. پارامترهایی برای کنترل یک حل منفرد که مختص مدل ورودی هستند (برای پارامترهای مستقل مدل به SolveParametersProto مراجعه کنید). |
بدن پاسخگو
پاسخ برای حل یکپارچه از راه دور در MathOpt.
در صورت موفقیت آمیز بودن، بدنه پاسخ حاوی داده هایی با ساختار زیر است:
نمایندگی JSON |
---|
{
"result": {
object ( |
زمینه های | |
---|---|
result | شرح خروجی حل مدل در درخواست. |
messages[] | اگر SolveParametersProto.enable_output استفاده شده باشد، این شامل پیامهای گزارش برای حلکنندههایی است که از تماسهای پیام پشتیبانی میکنند. |
SolverTypeProto
حل کننده های پشتیبانی شده توسط MathOpt.
Enums | |
---|---|
SOLVER_TYPE_UNSPECIFIED | |
SOLVER_TYPE_GSCIP | حل کننده محدودیت برنامه های عدد صحیح (SCIP) (شخص ثالث). پشتیبانی از مسائل LP، MIP، و غیر محدب عدد صحیح درجه دوم. با این حال، هیچ داده دوگانه ای برای LP ها بازگردانده نمی شود. GLOP را برای LP ترجیح دهید. |
SOLVER_TYPE_GUROBI | حل کننده گوروبی (شخص ثالث). پشتیبانی از مسائل LP، MIP، و غیر محدب عدد صحیح درجه دوم. به طور کلی سریعترین گزینه است، اما دارای مجوز ویژه است. |
SOLVER_TYPE_GLOP | حل کننده گلوپ گوگل از LP با روش های سیمپلکس اولیه و دوگانه پشتیبانی می کند. |
SOLVER_TYPE_CP_SAT | حل کننده CP-SAT گوگل. از مشکلاتی پشتیبانی می کند که در آن همه متغیرها عدد صحیح و محدود هستند (یا به طور ضمنی بعد از پیش حل هستند). پشتیبانی تجربی برای مقیاس مجدد و گسسته سازی مشکلات با متغیرهای پیوسته. |
SOLVER_TYPE_PDLP | حل کننده PDLP گوگل. پشتیبانی از LP و اهداف درجه دوم مورب محدب. از روش های مرتبه اول به جای سیمپلکس استفاده می کند. می تواند مشکلات بسیار بزرگ را حل کند. |
SOLVER_TYPE_GLPK | کیت برنامه نویسی خطی گنو (GLPK) (شخص ثالث). پشتیبانی از MIP و LP Thread-safety: GLPK از حافظه محلی رشته برای تخصیص حافظه استفاده می کند. در نتیجه، نمونههای حلکننده باید در همان رشتهای که ایجاد میشوند از بین بروند وگرنه GLPK خراب میشود. به نظر میرسد که فراخوانی Solver::Solve() از رشتهای غیر از رشتهای که برای ایجاد 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 | حل کننده مخروطی تقسیم (SCS) (شخص ثالث). از مشکلات LP و SOCP پشتیبانی می کند. از روش مرتبه اول استفاده می کند. |
SOLVER_TYPE_HIGHS | حل کننده HiGHS (شخص ثالث). از مشکلات LP و MIP پشتیبانی می کند (QPهای محدب اجرا نمی شوند). |
SOLVER_TYPE_SANTORINI | پیاده سازی مرجع MathOpt از یک حل کننده MIP. کند / برای تولید توصیه نمی شود. حل کننده LP نیست (هیچ اطلاعات دوگانه ای برگردانده نمی شود). |
ModelProto
یک مشکل بهینه سازی MathOpt پشتیبانی می کند: - متغیرهای تصمیم گیری پیوسته و صحیح با کران های محدود اختیاری. - اهداف خطی و درجه دوم (منفرد یا چند هدف)، به حداقل یا حداکثر. - تعدادی از انواع محدودیت ها، از جمله: * محدودیت های خطی * محدودیت های درجه دوم * محدودیت های مخروط مرتبه دوم * محدودیت های منطقی > محدودیت های SOS1 و SOS2 > محدودیت های شاخص
به طور پیش فرض، محدودیت ها در نقشه های "id-to-data" نشان داده می شوند. با این حال، ما محدودیت های خطی را در قالب کارآمدتر "ساختار آرایه ها" نشان می دهیم.
نمایندگی JSON |
---|
{ "name": string, "variables": { object ( |
زمینه های | |
---|---|
name | |
variables | |
objective | هدف اصلی در مدل |
auxiliaryObjectives | اهداف کمکی برای استفاده در مدل های چند هدفه. شناسه های کلید نقشه باید در [0, max(int64)) باشد. هر اولویت و هر نام خالی باید منحصر به فرد و همچنین از یک شی حاوی لیستی از |
linearConstraints | |
linearConstraintMatrix | ضرایب متغیر برای محدودیت های خطی. اگر متغیری که در این محدودیت دخیل است حذف شود، به گونه ای رفتار می شود که گویی روی صفر تنظیم شده است. الزامات: * linearConstraintMatrix.row_ids عناصر linearConstraints.ids هستند. * linearConstraintMatrix.column_ids عناصر variables.ids هستند. * ورودی های ماتریسی که مشخص نشده اند صفر هستند. * linearConstraintMatrix.values باید همه محدود باشند. |
quadraticConstraints | محدودیت های درجه دوم در مدل. یک شی حاوی لیستی از |
secondOrderConeConstraints | محدودیت های مخروطی مرتبه دوم در مدل. یک شی حاوی لیستی از |
sos1Constraints | محدودیت های SOS1 در مدل، که محدود می کنند که حداکثر یک یک شی حاوی لیستی از |
sos2Constraints | محدودیتهای SOS2 در مدل، که محدود میکنند که حداکثر دو ورودی یک شی حاوی لیستی از |
indicatorConstraints | محدودیتهای شاخص در مدل، که اعمال میکنند، اگر یک "متغیر شاخص" باینری روی یک تنظیم شود، "محدودیت ضمنی" باید برقرار باشد. یک شی حاوی لیستی از |
VariablesProto
همانطور که در زیر استفاده می شود، "#variables" = size(VariablesProto.ids) را تعریف می کنیم.
نمایندگی JSON |
---|
{ "ids": [ string ], "lowerBounds": [ number ], "upperBounds": [ number ], "integers": [ boolean ], "names": [ string ] } |
زمینه های | |
---|---|
ids[] | باید غیرمنفی و به شدت افزایش یابد. مقدار max(int64) را نمی توان استفاده کرد. |
lowerBounds[] | باید دارای طول برابر با #متغیرها، مقادیر [-inf، inf) باشد. |
upperBounds[] | باید دارای طول برابر با #متغیرها، مقادیر در (-inf، inf] باشد. |
integers[] | طول باید برابر با #متغیرها باشد. مقدار برای متغیرهای پیوسته false و برای متغیرهای عدد صحیح درست است. |
names[] | اگر تنظیم نشده باشد، فرض می شود که همه رشته ها خالی هستند. در غیر این صورت، باید طولی برابر با #متغیرها داشته باشد. همه نامهای خالی باید متمایز باشند. |
ObjectiveProto
نمایندگی JSON |
---|
{ "maximize": boolean, "offset": number, "linearCoefficients": { object ( |
زمینه های | |
---|---|
maximize | false به حداقل رساندن، true حداکثر کردن است |
offset | باید متناهی باشد و NaN نباشد. |
linearCoefficients | اصطلاحات ObjectiveProto که در متغیرهای تصمیم خطی هستند. الزامات: * linearCoefficients.ids عناصر VariablesProto.ids هستند. * VariablesProto مشخص نشده با صفر مطابقت دارد. * linearCoefficients.values همه باید محدود باشند. * linearCoefficients.values می تواند صفر باشد، اما این فقط فضا را هدر می دهد. |
quadraticCoefficients | اصطلاحات عینی که در متغیرهای تصمیم درجه دوم هستند. الزامات علاوه بر موارد موجود در پیام های SparseDoubleMatrixProto: * هر عنصر quadraticCoefficients.row_ids و هر عنصر quadraticCoefficients.column_ids باید عنصری از VariablesProto.ids باشد. * ماتریس باید مثلث بالایی باشد: برای هر i، quadraticCoefficients.row_ids[i] <= quadraticCoefficients.column_ids[i]. نکات: * عباراتی که به صراحت ذخیره نشده اند دارای ضریب صفر هستند. * عناصر quadraticCoefficients.coefficients می توانند صفر باشند، اما این فقط فضا را هدر می دهد. |
name | پیامهای والدین ممکن است الزامات منحصربهفردی در این زمینه داشته باشند. به عنوان مثال، ModelProto.objectives و AuxiliaryObjectivesUpdatesProto.new_objectives را ببینید. |
priority | برای مسائل چند هدفه، اولویت این هدف نسبت به سایرین (پایین تر مهمتر است). این مقدار باید غیر منفی باشد. علاوه بر این، هر اولویت هدف در مدل باید در زمان حل متمایز باشد. این شرط در سطح پروتو تایید نشده است، بنابراین مدلها ممکن است به طور موقت اهدافی با همان اولویت داشته باشند. |
SparseDoubleVectorProto
یک نمایش پراکنده از یک بردار دو برابری.
نمایندگی JSON |
---|
{ "ids": [ string ], "values": [ number ] } |
زمینه های | |
---|---|
ids[] | باید (در ترتیب افزایشی) با همه عناصر متمایز مرتب شود. |
values[] | باید طول برابر با شناسه داشته باشد. ممکن است حاوی NaN نباشد. |
SparseDoubleMatrixProto
یک نمایش پراکنده از یک ماتریس از دو برابر.
ماتریس به صورت سه گانه شناسه ردیف، شناسه ستون و ضریب ذخیره می شود. این سه بردار باید دارای طول مساوی باشند. برای همه i، تاپل (rowIds[i]، columnIds[i]) باید متمایز باشد. ورودی ها باید به ترتیب اصلی باشند.
نمایندگی JSON |
---|
{ "rowIds": [ string ], "columnIds": [ string ], "coefficients": [ number ] } |
زمینه های | |
---|---|
rowIds[] | |
columnIds[] | |
coefficients[] | ممکن است حاوی NaN نباشد. |
LinearConstraintsProto
همانطور که در زیر استفاده می شود، "# محدودیت های خطی" = اندازه (LinearConstraintsProto.ids) را تعریف می کنیم.
نمایندگی JSON |
---|
{ "ids": [ string ], "lowerBounds": [ number ], "upperBounds": [ number ], "names": [ string ] } |
زمینه های | |
---|---|
ids[] | باید غیرمنفی و به شدت افزایش یابد. مقدار max(int64) را نمی توان استفاده کرد. |
lowerBounds[] | باید طولی برابر با #محدودیت های خطی داشته باشد، مقادیر در [-inf، inf). |
upperBounds[] | باید دارای طول برابر با #محدودیت های خطی، مقادیر در (-inf، inf] باشد. |
names[] | اگر تنظیم نشده باشد، فرض می شود که همه رشته ها خالی هستند. در غیر این صورت، باید طولی برابر با #قیود خطی داشته باشد. همه نامهای خالی باید متمایز باشند. |
QuadraticConstraintProto
یک قید درجه دوم به شکل: lb <= sum{linearTerms} + sum{quadraticTerms} <= ub.
اگر متغیری که در این محدودیت دخیل است حذف شود، به گونه ای رفتار می شود که گویی روی صفر تنظیم شده است.
نمایندگی JSON |
---|
{ "linearTerms": { object ( |
زمینه های | |
---|---|
linearTerms | اصطلاحاتی که در متغیرهای تصمیم خطی هستند. علاوه بر الزامات پیامهای SparseDoubleVectorProto، ما نیاز داریم که: * linearTerms.ids عناصر VariablesProto.ids باشد. * linearTerms.values باید همه محدود باشند و NaN نباشند. نکات: * شناسه های متغیر حذف شده دارای ضریب مربوطه صفر هستند. * linearTerms.values می تواند صفر باشد، اما این فقط فضا را هدر می دهد. |
quadraticTerms | اصطلاحاتی که در متغیرهای تصمیم گیری درجه دوم هستند. علاوه بر الزامات پیامهای SparseDoubleMatrixProto، ما نیاز داریم که: * هر عنصر quadraticTerms.row_ids و هر عنصر quadraticTerms.column_ids باید عنصری از VariablesProto.ids باشد. * ماتریس باید مثلث بالایی باشد: برای هر i، quadraticTerms.row_ids[i] <= quadraticTerms.column_ids[i]. نکات: * عباراتی که به صراحت ذخیره نشده اند دارای ضریب صفر هستند. * عناصر quadraticTerms.coefficients می توانند صفر باشند، اما این فقط فضا را هدر می دهد. |
lowerBound | باید مقدار [-inf، inf) داشته باشد و کمتر یا مساوی با |
upperBound | باید مقدار (-inf، inf] داشته باشد و بزرگتر یا مساوی |
name | پیامهای والدین ممکن است الزامات منحصربهفردی در این زمینه داشته باشند. به عنوان مثال، ModelProto.quadratic_constraints و QuadraticConstraintUpdatesProto.new_constraints را ببینید. |
SecondOrderConeConstraintProto
یک محدودیت مخروط مرتبه دوم منفرد از فرم:
|| argumentsToNorm
||_2 <= upperBound
,
که در آن upperBound
و هر عنصر argumentsToNorm
عبارات خطی هستند.
اگر متغیری که در این محدودیت دخیل است حذف شود، به گونه ای رفتار می شود که گویی روی صفر تنظیم شده است.
نمایندگی JSON |
---|
{ "upperBound": { object ( |
زمینه های | |
---|---|
upperBound | |
argumentsToNorm[] | |
name | پیامهای والدین ممکن است الزامات منحصربهفردی در این زمینه داشته باشند. به عنوان مثال، |
LinearExpressionProto
یک نمایش پراکنده از یک عبارت خطی (مجموع وزنی متغیرها، به اضافه یک افست ثابت).
نمایندگی JSON |
---|
{ "ids": [ string ], "coefficients": [ number ], "offset": number } |
زمینه های | |
---|---|
ids[] | شناسه متغیرها باید (در ترتیب افزایشی) با همه عناصر متمایز مرتب شود. |
coefficients[] | باید طول برابر با شناسه داشته باشد. مقادیر باید محدود باشند ممکن است NaN نباشند. |
offset | باید محدود باشد و ممکن است NaN نباشد. |
SosConstraintProto
داده هایی برای نمایش یک محدودیت SOS1 یا SOS2.
اگر متغیری که در این محدودیت دخیل است حذف شود، به گونه ای رفتار می شود که گویی روی صفر تنظیم شده است.
نمایندگی JSON |
---|
{
"expressions": [
{
object ( |
زمینه های | |
---|---|
expressions[] | عباراتی که بر روی آنها محدودیت SOS اعمال می شود: * SOS1: حداکثر یک عنصر یک مقدار غیر صفر می گیرد. * SOS2: حداکثر دو عنصر مقادیر غیر صفر می گیرند و در مرتب سازی مکرر باید مجاور باشند. |
weights[] | یا خالی یا با طول عبارات. اگر خالی باشد، وزنهای پیشفرض 1، 2، ... هستند، ورودیها باید منحصربهفرد باشند. |
name | پیامهای والدین ممکن است الزامات منحصربهفردی در این زمینه داشته باشند. به عنوان مثال، ModelProto.sos1_constraints و SosConstraintUpdatesProto.new_constraints را ببینید. |
IndicatorConstraintProto
داده هایی برای نمایش یک محدودیت نشانگر واحد از فرم: متغیر(indicatorId) = (activateOnZero ? 0 : 1) ⇒ lowBound <= عبارت <= upperBound.
اگر متغیری که در این محدودیت دخیل است (اعم از نشانگر یا ظاهر شده در expression
) حذف شود، به گونه ای رفتار می شود که گویی روی صفر تنظیم شده است. به طور خاص، حذف متغیر نشانگر به این معنی است که اگر activateOnZero
نادرست باشد، محدودیت نشانگر خالی است، و اگر activateOnZero
درست باشد، معادل یک محدودیت خطی است.
نمایندگی JSON |
---|
{
"activateOnZero": boolean,
"expression": {
object ( |
زمینه های | |
---|---|
activateOnZero | اگر درست باشد، اگر متغیر نشانگر مقدار 0 را بگیرد، محدودیت ضمنی باید حفظ شود. در غیر این صورت، اگر متغیر نشانگر مقدار 1 را بگیرد، محدودیت ضمنی باید برقرار باشد. |
expression | باید یک عبارت خطی معتبر با توجه به مدل حاوی باشد: * همه شرایط بیان شده در |
lowerBound | باید مقدار [-inf, inf) داشته باشد. نمی تواند NaN باشد. |
upperBound | باید مقدار (-inf، inf) داشته باشد؛ نمی تواند NaN باشد. |
name | پیامهای والدین ممکن است الزامات منحصربهفردی در این زمینه داشته باشند. به عنوان مثال، |
indicatorId | شناسه مربوط به یک متغیر باینری یا تنظیم نشده است. اگر تنظیم نشده باشد، محدودیت نشانگر نادیده گرفته می شود. اگر تنظیم شود، ما نیاز داریم که: * VariablesProto.integers[indicatorId] = true، * VariablesProto.lower_bounds[indicatorId] >= 0، * VariablesProto.upper_bounds[indicatorId] <= 1. این شرایط توسط MathOpt تأیید نمی شوند، اما اگر تأیید نمی شود رضایت منجر به این می شود که حل کننده هنگام حل یک خطا را برگرداند. |
SolveParametersProto
پارامترهایی برای کنترل یک حل واحد.
شامل هر دو پارامتر مشترک برای همه حل کننده ها به عنوان مثال timeLimit، و پارامترهای یک حل کننده خاص، به عنوان مثال gscip. اگر مقداری هم در فیلد مشترک و هم در فیلد مخصوص حل کننده تنظیم شود، از تنظیم خاص حل کننده استفاده می شود.
پارامترهای رایجی که اختیاری و تنظیم نشده یا یک عدد با مقدار نامشخص هستند، نشان میدهند که از پیشفرض حلکننده استفاده میشود.
پارامترهای خاص حل کننده برای حل کننده هایی غیر از مورد استفاده نادیده گرفته می شوند.
پارامترهایی که به مدل بستگی دارند (به عنوان مثال اولویت انشعاب برای هر متغیر تنظیم شده است) در ModelSolveParametersProto ارسال می شوند.
نمایندگی JSON |
---|
{ "timeLimit": string, "enableOutput": boolean, "lpAlgorithm": enum ( |
زمینه های | |
---|---|
timeLimit | حداکثر زمانی که یک حل کننده باید برای مسئله صرف کند (یا بی نهایت اگر تنظیم نشده باشد). این مقدار محدودیت سختی نیست، زمان حل ممکن است کمی بیشتر از این مقدار باشد. این پارامتر همیشه به حل کننده اصلی ارسال می شود، پیش فرض حل کننده استفاده نمی شود. مدت زمان در ثانیه با حداکثر نه رقم کسری که با ' |
enableOutput | چاپ ردپای پیاده سازی حل کننده را فعال می کند. مکان آن آثار به حل کننده بستگی دارد. برای SCIP و Gurobi این جریان خروجی استاندارد خواهد بود. برای Glop و CP-SAT این LOG (INFO) خواهد بود. توجه داشته باشید که اگر حل کننده از callback پیام پشتیبانی می کند و کاربر برای آن یک callback ثبت می کند، این مقدار پارامتر نادیده گرفته می شود و هیچ اثری چاپ نمی شود. |
lpAlgorithm | الگوریتم حل یک برنامه خطی اگر LP_ALGORITHM_UNSPECIFIED، از الگوریتم پیش فرض حل کننده استفاده کنید. برای مسائلی که برنامههای خطی نیستند اما برنامهنویسی خطی یک زیر روال است، حلکنندهها ممکن است از این مقدار استفاده کنند. به عنوان مثال، حل کننده های MIP معمولاً از این فقط برای حل ریشه LP استفاده می کنند (و در غیر این صورت از دو سیمپلکس استفاده می کنند). |
presolve | قبل از شروع الگوریتم اصلی یا سطح تلاش پیشفرض حلکننده در صورت EMPHASIS_UNSPECIFIED، سعی کنید مشکل را ساده کنید. |
cuts | در صورت EMPHASIS_UNSPECIFIED، برای ایجاد آرامش LP قویتر (فقط MIP)، یا سطح تلاش پیشفرض حلکننده تلاش کنید. توجه: غیرفعال کردن برشها ممکن است مانع از فرصتی برای افزودن برشها در MIP_NODE شود، این رفتار مخصوص حلکننده است. |
heuristics | تلاش برای یافتن راهحلهای امکانپذیر فراتر از راهحلهایی که در روش جستجوی کامل (فقط MIP)، یا سطح تلاش پیشفرض حلکننده در صورت EMPHASIS_UNSPECIFIED مواجه میشوند. |
scaling | در صورت EMPHASIS_UNSPECIFIED، تلاش برای تغییر مقیاس مسئله برای بهبود پایداری عددی، یا سطح تلاش پیشفرض حلکننده. |
iterationLimit | محدودیت در تکرارهای الگوریتم زیربنایی (مثلاً محورهای سیمپلکس). رفتار خاص به حل کننده و الگوریتم مورد استفاده بستگی دارد، اما اغلب می تواند یک حد تعیین کننده حل ارائه دهد (ممکن است پیکربندی بیشتری مورد نیاز باشد، به عنوان مثال یک رشته). به طور معمول توسط حل کننده های LP، QP و MIP پشتیبانی می شود، اما برای حل کننده های MIP نیز به nodeLimit مراجعه کنید. |
nodeLimit | محدودیت در تعداد زیرمسائل حل شده در جستجوی شمارشی (به عنوان مثال شاخه و کران). برای بسیاری از حلکنندهها، میتوان از آن برای محدود کردن محاسبات به طور قطعی استفاده کرد (ممکن است پیکربندی بیشتری مورد نیاز باشد، مثلاً یک رشته). به طور معمول برای حل کننده های MIP، iterationLimit را نیز ببینید. |
cutoffLimit | اگر بتواند ثابت کند که هیچ راه حل اولیه ای حداقل به خوبی قطعی وجود ندارد، حل کننده زود متوقف می شود. در توقف اولیه، حل کننده دلیل خاتمه NO_SOLUTION_FOUND و با محدودیت CUTOFF را برمی گرداند و نیازی به ارائه اطلاعات راه حل اضافی ندارد. اگر توقف اولیه وجود نداشته باشد، تأثیری بر مقدار بازگشتی ندارد. توصیه می شود در صورتی که می خواهید راه حل هایی با هدف دقیقاً برابر با برش بازگردانده شوند، از تلورانس استفاده کنید. برای جزئیات بیشتر و مقایسه با bestBoundLimit به راهنمای کاربر مراجعه کنید. |
objectiveLimit | حل کننده به محض اینکه راه حلی حداقل به این خوبی پیدا کند زود متوقف می شود، با دلیل خاتمه عملی و محدودیت هدف. |
bestBoundLimit | به محض اینکه ثابت کرد بهترین کران حداقل این خوب است، با دلیل خاتمه FEASIBLE یا NO_SOLUTION_FOUND و محدودیت OBJECTIVE، حل کننده زود متوقف می شود. برای جزئیات بیشتر و مقایسه با cutoffLimit به راهنمای کاربر مراجعه کنید. |
solutionLimit | حلکننده پس از یافتن این تعداد راهحل امکانپذیر، با دلیل خاتمه امکان پذیر و راه حل محدود، زود متوقف میشود. در صورت تنظیم باید بزرگتر از صفر باشد. اغلب از آن استفاده می شود تا حل کننده در اولین راه حل عملی یافت شده متوقف شود. توجه داشته باشید که هیچ تضمینی در مورد مقدار هدف برای هیچ یک از راه حل های برگشتی وجود ندارد. حلکنندهها معمولاً راهحلهای بیشتری از حد راهحل را بر نمیگردانند، اما این مورد توسط MathOpt اعمال نمیشود، همچنین به b/214041169 مراجعه کنید. در حال حاضر برای Gurobi و SCIP و فقط برای CP-SAT با مقدار 1 پشتیبانی می شود. |
threads | اگر تنظیم شود، باید >= 1 باشد. |
randomSeed | بذر برای مولد اعداد شبه تصادفی در حل کننده اصلی. توجه داشته باشید که همه حلکنندهها از اعداد شبه تصادفی برای انتخاب مواردی مانند اغتشاش در الگوریتم 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، randomSeed)) دریافت می کند. |
absoluteGapTolerance | یک تحمل بهینه مطلق (در درجه اول) برای حل کننده های MIP. GAP مطلق قدر مطلق تفاوت بین: * مقدار عینی بهترین راه حل ممکن یافت شده، * کران دوگانه تولید شده توسط جستجو است. حلکننده میتواند زمانی که GAP مطلق حداکثر ToleranceGap مطلق باشد (در صورت تنظیم) متوقف شود و TERMINATION_REASON_OPTIMAL را برگرداند. در صورت تنظیم باید >= 0 باشد. همچنین relativeGapTolerance را ببینید. |
relativeGapTolerance | تحمل بهینه نسبی (در درجه اول) برای حل کننده های MIP. GAP نسبی یک نسخه نرمال شده از GAP مطلق است (تعریف شده در absoluteGapTolerance)، که در آن عادی سازی وابسته به حل کننده است، به عنوان مثال شکاف مطلق تقسیم بر مقدار هدف بهترین راه حل ممکن یافت شده. زمانی که GAP نسبی حداکثر نسبیGapTolerance (در صورت تنظیم) شد، حل کننده می تواند متوقف شود و TERMINATION_REASON_OPTIMAL را برگرداند. در صورت تنظیم باید >= 0 باشد. AbsoluteGapTolerance را نیز ببینید. |
solutionPoolSize | در حین جستجو، راه حل های |
LPAlgorithmProto
الگوریتمی را برای حل برنامه های خطی انتخاب می کند.
Enums | |
---|---|
LP_ALGORITHM_UNSPECIFIED | |
LP_ALGORITHM_PRIMAL_SIMPLEX | روش سیمپلکس (اولیه). معمولاً میتواند راهحلهای اولیه و دوگانه، پرتوهای اولیه/دوگانه بر روی مسائل نامحدود اولیه/دوگانه و پایه ارائه کند. |
LP_ALGORITHM_DUAL_SIMPLEX | روش دو سیمپلکس معمولاً میتواند راهحلهای اولیه و دوگانه، پرتوهای اولیه/دوگانه بر روی مسائل نامحدود اولیه/دوگانه و پایه ارائه کند. |
LP_ALGORITHM_BARRIER | روش مانع که معمولاً روش نقطه داخلی (IPM) نیز نامیده می شود. به طور معمول می تواند هر دو راه حل اولیه و دوگانه ارائه دهد. برخی از پیادهسازیها همچنین میتوانند اشعههایی را روی مشکلات نامحدود/غیرقابل اجرا تولید کنند. مبنایی داده نمی شود مگر اینکه حل کننده اصلی "تقاطع" را انجام دهد و با سیمپلکس تمام کند. |
LP_ALGORITHM_FIRST_ORDER | یک الگوریتم مبتنی بر یک روش مرتبه اول. اینها معمولاً راهحلهای اولیه و دوگانه و به طور بالقوه گواهیهای غیرممکن اولیه و/یا دوگانه را تولید میکنند. روشهای مرتبه اول معمولاً راهحلهایی را با دقت پایینتری ارائه میکنند، بنابراین کاربران باید مراقب تنظیم پارامترهای کیفیت راهحل (مثلاً تحملها) و اعتبارسنجی راهحلها باشند. |
تاکید 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 |
ModelSolveParametersProto
نمایندگی JSON |
---|
{ "variableValuesFilter": { object ( |
زمینه های | |
---|---|
variableValuesFilter | فیلتری که برای همه ظروف پراکنده برگشتی که توسط متغیرهای PrimalSolutionProto و PrimalRayProto کلید میخورند (PrimalSolutionProto.variable_values، PrimalRayProto.variable_values) اعمال میشود. الزامات: * filteredIds عناصر VariablesProto.ids هستند. |
dualValuesFilter | فیلتری که روی همه ظروف پراکنده برگشتی اعمال میشود که با محدودیتهای خطی در DualSolutionProto و DualRay (DualSolutionProto.dual_values، DualRay.dual_values) کلید شدهاند. الزامات: * filteredIds عناصر LinearConstraints.ids هستند. |
reducedCostsFilter | فیلتری که برای همه ظروف پراکنده برگشتی که توسط متغیرهای DualSolutionProto و DualRay کلید میخورند (DualSolutionProto.reduced_costs، DualRay.reduced_costs) اعمال میشود. الزامات: * filteredIds عناصر VariablesProto.ids هستند. |
initialBasis | مبنای اولیه اختیاری برای حلگرهای LP سیمپلکس با شروع گرم. در صورت تنظیم، انتظار می رود مطابق |
solutionHints[] | نکات راه حل اختیاری اگر حل کننده اصلی فقط یک اشاره را بپذیرد، از اولین اشاره استفاده می شود. |
branchingPriorities | اولویت های انشعاب اختیاری ابتدا متغیرهایی با مقادیر بالاتر منشعب می شوند. متغیرهایی که اولویت برای آنها تنظیم نشده است، اولویت پیش فرض حل کننده (معمولاً صفر) را دریافت می کنند. الزامات: * branchingPriorities.values باید محدود باشد. * branchingPriorities.ids باید عناصر VariablesProto.ids باشد. |
SparseVectorFilterProto
این پیام اجازه می دهد تا بخش های خاصی از یک SparseXxxxVector را پرس و جو/تنظیم کنید. رفتار پیش فرض این است که چیزی را فیلتر نکنید. یک کاربرد رایج این است که فقط بخشهایی از راهحلها را پرس و جو کنید (فقط مقادیر غیر صفر، و/یا فقط مجموعهای از مقادیر متغیر دستچین شده).
نمایندگی JSON |
---|
{ "skipZeroValues": boolean, "filterByIds": boolean, "filteredIds": [ string ] } |
زمینه های | |
---|---|
skipZeroValues | برای SparseBoolVectorProto "صفر" |
filterByIds | وقتی درست است، فقط مقادیر مربوط به شناسه های فهرست شده در filteredIds را برگردانید. |
filteredIds[] | لیست شناسه هایی که باید در زمانی که filterByIds درست است استفاده کنید. وقتی filterByIds نادرست است، باید خالی باشد. توجه: اگر این خالی باشد و filterByIds درست باشد، میگویید که هیچ اطلاعاتی در نتیجه نمیخواهید. |
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 را نیز برآورده کند، راه حل اساسی عملی نامیده می شود.
نمایندگی JSON |
---|
{ "constraintStatus": { object ( |
زمینه های | |
---|---|
constraintStatus | وضعیت پایه محدودیت الزامات: * constraintStatus.ids برابر با LinearConstraints.ids است. |
variableStatus | وضعیت پایه متغیر الزامات: * constraintStatus.ids برابر با VariablesProto.ids است. |
basicDualFeasibility | این یک ویژگی پیشرفته است که توسط MathOpt برای توصیف امکانسنجی راهحلهای LP کمتر از حد بهینه استفاده میشود (راهحلهای بهینه همیشه وضعیت SOLUTION_STATUS_FEASIBLE را خواهند داشت). برای LP های یک طرفه باید با وضعیت امکان سنجی راه حل دوگانه مرتبط برابر باشد. برای LP های دو طرفه ممکن است در برخی از موارد لبه متفاوت باشد (مثلاً حل های ناقص با سیمپلکس اولیه). اگر پایه شروع را از طریق ModelSolveParametersProto.initial_basis ارائه می کنید، این مقدار نادیده گرفته می شود. این فقط مربوط به پایه ای است که توسط SolutionProto.basis برگردانده شده است. |
SparseBasisStatusVector
یک نمایش پراکنده از یک بردار از وضعیت های پایه.
نمایندگی JSON |
---|
{
"ids": [
string
],
"values": [
enum ( |
زمینه های | |
---|---|
ids[] | باید (در ترتیب افزایشی) با همه عناصر متمایز مرتب شود. |
values[] | باید طول برابر با شناسه داشته باشد. |
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 | متغیر/محدودیت اساسی است. |
SolutionStatusProto
امکان سنجی یک راه حل اولیه یا دوگانه همانطور که توسط حل کننده ادعا شده است.
Enums | |
---|---|
SOLUTION_STATUS_UNSPECIFIED | مقدار گارد نشان دهنده وضعیتی نیست. |
SOLUTION_STATUS_UNDETERMINED | حل کننده وضعیت امکان سنجی را ادعا نمی کند. |
SOLUTION_STATUS_FEASIBLE | Solver ادعا می کند که راه حل امکان پذیر است. |
SOLUTION_STATUS_INFEASIBLE | Solver ادعا می کند که راه حل غیر ممکن است. |
SolutionHintProto
یک راه حل شروع پیشنهادی برای حل کننده.
حلکنندههای MIP معمولاً فقط اطلاعات اولیه ( variableValues
) را میخواهند، در حالی که حلکنندههای LP هم اطلاعات اولیه و هم اطلاعات دوگانه ( dualValues
) را میخواهند.
بسیاری از حل کننده های MIP می توانند با موارد زیر کار کنند: (1) راه حل های جزئی که همه متغیرها را مشخص نمی کنند یا (2) راه حل های غیرقابل اجرا. در این موارد، حلکنندهها معمولاً یک MIP فرعی را برای تکمیل/تصحیح راهنمایی حل میکنند.
نحوه استفاده از اشاره توسط حل کننده، اگر اصلاً باشد، بسیار به حل کننده، نوع مسئله و الگوریتم مورد استفاده بستگی دارد. مطمئنترین راه برای اطمینان از تأثیر راهنمایی شما، خواندن گزارشهای حلکننده اصلی با و بدون اشاره است.
حلکنندههای LP مبتنی بر Simplex معمولاً یک مبنای اولیه را به یک اشاره راهحل ترجیح میدهند (آنها برای تبدیل راهنمایی به یک راهحل اساسی اساسی نیاز به متقاطع دارند در غیر این صورت).
نمایندگی JSON |
---|
{ "variableValues": { object ( |
زمینه های | |
---|---|
variableValues | یک انتساب احتمالاً جزئی از مقادیر به متغیرهای اولیه مسئله. الزامات مستقل از حل کننده برای این پیام فرعی عبارتند از: * variableValues.ids عناصر VariablesProto.ids هستند. * variableValues.values همه باید محدود باشند. |
dualValues | تخصیص (بالقوه جزئی) مقادیر به قیود خطی مسئله. الزامات: * dualValues.ids عناصر LinearConstraintsProto.ids هستند. * dualValues.values همه باید محدود باشند. |
SparseInt32VectorProto
یک نمایش پراکنده از یک بردار ints.
نمایندگی JSON |
---|
{ "ids": [ string ], "values": [ integer ] } |
زمینه های | |
---|---|
ids[] | باید (در ترتیب افزایشی) با همه عناصر متمایز مرتب شود. |
values[] | باید طول برابر با شناسه داشته باشد. |
SolveResultProto
قرارداد زمانی که راه حل ها/پرتوهای اولیه/دوگانه پیچیده است، برای توضیحات کامل به termination_reasons.md مراجعه کنید.
تا زمانی که یک قرارداد دقیق نهایی نشده است، به جای تکیه بر دلیل خاتمه، ایمن ترین کار این است که به سادگی بررسی کنید که آیا یک راه حل/پرتو وجود دارد یا خیر.
نمایندگی JSON |
---|
{ "termination": { object ( |
زمینه های | |
---|---|
termination | دلیل توقف حل کننده |
solutions[] | قرارداد کلی برای ترتیب راهحلهایی که حلکنندههای آینده باید پیادهسازی کنند، این است که به ترتیب زیر سفارش داده شوند: 1. راهحلهایی با یک راهحل امکانپذیر اولیه، که ابتدا بر اساس بهترین هدف اولیه مرتب شدهاند. 2. راه حل های با یک راه حل امکان پذیر دوگانه، به ترتیب با بهترین هدف دوگانه (هدف دوگانه ناشناخته بدترین است) 3. همه راه حل های باقی مانده را می توان به هر ترتیبی برگرداند. |
primalRays[] | مسیرهای بهبود اولیه نامحدود، یا به طور معادل، گواهی عدم امکان دوگانه. معمولاً برای TerminationReasonProtos UNBOUNDED و DUAL_INFEASIBLE ارائه شده است |
dualRays[] | مسیرهای بهبود دوگانه نامحدود، یا به طور معادل، گواهینامه های اولیه غیرممکن. به طور معمول برای TerminationReasonProto INFEASIBLE ارائه می شود. |
solveStats | آمار در مورد فرآیند حل، به عنوان مثال زمان اجرا، تکرار. |
خاتمه پروتو
تمام اطلاعات در مورد اینکه چرا فراخوانی به Solve() خاتمه یافت.
نمایندگی JSON |
---|
{ "reason": enum ( |
زمینه های | |
---|---|
reason | اطلاعات اضافی در |
limit | LIMIT_UNSPECIFIED است مگر اینکه دلیل TERMINATION_REASON_FEASIBLE یا TERMINATION_REASON_NO_SOLUTION_FOUND باشد. همه حل کننده ها همیشه نمی توانند حدی را که باعث خاتمه می شود تعیین کنند، LIMIT_UNDETERMINED زمانی استفاده می شود که علت آن قابل تعیین نباشد. |
detail | اطلاعات اضافی معمولاً حل کننده در مورد خاتمه. |
problemStatus | وضعیت امکان سنجی برای مشکلات اولیه و دوگانه از 18 ژوئیه 2023 این پیام ممکن است وجود نداشته باشد. در صورت عدم وجود، problemStatus را می توان در SolveResultProto.solve_stats یافت. |
objectiveBounds | حدود مقدار هدف بهینه. از 18 ژوئیه 2023 این پیام ممکن است وجود نداشته باشد. در صورت عدم وجود، objectBounds.primal_bound را می توان در SolveResultProto.solve.stats.best_primal_bound و objectBounds.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 | مشکل اولیه یا غیر ممکن است یا نامحدود. جزئیات بیشتر در مورد وضعیت مشکل ممکن است در solveStats.problem_status موجود باشد. توجه داشته باشید که وضعیت نامحدود Gurobi ممکن است در اینجا ترسیم شود. |
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 | الگوریتم به دلیل خطایی که توسط یکی از وضعیت های تعریف شده در بالا پوشش داده نمی شود متوقف شد. هیچ اطلاعات راه حلی در دسترس نیست. |
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 ممکن است حاوی اطلاعات اضافی درباره محدودیت باشد. |
ProblemStatusProto
وضعیت امکان سنجی مسئله اولیه و دوگانه آن (یا دوگانه آرامش مداوم) همانطور که توسط حل کننده ادعا شده است. حل کننده ملزم به بازگرداندن گواهی برای ادعا نیست (مثلاً حل کننده ممکن است بدون برگرداندن یک راه حل امکان پذیر اولیه ادعای امکان سنجی اولیه کند). این وضعیت ترکیبی توصیف جامعی از ادعاهای یک حل کننده در مورد امکان سنجی و نامحدود بودن مسئله حل شده را ارائه می دهد. برای مثال،
- وضعیت امکان پذیر برای مسائل اولیه و دوگانه نشان می دهد که اولیه امکان پذیر و محدود است و احتمالاً راه حل بهینه ای دارد (تضمین شده برای مسائل بدون محدودیت های غیر خطی).
- یک وضعیت امکان پذیر اولیه و یک وضعیت غیرقابل اجرا دوگانه نشان می دهد که مشکل اولیه نامحدود است (یعنی راه حل های دلخواه خوب دارد).
توجه داشته باشید که یک وضعیت غیرقابل اجرا دوگانه به خودی خود (یعنی همراه با یک وضعیت اولیه نامشخص) به این معنی نیست که مشکل اولیه نامحدود است زیرا ممکن است هر دو مشکل غیرقابل اجرا باشند. همچنین، در حالی که یک وضعیت امکان پذیر اولیه و دوگانه ممکن است به وجود یک راه حل بهینه دلالت کند، اما تضمین نمی کند که حل کننده چنین راه حل بهینه ای را پیدا کرده است.
نمایندگی JSON |
---|
{ "primalStatus": enum ( |
زمینه های | |
---|---|
primalStatus | وضعیت برای مشکل اولیه |
dualStatus | وضعیت برای مشکل دوگانه (یا برای دوگانه آرامش مداوم). |
primalOrDualInfeasible | اگر درست باشد، حلکننده ادعا میکند که مشکل اولیه یا دوگانه غیرممکن است، اما نمیداند کدام (یا هر دو غیرممکن هستند). فقط زمانی درست است که primal_problem_status = dual_problem_status = kUndetermined. این اطلاعات اضافی اغلب زمانی مورد نیاز است که پیش پردازش مشخص می کند که راه حل بهینه ای برای مشکل وجود ندارد (اما نمی توان تعیین کرد که آیا به دلیل غیرممکن بودن، نامحدود بودن یا هر دو است). |
FeasibilityStatusProto
وضعیت امکان سنجی مشکل همانطور که توسط حل کننده ادعا شده است (حل کننده نیازی به بازگرداندن گواهی برای ادعا ندارد).
Enums | |
---|---|
FEASIBILITY_STATUS_UNSPECIFIED | مقدار گارد نشان دهنده وضعیتی نیست. |
FEASIBILITY_STATUS_UNDETERMINED | حل کننده مدعی وضعیت نیست. |
FEASIBILITY_STATUS_FEASIBLE | حلال ادعا می کند که مشکل امکان پذیر است. |
FEASIBILITY_STATUS_INFEASIBLE | Solver ادعا می کند که این مشکل غیر ممکن است. |
ObjectiveBoundsProto
حدود مقدار هدف بهینه.
نمایندگی JSON |
---|
{ "primalBound": number, "dualBound": number } |
زمینه های | |
---|---|
primalBound | Solver ادعا می کند که مقدار بهینه برابر یا بهتر است (کوچکتر برای کمینه سازی و بزرگتر برای حداکثر کردن) از primalBound تا تحمل امکان سنجی اولیه حل کننده ها (به هشدار زیر مراجعه کنید): * primalBound بی اهمیت است (+inf برای به حداقل رساندن و -inf حداکثر سازی) زمانی که حل کننده ادعا نمی کند که چنین محدودیتی دارد. * primalBound می تواند به مقدار بهینه نزدیکتر باشد تا هدف بهترین راه حل ممکن اولیه. بهویژه، primalBound ممکن است حتی زمانی که هیچ راهحل اولیه امکانپذیری برگردانده نمیشود، بیاهمیت باشد. هشدار: ادعای دقیق این است که یک راه حل اولیه وجود دارد که: * از نظر عددی امکان پذیر است (یعنی تا حد تحمل حل کننده ها امکان پذیر است)، و * دارای یک مقدار هدف primalBound است. این راه حل عددی امکان پذیر می تواند کمی غیر قابل اجرا باشد، در این صورت primalBound می تواند به شدت بهتر از مقدار بهینه باشد. ترجمه یک تلورانس امکان سنجی اولیه به یک تلورانس در primalBound غیر ضروری است، به خصوص زمانی که تحمل امکان سنجی نسبتاً زیاد است (مثلاً هنگام حل با PDLP). |
dualBound | حلکننده ادعا میکند که مقدار بهینه برابر یا بدتر است (بزرگتر برای کمینهسازی و کوچکتر برای بیشینهسازی) از dualBound تا حلکنندهها تحمل امکانسنجی دوگانه (به هشدار زیر مراجعه کنید): * dualBound بیاهمیت است (-inf برای کمینهسازی و +inf حداکثر کردن) زمانی که حلکننده ادعا نمی کند که چنین محدودیتی دارد. مشابه primalBound، این ممکن است برای برخی از حل کننده ها حتی در هنگام بازگشت بهینه نیز اتفاق بیفتد. حل کننده های MIP معمولاً یک کران را گزارش می کنند حتی اگر نادقیق باشد. * برای مسائل پیوسته dualBound می تواند به مقدار بهینه نزدیکتر از هدف بهترین راه حل امکان پذیر دوگانه باشد. برای MIP یکی از اولین مقادیر غیر ضروری برای dualBound اغلب مقدار بهینه آرامش LP MIP است. * dualBound باید بهتر باشد (برای کمینه سازی کوچکتر و برای حداکثرسازی بزرگتر) از primalBound تا تلورانس های حل کننده (به هشدار زیر مراجعه کنید). هشدار: * برای مسائل پیوسته، ادعای دقیق این است که یک راه حل دوگانه وجود دارد که: * از نظر عددی امکان پذیر است (یعنی تا حد تحمل حل کننده ها امکان پذیر است)، و * دارای مقدار هدف dualBound است. این راه حل عددی امکان پذیر می تواند کمی غیر قابل اجرا باشد، در این صورت dualBound می تواند به شدت بدتر از مقدار بهینه و primalBound باشد. مشابه حالت اولیه، ترجمه یک تحمل امکانسنجی دوگانه به یک تحمل در dualBound، به ویژه زمانی که تحمل امکانسنجی نسبتاً زیاد باشد، غیر ضروری است. با این حال، برخی از حل کننده ها نسخه اصلاح شده dualBound را ارائه می دهند که می تواند از نظر عددی ایمن تر باشد. این نسخه اصلاح شده را می توان از طریق خروجی خاص حل کننده (به عنوان مثال برای PDLP، pdlp_output.convergence_information.corrected_dual_objective) در دسترس قرار داد. * برای حلکنندههای MIP، dualBound ممکن است به یک راهحل دوگانه برای آرامش مداوم (مثلاً آرامش LP) مرتبط باشد، اما اغلب پیامد پیچیدهای از اجرای حلکنندهها است و معمولاً مبهمتر از محدودههای گزارششده توسط حلکنندههای LP است. |
SolutionProto
آنچه در راه حل گنجانده می شود به نوع مشکل و حل کننده بستگی دارد. الگوهای رایج فعلی 1 هستند. حل کننده های MIP فقط یک راه حل اولیه را برمی گرداند. 2. حل کننده های ساده LP اغلب یک مبنا و راه حل های اولیه و دوگانه مرتبط با این مبنا را برمی گردانند. 3. سایر حل کننده های پیوسته اغلب یک راه حل اولیه و دوگانه را که به شکلی وابسته به حل کننده به هم متصل هستند، برمی گردانند.
الزامات: * حداقل یک فیلد باید تنظیم شود. یک راه حل نمی تواند خالی باشد
نمایندگی JSON |
---|
{ "primalSolution": { object ( |
زمینه های | |
---|---|
primalSolution | |
dualSolution | |
basis | |
PrimalSolutionProto
راه حلی برای مسئله بهینه سازی
به عنوان مثال یک برنامه خطی ساده را در نظر بگیرید: min c * x st A * x >= bx >= 0. یک راه حل اولیه مقادیری است که به x نسبت داده می شود. در صورتی امکان پذیر است که A * x >= b و x >= 0 را از بالا برآورده کند. در پیام PrimalSolutionProto زیر، variableValues x و ObjectValue c * x است.
نمایندگی JSON |
---|
{ "variableValues": { object ( |
زمینه های | |
---|---|
variableValues | الزامات: * variableValues.ids عناصر VariablesProto.ids هستند. * variableValues.values همه باید محدود باشند. |
objectiveValue | مقدار عینی که توسط حل کننده اصلی محاسبه می شود. نمی تواند بی نهایت یا NaN باشد. |
auxiliaryObjectiveValues | مقادیر هدف کمکی که توسط حل کننده اصلی محاسبه می شود. کلیدها باید شناسه هدف کمکی معتبر باشند. مقادیر نمی توانند بی نهایت یا NaN باشند. یک شی حاوی لیستی از |
feasibilityStatus | وضعیت امکان سنجی راه حل با توجه به حل کننده اساسی. |
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 مقدار هدف است.
نمایندگی JSON |
---|
{ "dualValues": { object ( |
زمینه های | |
---|---|
dualValues | الزامات: * dualValues.ids عناصر LinearConstraints.ids هستند. * dualValues.values همه باید محدود باشند. |
reducedCosts | الزامات: * smallCosts.ids عناصر VariablesProto.ids هستند. * کاهش هزینه ها. ارزش ها همه باید محدود باشند. |
feasibilityStatus | وضعیت امکان سنجی راه حل با توجه به حل کننده اساسی. |
objectiveValue | |
PrimalRayProto
جهت بهبود نامحدود به یک مسئله بهینه سازی؛ به طور معادل، گواهی عدم امکان برای مسئله دوگانه بهینه سازی.
به عنوان مثال یک برنامه خطی ساده را در نظر بگیرید: min c * x st A * x >= bx >= 0 یک پرتو اولیه یک x است که برآورده می کند: c * x < 0 A * x >= 0 x >= 0 مشاهده کنید که یک امکان پذیر است راه حل، هر مضرب مثبت پرتوی اولیه به اضافه آن راه حل هنوز امکان پذیر است و مقدار هدف بهتری به دست می دهد. یک پرتو اولیه نیز ثابت می کند که مسئله بهینه سازی دوگانه غیرممکن است.
در پیام PrimalRay زیر، variableValues x است.
نمایندگی JSON |
---|
{
"variableValues": {
object ( |
زمینه های | |
---|---|
variableValues | الزامات: * variableValues.ids عناصر VariablesProto.ids هستند. * variableValues.values همه باید محدود باشند. |
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 dualValues و r کاهش هزینه ها است.
نمایندگی JSON |
---|
{ "dualValues": { object ( |
زمینه های | |
---|---|
dualValues | الزامات: * dualValues.ids عناصر LinearConstraints.ids هستند. * dualValues.values همه باید محدود باشند. |
reducedCosts | الزامات: * smallCosts.ids عناصر VariablesProto.ids هستند. * کاهش هزینه ها. ارزش ها همه باید محدود باشند. |
SolveStatsProto
نمایندگی JSON |
---|
{
"solveTime": string,
"problemStatus": {
object ( |
زمینه های | |
---|---|
solveTime | زمان سپری شده ساعت دیواری که با math_opt اندازه گیری می شود، تقریباً زمان داخل Solver::Solve(). توجه: این شامل کار انجام شده در ساخت مدل نمی شود. مدت زمان در ثانیه با حداکثر نه رقم کسری که با ' |
problemStatus | وضعیت امکان سنجی برای مشکلات اولیه و دوگانه |
simplexIterations | |
barrierIterations | |
firstOrderIterations | |
nodeCount | |