Method: mathopt.solveMathOptModel

Решает входную модель и сразу возвращает результат. Используйте это, когда вам не нужны обратные вызовы, инкрементность и не нужно отслеживать ход решения.

HTTP-запрос

POST https://optimization.googleapis.com/v1/mathopt:solveMathOptModel

URL-адрес использует синтаксис транскодирования gRPC .

Тело запроса

Тело запроса содержит данные следующей структуры:

JSON-представление 
{
  "solverType": enum (SolverTypeProto),
  "model": {
    object (ModelProto)
  },
  "parameters": {
    object (SolveParametersProto)
  },
  "modelParameters": {
    object (ModelSolveParametersProto)
  }
}
Поля
solverType

enum ( SolverTypeProto )

Необязательный. Тип решателя для численного решения задачи. Обратите внимание: если решатель не поддерживает определенную функцию модели, процедура оптимизации не будет успешной.

model

object ( ModelProto )

Необходимый. Математическое представление решаемой задачи оптимизации.

parameters

object ( SolveParametersProto )

Необязательный. Параметры для управления одним решением. Параметр EnableOutput обрабатывается особым образом. Для решателей, которые поддерживают обратные вызовы сообщений, установка значения true приведет к тому, что сервер зарегистрирует обратный вызов сообщения. Результирующие сообщения будут возвращены в SolveMathOptModelResponse.messages. Для других решателей установка параметра EnableOutput в значение true приведет к ошибке.

modelParameters

object ( ModelSolveParametersProto )

Необязательный. Параметры для управления одним решением, специфичные для входной модели (см. SolveParametersProto для независимых параметров модели).

Тело ответа

Ответ на унарное удаленное решение в MathOpt.

В случае успеха тело ответа содержит данные следующей структуры:

JSON-представление 
{
  "result": {
    object (SolveResultProto)
  },
  "messages": [
    string
  ]
}
Поля
result

object ( SolveResultProto )

Описание результата решения модели в запросе.

messages[]

string

Если использовался SolveParametersProto.enable_output, он будет содержать сообщения журнала для решателей, которые поддерживают обратные вызовы сообщений.

SolverTypeПрототип

Решатели, поддерживаемые MathOpt.

Перечисления
SOLVER_TYPE_UNSPECIFIED
SOLVER_TYPE_GSCIP

Решатель Solving Constraint Integer Programs (SCIP) (сторонний).

Поддерживает LP, MIP и невыпуклые целочисленные квадратичные задачи. Однако двойные данные для LP не возвращаются. Предпочитайте GLOP для пластинок.

SOLVER_TYPE_GUROBI

Решатель Гуроби (сторонний).

Поддерживает LP, MIP и невыпуклые целочисленные квадратичные задачи. Обычно самый быстрый вариант, но имеет специальную лицензию.

SOLVER_TYPE_GLOP

Решатель Google Glop.

Поддерживает LP с простыми и двойными симплексными методами.

SOLVER_TYPE_CP_SAT

Решатель CP-SAT от Google.

Поддерживает задачи, в которых все переменные являются целочисленными и ограниченными (или подразумеваются после предварительного решения). Экспериментальная поддержка масштабирования и дискретизации задач с непрерывными переменными.

SOLVER_TYPE_PDLP

Решатель PDLP от Google.

Поддерживает LP и выпуклые диагонально-квадратичные цели. Использует методы первого порядка, а не симплексные. Может решить очень большие проблемы.

SOLVER_TYPE_GLPK

GNU Linear Programming Kit (GLPK) (сторонний).

Поддерживает MIP и LP.

Потокобезопасность: GLPK использует локальное хранилище потоков для выделения памяти. Как следствие, экземпляры Solver должны быть уничтожены в том же потоке, в котором они были созданы, иначе GLPK выйдет из строя. Кажется, можно вызывать Solver::Solve() из другого потока, отличного от того, который использовался для создания Solver, но это не документировано GLPK, и его следует избегать.

При решении ЛП с помощью пресольвера решение (и несвязанные лучи) возвращаются только в том случае, если было найдено оптимальное решение. В противном случае ничего не возвращается. Подробности см. на странице 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

Эталонная реализация решателя MIP в MathOpt.

Медленно/не рекомендуется для производства. Не является решателем LP (двойная информация не возвращается).

МодельПрото

Проблема оптимизации. MathOpt поддерживает: - Непрерывные и целочисленные переменные решения с дополнительными конечными границами. - Линейные и квадратичные цели (одна или несколько целей), минимизированные или максимизированные. - Ряд типов ограничений, в том числе: * Линейные ограничения * Квадратичные ограничения * Конусные ограничения второго порядка * Логические ограничения > Ограничения SOS1 и SOS2 > Ограничения индикатора

По умолчанию ограничения представлены в виде карт «id-to-data». Однако мы представляем линейные ограничения в более эффективном формате «структуры массивов».

JSON-представление 
{
  "name": string,
  "variables": {
    object (VariablesProto)
  },
  "objective": {
    object (ObjectiveProto)
  },
  "auxiliaryObjectives": {
    string: {
      object (ObjectiveProto)
    },
    ...
  },
  "linearConstraints": {
    object (LinearConstraintsProto)
  },
  "linearConstraintMatrix": {
    object (SparseDoubleMatrixProto)
  },
  "quadraticConstraints": {
    string: {
      object (QuadraticConstraintProto)
    },
    ...
  },
  "secondOrderConeConstraints": {
    string: {
      object (SecondOrderConeConstraintProto)
    },
    ...
  },
  "sos1Constraints": {
    string: {
      object (SosConstraintProto)
    },
    ...
  },
  "sos2Constraints": {
    string: {
      object (SosConstraintProto)
    },
    ...
  },
  "indicatorConstraints": {
    string: {
      object (IndicatorConstraintProto)
    },
    ...
  }
}
Поля
name

string

variables

object ( VariablesProto )

objective

object ( ObjectiveProto )

Основная цель модели.

auxiliaryObjectives

map (key: string ( int64 format), value: object ( ObjectiveProto ))

Вспомогательные цели для использования в многокритериальных моделях.

Идентификаторы ключей карты должны быть в формате [0, max(int64)). Каждый приоритет и каждое непустое имя должны быть уникальными и отличаться от основной objective .

Объект, содержащий список пар "key": value . Пример: { "name": "wrench", "mass": "1.3kg", "count": "3" } .

linearConstraints

object ( LinearConstraintsProto )

linearConstraintMatrix

object ( SparseDoubleMatrixProto )

Переменные коэффициенты для линейных ограничений.

Если переменная, участвующая в этом ограничении, удаляется, она обрабатывается так, как если бы ей было присвоено нулевое значение.

Требования: * LinearConstraintMatrix.row_ids — это элементы линейногоConstraints.ids. * LinearConstraintMatrix.column_ids — это элементы переменных.ids. * Неуказанные элементы матрицы равны нулю. * Все значения LinearConstraintMatrix.values ​​должны быть конечными.

quadraticConstraints

map (key: string ( int64 format), value: object ( QuadraticConstraintProto ))

Квадратичные ограничения в модели.

Объект, содержащий список пар "key": value . Пример: { "name": "wrench", "mass": "1.3kg", "count": "3" } .

secondOrderConeConstraints

map (key: string ( int64 format), value: object ( SecondOrderConeConstraintProto ))

Конусные ограничения второго порядка в модели.

Объект, содержащий список пар "key": value . Пример: { "name": "wrench", "mass": "1.3kg", "count": "3" } .

sos1Constraints

map (key: string ( int64 format), value: object ( SosConstraintProto ))

Ограничения SOS1 в модели, которые запрещают не более одного expression быть ненулевым. Необязательные записи weights — это деталь реализации, используемая решателем для (надеюсь) более быстрой сходимости. Более подробно, решатели могут (или не могут) использовать эти веса для выбора решений ветвления, которые создают «сбалансированные» дочерние узлы.

Объект, содержащий список пар "key": value . Пример: { "name": "wrench", "mass": "1.3kg", "count": "3" } .

sos2Constraints

map (key: string ( int64 format), value: object ( SosConstraintProto ))

Ограничения SOS2 в модели, которые ограничивают то, что не более двух записей expression могут быть ненулевыми и они должны быть соседними по своему порядку. Если weights не указаны, этот порядок является их линейным порядком в списке expressions ; если представлены weights , то порядок расположения принимается по отношению к этим значениям в порядке возрастания.

Объект, содержащий список пар "key": value . Пример: { "name": "wrench", "mass": "1.3kg", "count": "3" } .

indicatorConstraints

map (key: string ( int64 format), value: object ( IndicatorConstraintProto ))

Ограничения индикатора в модели, которые обеспечивают следующее: если двоичная «переменная индикатора» установлена ​​в единицу, то «подразумеваемое ограничение» должно соблюдаться.

Объект, содержащий список пар "key": value . Пример: { "name": "wrench", "mass": "1.3kg", "count": "3" } .

ПеременныеProto

Как используется ниже, мы определяем «#variables» = size(VariablesProto.ids).

JSON-представление 
{
  "ids": [
    string
  ],
  "lowerBounds": [
    number
  ],
  "upperBounds": [
    number
  ],
  "integers": [
    boolean
  ],
  "names": [
    string
  ]
}
Поля
ids[]

string ( int64 format)

Должно быть неотрицательным и строго возрастающим. Значение max(int64) использовать нельзя.

lowerBounds[]

number

Должна иметь длину, равную #variables, значения в [-inf, inf).

upperBounds[]

number

Должна иметь длину, равную #variables, значениям в (-inf, inf].

integers[]

boolean

Должен иметь длину, равную #variables. Значение false для непрерывных переменных и true для целочисленных переменных.

names[]

string

Если не установлено, предполагается, что все строки пусты. В противном случае длина должна быть равна #variables.

Все непустые имена должны быть разными.

ЦельПрото

JSON-представление 
{
  "maximize": boolean,
  "offset": number,
  "linearCoefficients": {
    object (SparseDoubleVectorProto)
  },
  "quadraticCoefficients": {
    object (SparseDoubleMatrixProto)
  },
  "name": string,
  "priority": string
}
Поля
maximize

boolean

false — минимизировать, true — максимизировать

offset

number

Должно быть конечным, а не NaN.

linearCoefficients

object ( SparseDoubleVectorProto )

Условия ObjectiveProto, линейные по переменным решения.

Требования: * LinearCoefficients.ids являются элементами VariablesProto.ids. * Неуказанные переменныеProto соответствуют нулю. * Все значения linearCoefficients.values ​​должны быть конечными. * LinearCoefficients.values ​​может быть нулевым, но это приведет к пустой трате места.

quadraticCoefficients

object ( SparseDoubleMatrixProto )

Объективные члены, квадратичные по переменным решения.

Требования в дополнение к требованиям к сообщениям SparseDoubleMatrixProto: * Каждый элементquadaticCoefficients.row_ids и каждый элементquadaticCoefficients.column_ids должен быть элементом VariablesProto.ids. * Матрица должна быть верхнетреугольной: для каждого i квадратичные коэффициенты.row_ids[i] <= квадратичныекоэффициенты.column_ids[i].

Примечания: * Термины, не сохраненные явно, имеют нулевой коэффициент. * ЭлементыquadaticCoefficients.coefficients могут быть нулевыми, но это приведет к пустой трате места.

name

string

Родительские сообщения могут иметь требования к уникальности в этом поле; например, см. ModelProto.objectives и AuxiliaryObjectivesUpdatesProto.new_objectives.

priority

string ( int64 format)

Для многокритериальных задач приоритет этой цели относительно других (более важен более низкий). Это значение должно быть неотрицательным. Более того, каждый объективный приоритет в модели должен быть различен во время решения. Это условие не проверяется на уровне прототипа, поэтому модели могут временно иметь цели с тем же приоритетом.

РазреженныйдвойнойВекторныйПрото

Разреженное представление вектора двойников.

JSON-представление 
{
  "ids": [
    string
  ],
  "values": [
    number
  ]
}
Поля
ids[]

string ( int64 format)

Должен быть отсортирован (в порядке возрастания) так, чтобы все элементы были различимы.

values[]

number

Должен иметь одинаковую длину с идентификаторами. Может не содержать NaN.

РазреженныйDoubleMatrixПрото

Разреженное представление матрицы двойников.

Матрица хранится в виде троек идентификатора строки, идентификатора столбца и коэффициента. Эти три вектора должны быть одинаковой длины. Для всех i кортеж (rowIds[i], columnsIds[i]) должен быть различным. Записи должны располагаться в порядке возрастания строк.

JSON-представление 
{
  "rowIds": [
    string
  ],
  "columnIds": [
    string
  ],
  "coefficients": [
    number
  ]
}
Поля
rowIds[]

string ( int64 format)

columnIds[]

string ( int64 format)

coefficients[]

number

Может не содержать NaN.

Линейные ограниченияПрото

Как используется ниже, мы определяем «#linear ограничения» = size(LinearConstraintsProto.ids).

JSON-представление 
{
  "ids": [
    string
  ],
  "lowerBounds": [
    number
  ],
  "upperBounds": [
    number
  ],
  "names": [
    string
  ]
}
Поля
ids[]

string ( int64 format)

Должно быть неотрицательным и строго возрастающим. Значение max(int64) использовать нельзя.

lowerBounds[]

number

Должна иметь длину, равную #linear ограничениям, значениям в [-inf, inf).

upperBounds[]

number

Должна иметь длину, равную #linear ограничениям, значениям в (-inf, inf].

names[]

string

Если не установлено, предполагается, что все строки пусты. В противном случае длина должна быть равна #linear ограничениям.

Все непустые имена должны быть разными.

Квадратичное ограничениеПрото

Единственное квадратичное ограничение вида: lb <= sum{linearTerms} + sum{quadraticTerms} <= ub.

Если переменная, участвующая в этом ограничении, удаляется, она обрабатывается так, как если бы ей было присвоено нулевое значение.

JSON-представление 
{
  "linearTerms": {
    object (SparseDoubleVectorProto)
  },
  "quadraticTerms": {
    object (SparseDoubleMatrixProto)
  },
  "lowerBound": number,
  "upperBound": number,
  "name": string
}
Поля
linearTerms

object ( SparseDoubleVectorProto )

Члены, линейные по переменным решения.

В дополнение к требованиям к сообщениям SparseDoubleVectorProto мы требуем, чтобы: * LinearTerms.ids были элементами VariablesProto.ids. * Все значения LinearTerms.values ​​должны быть конечными и не иметь значения NaN.

Примечания: * Идентификаторы пропущенных переменных имеют соответствующий коэффициент, равный нулю. * LinearTerms.values ​​может быть нулевым, но это приведет к пустой трате места.

quadraticTerms

object ( SparseDoubleMatrixProto )

Члены, квадратичные по переменным решения.

В дополнение к требованиям к сообщениям SparseDoubleMatrixProto мы требуем, чтобы: * Каждый элементquadaticTerms.row_ids и каждый элементquadaticTerms.column_ids должен быть элементом VariablesProto.ids. * Матрица должна быть верхнетреугольной: для каждого i квадратичныйТермс.row_ids[i] <= квадратичныйТермс.столбец_идс[i].

Примечания: * Термины, не сохраненные явно, имеют нулевой коэффициент. * ЭлементыquadaticTerms.coefficients могут быть нулевыми, но это приведет к пустой трате места.

lowerBound

number

Должно иметь значение в [-inf, inf) и быть меньше или равно upperBound .

upperBound

number

Должно иметь значение в (-inf, inf] и быть больше или равно lowerBound .

name

string

Родительские сообщения могут иметь требования к уникальности в этом поле; например, см. ModelProto.quadratic_constraints и QuadraticConstraintUpdatesProto.new_constraints.

SecondOrderConeConstraintProto

Единственное ограничение конуса второго порядка вида:

|| argumentsToNorm ||_2 <= upperBound ,

где upperBound и каждый элемент argumentsToNorm являются линейными выражениями.

Если переменная, участвующая в этом ограничении, удаляется, она обрабатывается так, как если бы ей было присвоено нулевое значение.

JSON-представление 
{
  "upperBound": {
    object (LinearExpressionProto)
  },
  "argumentsToNorm": [
    {
      object (LinearExpressionProto)
    }
  ],
  "name": string
}
Поля
upperBound

object ( LinearExpressionProto )

argumentsToNorm[]

object ( LinearExpressionProto )

name

string

Родительские сообщения могут иметь требования к уникальности в этом поле; например, см. ModelProto.second_order_cone_constraints и SecondOrderConeConstraintUpdatesProto.new_constraints .

ЛинейноеВыражениеПрото

Разреженное представление линейного выражения (взвешенная сумма переменных плюс постоянное смещение).

JSON-представление 
{
  "ids": [
    string
  ],
  "coefficients": [
    number
  ],
  "offset": number
}
Поля
ids[]

string ( int64 format)

Идентификаторы переменных. Должен быть отсортирован (в порядке возрастания) так, чтобы все элементы были различимы.

coefficients[]

number

Должен иметь одинаковую длину с идентификаторами. Значения должны быть конечными и не могут быть NaN.

offset

number

Должно быть конечным и не может быть NaN.

SosConstraintПрото

Данные для представления одного ограничения SOS1 или SOS2.

Если переменная, участвующая в этом ограничении, удаляется, она обрабатывается так, как если бы ей было присвоено нулевое значение.

JSON-представление 
{
  "expressions": [
    {
      object (LinearExpressionProto)
    }
  ],
  "weights": [
    number
  ],
  "name": string
}
Поля
expressions[]

object ( LinearExpressionProto )

Выражения, к которым применяется ограничение SOS: * SOS1: не более одного элемента принимает ненулевое значение. * SOS2: не более двух элементов могут принимать ненулевые значения и должны быть соседними в повторяющемся порядке.

weights[]

number

Либо пустое, либо равной длины выражениям. Если пусто, веса по умолчанию равны 1, 2,... Если они присутствуют, записи должны быть уникальными.

name

string

Родительские сообщения могут иметь требования к уникальности в этом поле; например, см. ModelProto.sos1_constraints и SosConstraintUpdatesProto.new_constraints.

ИндикаторОграничениеПрото

Данные для представления ограничения одного индикатора в форме: Variable(indicatorId) = (activateOnZero? 0: 1) ⇒ LowerBound <= выражение <= UpperBound.

Если переменная, участвующая в этом ограничении (либо индикатор, либо фигурирующая в expression ), удаляется, она обрабатывается так, как если бы ей было присвоено нулевое значение. В частности, удаление индикаторной переменной означает, что ограничение индикатора является пустым, если activateOnZero имеет значение false, и что оно эквивалентно линейному ограничению, если activateOnZero имеет значение true.

JSON-представление 
{
  "activateOnZero": boolean,
  "expression": {
    object (SparseDoubleVectorProto)
  },
  "lowerBound": number,
  "upperBound": number,
  "name": string,
  "indicatorId": string
}
Поля
activateOnZero

boolean

Если это правда, то если индикаторная переменная принимает значение 0, подразумеваемое ограничение должно выполняться. В противном случае, если индикаторная переменная принимает значение 1, подразумеваемое ограничение должно выполняться.

expression

object ( SparseDoubleVectorProto )

Должно быть допустимым линейным выражением относительно содержащейся модели: * Все указанные условия для SparseDoubleVectorProto , * Все элементы expression.values ​​должны быть конечными, * expression.ids являются подмножеством VariablesProto.ids .

lowerBound

number

Должно иметь значение в [-inf, inf); не может быть NaN.

upperBound

number

Должно иметь значение в (-inf, inf]; не может быть NaN.

name

string

Родительские сообщения могут иметь требования к уникальности в этом поле; например, см. ModelProto.indicator_constraints и IndicatorConstraintUpdatesProto.new_constraints .

indicatorId

string ( int64 format)

Идентификатор, соответствующий двоичной переменной, или не установлен. Если не установлено, ограничение индикатора игнорируется. Если установлено, мы требуем, чтобы: * VariablesProto.integers[indicatorId] = true, * VariablesProto.lower_bounds[indicatorId] >= 0, * VariablesProto.upper_bounds[indicatorId] <= 1. Эти условия не проверяются MathOpt, но если нет удовлетворение приведет к тому, что решатель вернет ошибку после решения.

РешитьПараметрыПрототип

Параметры для управления одним решением.

Содержит как параметры, общие для всех решателей, например timeLimit, так и параметры для конкретного решателя, например gscip. Если значение установлено как в общем поле, так и в поле, специфичном для решателя, используется настройка, специфичная для решателя.

Общие параметры, которые являются необязательными и не заданы, или перечисление с неуказанным значением, указывают на то, что используется решатель по умолчанию.

Специфические параметры решателя для решателей, отличных от используемого, игнорируются.

Параметры, зависящие от модели (например, для каждой переменной установлен приоритет ветвления), передаются в ModelSolveParametersProto.

JSON-представление 
{
  "timeLimit": string,
  "enableOutput": boolean,
  "lpAlgorithm": enum (LPAlgorithmProto),
  "presolve": enum (EmphasisProto),
  "cuts": enum (EmphasisProto),
  "heuristics": enum (EmphasisProto),
  "scaling": enum (EmphasisProto),
  "iterationLimit": string,
  "nodeLimit": string,
  "cutoffLimit": number,
  "objectiveLimit": number,
  "bestBoundLimit": number,
  "solutionLimit": integer,
  "threads": integer,
  "randomSeed": integer,
  "absoluteGapTolerance": number,
  "relativeGapTolerance": number,
  "solutionPoolSize": integer
}
Поля
timeLimit

string ( Duration format)

Максимальное время, которое решатель должен потратить на решение задачи (или бесконечное, если не установлено).

Это значение не является жестким пределом, время решения может немного превышать это значение. Этот параметр всегда передается базовому решателю, значение решателя по умолчанию не используется.

Длительность в секундах, содержащая до девяти дробных цифр и оканчивающаяся на « s ». Пример: "3.5s" .

enableOutput

boolean

Включает печать трассировок реализации решателя. Расположение этих следов зависит от решателя. Для SCIP и Gurobi это будут стандартные потоки вывода. Для Glop и CP-SAT это будет LOG(INFO).

Обратите внимание: если решатель поддерживает обратный вызов сообщения и пользователь регистрирует для него обратный вызов, то значение этого параметра игнорируется и трассировки не печатаются.

lpAlgorithm

enum ( LPAlgorithmProto )

Алгоритм решения линейной программы. Если LP_ALGORITHM_UNSPECIFIED, используйте алгоритм решателя по умолчанию.

Для задач, которые не являются линейными программами, но где линейное программирование является подпрограммой, решатели могут использовать это значение. Например, решатели MIP обычно используют это только для решения корневого LP (в противном случае используют двойной симплекс).

presolve

enum ( EmphasisProto )

Усилия по упрощению задачи перед запуском основного алгоритма или уровень усилий решателя по умолчанию, если EMPHASIS_UNSPECIFIED.

cuts

enum ( EmphasisProto )

Усилия по получению более сильного расслабления LP (только MIP) или уровень усилий решателя по умолчанию, если EMPHASIS_UNSPECIFIED.

ПРИМЕЧАНИЕ. отключение разрезов может помешать обратным вызовам добавлять разрезы в MIP_NODE, такое поведение зависит от решателя.

heuristics

enum ( EmphasisProto )

Усилия по поиску возможных решений, выходящие за рамки тех, которые встречаются в полной процедуре поиска (только MIP), или уровень усилий решателя по умолчанию, если EMPHASIS_UNSPECIFIED.

scaling

enum ( EmphasisProto )

Усилия по изменению масштаба задачи для улучшения числовой стабильности или уровень усилий решателя по умолчанию, если EMPHASIS_UNSPECIFIED.

iterationLimit

string ( int64 format)

Ограничение на итерации базового алгоритма (например, симплексные повороты). Конкретное поведение зависит от используемого решателя и алгоритма, но часто может давать детерминированный предел решения (может потребоваться дополнительная настройка, например, один поток).

Обычно поддерживается решателями LP, QP и MIP, но для решателей MIP см. также nodeLimit.

nodeLimit

string ( int64 format)

Ограничение на количество подзадач, решаемых при перечислительном поиске (например, ветвей и границ). Для многих решателей это может использоваться для детерминированного ограничения вычислений (может потребоваться дополнительная настройка, например, один поток).

Обычно для решателей MIP см. также iterationLimit.

cutoffLimit

number

Решатель останавливается раньше, если может доказать, что не существует простых решений, по крайней мере столь же хороших, как отсечение.

При ранней остановке решатель возвращает причину завершения NO_SOLUTION_FOUND и предел CUTOFF, и ему не требуется предоставлять какую-либо дополнительную информацию о решении. Не влияет на возвращаемое значение, если нет ранней остановки.

Рекомендуется использовать допуск, если вы хотите, чтобы возвращались решения с целью, точно равной отсечению.

Более подробную информацию и сравнение с bestBoundLimit можно найти в руководстве пользователя.

objectiveLimit

number

Решающая программа останавливается раньше, как только находит решение, по крайней мере, этого хорошего, с причиной завершения ВЫПОЛНЕННОЙ и ограничивающей ЦЕЛЬ.

bestBoundLimit

number

Решающая программа останавливается раньше, как только доказывает, что наилучшая граница по крайней мере настолько хороша, с причиной завершения FEASIBLE или NO_SOLUTION_FOUND и ограничением OBJECTIVE.

Более подробную информацию и сравнение с CutoffLimit см. в руководстве пользователя.

solutionLimit

integer

Решатель останавливается раньше времени после того, как найдет такое количество возможных решений, с причиной завершения FEASIBLE и пределом SOLUTION. Должно быть больше нуля, если установлено. Часто используется, чтобы решатель остановился на первом найденном возможном решении. Обратите внимание, что нет никакой гарантии объективного значения для любого из возвращенных решений.

Решатели обычно не возвращают больше решений, чем предел решений, но MathOpt не обеспечивает этого, см. также b/214041169.

В настоящее время поддерживается для Gurobi и SCIP, а для CP-SAT только со значением 1.

threads

integer

Если установлено, оно должно быть >= 1.

randomSeed

integer

Начальное значение для генератора псевдослучайных чисел в базовом решателе. Обратите внимание, что все решатели используют псевдослучайные числа для выбора таких вещей, как возмущение в алгоритме LP, для правил разделения связей и для эвристических исправлений. Изменение этого параметра может оказать заметное влияние на поведение решателя.

Хотя все решатели имеют концепцию начальных чисел, обратите внимание, что допустимые значения зависят от фактического решателя. - Гуроби: [0:GRB_MAXINT] (что начиная с Гуроби 9.0 равно 2x10^9). - GSCIP: [0:2147483647] (что равно MAX_INT или kint32max или 2^31-1). - GLOP: [0:2147483647] (то же, что и выше). Во всех случаях решатель получит значение, равное: MAX(0, MIN(MAX_VALID_VALUE_FOR_SOLVER, randSeed)).

absoluteGapTolerance

number

Абсолютный допуск оптимальности (в первую очередь) для решателей MIP.

Абсолютный GAP — это абсолютное значение разницы между: * объективным значением найденного наилучшего возможного решения; * двойной границей, полученной в результате поиска. Решатель может остановиться, как только абсолютный GAP достигнет максимального значения AbsoluteGapTolerance (если он установлен), и вернуть TERMINATION_REASON_OPTIMAL.

Должно быть >= 0, если установлено.

См. также относительныйGapTolerance.

relativeGapTolerance

number

Относительный допуск оптимальности (в первую очередь) для решателей MIP.

Относительный GAP — это нормализованная версия абсолютного GAP (определенного в AbsoluteGapTolerance), где нормализация зависит от решателя, например, абсолютный GAP, разделенный на целевое значение найденного наилучшего возможного решения.

Решающая программа может остановиться, как только относительный GAP достигнет максимального значенияrelativeGapTolerance (если установлено), и вернуть TERMINATION_REASON_OPTIMAL.

Должно быть >= 0, если установлено.

См. также AbsoluteGapTolerance.

solutionPoolSize

integer

Поддерживайте до решений solutionPoolSize во время поиска. Пул решений обычно имеет две функции: (1) Для решателей, которые могут возвращать более одного решения, это ограничивает количество возвращаемых решений. (2) Некоторые решатели могут выполнять эвристику, используя решения из пула решений, поэтому изменение этого значения может повлиять на путь алгоритма. Чтобы заставить решатель заполнить пул решений, например, n лучшими решениями, требуется дополнительная настройка решателя.

LPАлгоритмПрото

Выбирает алгоритм решения линейных программ.

Перечисления
LP_ALGORITHM_UNSPECIFIED
LP_ALGORITHM_PRIMAL_SIMPLEX (Первичный) симплексный метод. Обычно может предоставлять простые и двойственные решения, основные/двойные лучи для простых/двойственных неограниченных задач и базис.
LP_ALGORITHM_DUAL_SIMPLEX Двойной симплексный метод. Обычно может предоставлять простые и двойственные решения, основные/двойные лучи для простых/двойственных неограниченных задач и базис.
LP_ALGORITHM_BARRIER Барьерный метод, также часто называемый методом внутренней точки (IPM). Обычно может давать как первичное, так и двойственное решение. Некоторые реализации также могут создавать лучи для неограниченных/неосуществимых задач. Базис не задается, если базовый решатель не выполняет «пересечение» и не завершает симплекс.
LP_ALGORITHM_FIRST_ORDER Алгоритм, основанный на методе первого порядка. Обычно они дают как первичное, так и двойное решение, а также, возможно, сертификаты первичной и/или двойной неосуществимости. Методы первого порядка обычно дают решения с меньшей точностью, поэтому пользователям следует позаботиться о настройке параметров качества решения (например, допусков) и проверке решений.

АкцентПрото

Уровень усилий, применяемый к дополнительной задаче при решении (см. SolveParametersProto для использования).

Акцент используется для настройки функции решателя следующим образом: * Если решатель не поддерживает эту функцию, всегда будет действительным только UNSPECIFIED, любая другая настройка обычно будет являться ошибкой недопустимого аргумента (некоторые решатели также могут принимать значение OFF). * Если решатель поддерживает эту функцию: - Если установлено значение UNSPECIFIED, используется базовое значение по умолчанию. - Если эту функцию невозможно отключить, команда OFF вернет ошибку. - Если эта функция включена по умолчанию, решатель по умолчанию обычно сопоставляется со значением MEDIUM. - Если эта функция поддерживается, НИЗКИЙ, СРЕДНИЙ, ВЫСОКИЙ и ОЧЕНЬ ВЫСОКИЙ никогда не выдадут ошибку и будут соответствовать их наилучшему совпадению.

Перечисления
EMPHASIS_UNSPECIFIED
EMPHASIS_OFF
EMPHASIS_LOW
EMPHASIS_MEDIUM
EMPHASIS_HIGH
EMPHASIS_VERY_HIGH

МодельРешитьПараметрыПрототип

JSON-представление 
{
  "variableValuesFilter": {
    object (SparseVectorFilterProto)
  },
  "dualValuesFilter": {
    object (SparseVectorFilterProto)
  },
  "reducedCostsFilter": {
    object (SparseVectorFilterProto)
  },
  "initialBasis": {
    object (BasisProto)
  },
  "solutionHints": [
    {
      object (SolutionHintProto)
    }
  ],
  "branchingPriorities": {
    object (SparseInt32VectorProto)
  }
}
Поля
variableValuesFilter

object ( SparseVectorFilterProto )

Фильтр, который применяется ко всем возвращаемым разреженным контейнерам с ключами переменных в PrimalSolutionProto и PrimalRayProto (PrimalSolutionProto.variable_values, PrimalRayProto.variable_values).

Требования: * filteredIds являются элементами VariablesProto.ids.

dualValuesFilter

object ( SparseVectorFilterProto )

Фильтр, который применяется ко всем возвращаемым разреженным контейнерам с ключами линейных ограничений в DualSolutionProto и DualRay (DualSolutionProto.dual_values, DualRay.dual_values).

Требования: * filteredIds являются элементами LinearConstraints.ids.

reducedCostsFilter

object ( SparseVectorFilterProto )

Фильтр, который применяется ко всем возвращаемым разреженным контейнерам с ключами переменных в DualSolutionProto и DualRay (DualSolutionProto.reduced_costs, DualRay.reduced_costs).

Требования: * filteredIds являются элементами VariablesProto.ids.

initialBasis

object ( BasisProto )

Дополнительная начальная основа для теплого запуска симплексных решателей ЛП. Если он установлен, ожидается, что он будет действительным в соответствии с ValidateBasis в validators/solution_validator.h для текущего ModelSummary .

solutionHints[]

object ( SolutionHintProto )

Дополнительные подсказки по решению. Если базовый решатель принимает только одну подсказку, используется первая подсказка.

branchingPriorities

object ( SparseInt32VectorProto )

Необязательные приоритеты ветвления. Переменные с более высокими значениями будут разветвлены в первую очередь. Переменные, для которых не установлены приоритеты, получают приоритет решателя по умолчанию (обычно нулевой).

Требования: * значения BranchingPriorities.values ​​должны быть конечными. * BranchingPriorities.ids должен быть элементом VariablesProto.ids.

РазреженныйВекторФильтрПрото

Это сообщение позволяет запрашивать/устанавливать определенные части SparseXxxxVector. Поведение по умолчанию — ничего не фильтровать. Обычно используется запрос только частей решений (только ненулевых значений и/или только тщательно подобранного набора значений переменных).

JSON-представление 
{
  "skipZeroValues": boolean,
  "filterByIds": boolean,
  "filteredIds": [
    string
  ]
}
Поля
skipZeroValues

boolean

Для SparseBoolVectorProto «ноль» имеет значение false .

filterByIds

boolean

Если это правда, возвращайте только значения, соответствующие идентификаторам, перечисленным в filteredIds.

filteredIds[]

string ( int64 format)

Список идентификаторов, которые будут использоваться, когда filterByIds имеет значение true. Должно быть пустым, если filterByIds имеет значение false. ПРИМЕЧАНИЕ. Если это поле пусто и filterByIds имеет значение true, вы говорите, что вам не нужна какая-либо информация в результате.

БазисПрото

Комбинаторная характеристика решения линейной программы.

Симплексный метод решения линейных программ всегда возвращает «базовое допустимое решение», которое можно комбинаторно описать базисом. Базис назначает BasisStatusProto для каждой переменной и линейного ограничения.

Например, рассмотрим стандартную форму LP: min c * x st A * x = bx >= 0, которая имеет больше переменных, чем ограничений, и с полным рангом строки A.

Пусть n — количество переменных, а m — количество линейных ограничений. Действительная основа для этой проблемы может быть построена следующим образом: * Все ограничения будут иметь статус базы FIXED. * Выберите m переменных так, чтобы столбцы A были линейно независимыми, и присвойте им статус BASIC. * Присвойте статус AT_LOWER остальным n - m переменным.

Базовым решением для этого базиса является уникальное решение A * x = b, в котором все переменные со статусом AT_LOWER зафиксированы на своих нижних границах (все равны нулю). Полученное решение называется базовым допустимым решением, если оно также удовлетворяет условию x >= 0.

JSON-представление 
{
  "constraintStatus": {
    object (SparseBasisStatusVector)
  },
  "variableStatus": {
    object (SparseBasisStatusVector)
  },
  "basicDualFeasibility": enum (SolutionStatusProto)
}
Поля
constraintStatus

object ( SparseBasisStatusVector )

Статус основы ограничения.

Требования: * ограничениеStatus.ids равно LinearConstraints.ids.

variableStatus

object ( SparseBasisStatusVector )

Статус переменной базы.

Требования: * ограничениеStatus.ids равно VariablesProto.ids.

basicDualFeasibility

enum ( SolutionStatusProto )

Это расширенная функция, используемая MathOpt для характеристики возможности неоптимальных решений LP (оптимальные решения всегда будут иметь статус SOLUTION_STATUS_FEASIBLE).

Для односторонних ЛП он должен соответствовать статусу осуществимости соответствующего двойного решения. Для двусторонних ЛП в некоторых крайних случаях это может быть иначе (например, неполные решения с простым симплексом).

Если вы предоставляете начальную основу через ModelSolveParametersProto.initial_basis, это значение игнорируется. Это актуально только для базиса, возвращаемого SolutionProto.basis.

Разреженныйбазисстатусвектор

Разреженное представление вектора базисных состояний.

JSON-представление 
{
  "ids": [
    string
  ],
  "values": [
    enum (BasisStatusProto)
  ]
}
Поля
ids[]

string ( int64 format)

Должен быть отсортирован (в порядке возрастания) так, чтобы все элементы были различимы.

values[]

enum ( BasisStatusProto )

Должен иметь одинаковую длину с идентификаторами.

БазисстатусПрото

Статус переменной/ограничения в основе LP.

Перечисления
BASIS_STATUS_UNSPECIFIED Защитное значение, не представляющее никакого статуса.
BASIS_STATUS_FREE Переменная/ограничение свободна (не имеет конечных границ).
BASIS_STATUS_AT_LOWER_BOUND Переменная/ограничение находится на своей нижней границе (которая должна быть конечной).
BASIS_STATUS_AT_UPPER_BOUND Переменная/ограничение находится на своей верхней границе (которая должна быть конечной).
BASIS_STATUS_FIXED_VALUE Переменная/ограничение имеет одинаковые конечные нижнюю и верхнюю границы.
BASIS_STATUS_BASIC Переменная/ограничение является базовой.

Статус решенияПрото

Осуществимость простого или двойного решения, как утверждает решатель.

Перечисления
SOLUTION_STATUS_UNSPECIFIED Защитное значение, не представляющее никакого статуса.
SOLUTION_STATUS_UNDETERMINED Solver не претендует на статус осуществимости.
SOLUTION_STATUS_FEASIBLE Solver утверждает, что решение осуществимо.
SOLUTION_STATUS_INFEASIBLE Солвер утверждает, что решение невозможно.

РешениеПодсказкаПрото

Предлагаемое стартовое решение для решателя.

Решателям MIP обычно нужна только первичная информация ( variableValues ), тогда как решателям LP нужна как первичная, так и двойная информация ( dualValues ).

Многие решатели MIP могут работать с: (1) частичными решениями, в которых не указаны все переменные, или (2) недопустимыми решениями. В этих случаях решатели обычно решают суб-MIP, чтобы завершить/исправить подсказку.

То, как подсказка используется решателем, если вообще используется, сильно зависит от решателя, типа задачи и используемого алгоритма. Самый надежный способ убедиться, что ваша подсказка подействовала, — это прочитать журналы базовых решателей с подсказкой и без нее.

Решатели LP на основе симплекса обычно предпочитают начальный базис подсказке решения (в противном случае им необходимо пересечение, чтобы преобразовать подсказку в базовое допустимое решение).

JSON-представление 
{
  "variableValues": {
    object (SparseDoubleVectorProto)
  },
  "dualValues": {
    object (SparseDoubleVectorProto)
  }
}
Поля
variableValues

object ( SparseDoubleVectorProto )

Возможно частичное присвоение значений основным переменным задачи. Независимые от решателя требования для этого подсообщения: * переменныеValues.ids являются элементами VariablesProto.ids. * Все переменныеValues.values ​​должны быть конечными.

dualValues

object ( SparseDoubleVectorProto )

(Потенциально частичное) присвоение значений линейным ограничениям задачи.

Требования: * DualValues.ids являются элементами LinearConstraintsProto.ids. * Все значения DualValues.values ​​должны быть конечными.

SparseInt32ВекторПрото

Разреженное представление вектора целых чисел.

JSON-представление 
{
  "ids": [
    string
  ],
  "values": [
    integer
  ]
}
Поля
ids[]

string ( int64 format)

Должны быть отсортированы (в порядке возрастания), чтобы все элементы были различимы.

values[]

integer

Должен иметь одинаковую длину с идентификаторами.

РешитьРезультатПрото

Контракт, когда основное/двойное решение/лучи является сложным, см. полное описание в терминации_reasons.md.

До тех пор, пока точный контракт не будет окончательно оформлен, безопаснее всего просто проверить наличие решения/луча, а не полагаться на причину расторжения.

JSON-представление 
{
  "termination": {
    object (TerminationProto)
  },
  "solutions": [
    {
      object (SolutionProto)
    }
  ],
  "primalRays": [
    {
      object (PrimalRayProto)
    }
  ],
  "dualRays": [
    {
      object (DualRayProto)
    }
  ],
  "solveStats": {
    object (SolveStatsProto)
  }
}
Поля
termination

object ( TerminationProto )

Причина остановки решателя.

solutions[]

object ( SolutionProto )

Общий договор о порядке решений, которые должны реализовать будущие решатели, заключается в следующем: 1. Решения с основным допустимым решением, упорядоченные в первую очередь по наилучшей основной цели. 2. Решения с двойным допустимым решением, упорядоченные по наилучшей двойной цели (неизвестная двойная цель является худшей). 3. Все оставшиеся решения могут быть возвращены в любом порядке.

primalRays[]

object ( PrimalRayProto )

Направления неограниченного первичного улучшения или, что то же самое, двойные сертификаты неосуществимости. Обычно предоставляется для TerminationReasonProtos UNBOUNDED и DUAL_INFEASIBLE.

dualRays[]

object ( DualRayProto )

Направления неограниченного двойного улучшения или, что то же самое, первичные сертификаты неосуществимости. Обычно предоставляется для TerminationReasonProto INFEASIBLE.

solveStats

object ( SolveStatsProto )

Статистика процесса решения, например, время выполнения, итерации.

ПрекращениеПрото

Вся информация о том, почему вызов Solve() был прекращен.

JSON-представление 
{
  "reason": enum (TerminationReasonProto),
  "limit": enum (LimitProto),
  "detail": string,
  "problemStatus": {
    object (ProblemStatusProto)
  },
  "objectiveBounds": {
    object (ObjectiveBoundsProto)
  }
}
Поля
reason

enum ( TerminationReasonProto )

Дополнительная информация в limit , если значение равно TERMINATION_REASON_FEASIBLE или TERMINATION_REASON_NO_SOLUTION_FOUND, подробности см. в limit .

limit

enum ( LimitProto )

Имеет значение LIMIT_UNSPECIFIED, если только причина не TERMINATION_REASON_FEASIBLE или TERMINATION_REASON_NO_SOLUTION_FOUND. Не все решатели всегда могут определить предел, вызвавший прекращение работы. LIMIT_UNDETERMINED используется, когда причина не может быть определена.

detail

string

Дополнительная обычно специфичная для решателя информация о завершении.

problemStatus

object ( ProblemStatusProto )

Статусы осуществимости для первичных и двойственных задач. По состоянию на 18 июля 2023 г. это сообщение может отсутствовать. Если параметр «статус проблемы» отсутствует, его можно найти в SolveResultProto.solve_stats.

objectiveBounds

object ( ObjectiveBoundsProto )

Границы оптимального целевого значения. По состоянию на 18 июля 2023 г. это сообщение может отсутствовать. Если параметр ObjectBounds.primal_bound отсутствует, его можно найти в SolveResultProto.solve.stats.best_primal_bound, а ObjectBounds.dual_bound можно найти в SolveResultProto.solve.stats.best_dual_bound.

ПрекращениеПричинаПрото

Причина завершения вызова Solve().

Перечисления
TERMINATION_REASON_UNSPECIFIED
TERMINATION_REASON_OPTIMAL Найдено доказуемо оптимальное решение (с точностью до числовых допусков).
TERMINATION_REASON_INFEASIBLE Основная задача не имеет возможных решений.
TERMINATION_REASON_UNBOUNDED Основная задача разрешима, и вдоль основного луча можно найти сколь угодно хорошие решения.
TERMINATION_REASON_INFEASIBLE_OR_UNBOUNDED Основная проблема либо неосуществима, либо неограничена. Более подробную информацию о статусе проблемы можно найти в файлеsolveStats.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 Алгоритм остановился из -за ошибки, не покрытой одним из статусов, определенных выше. Информация о решении не доступна.

LimitProto

Когда решает () рано останавливается с возможным завершением прохождения или no_solution_found, конкретный предел, который был достигнут.

Перечисление
LIMIT_UNSPECIFIED Используется в качестве нулевого значения, когда мы не прекращались не из предела (например, завершение_Резон_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 может содержать дополнительную информацию о пределе.

Проблема StatusProto

Статус осуществимости первичной проблемы и ее двойной (или двойной непрерывной релаксации), как утверждается решатель. Решатель не обязан возвращать сертификат на требование (например, решатель может требовать первичной осуществимости без возвращения первичного осуществимого солютуона). Этот комбинированный статус дает исчерпывающее описание претензий решателя о осуществимости и неограничении решения проблемы. Например,

  • Возможный статус для первичных и двойных задач указывает на то, что первичный является возможным и ограниченным и, вероятно, имеет оптимальное решение (гарантированно для проблем без нелинейных ограничений).
  • Первичный осуществимый и двойной невозмутимый статус указывает на то, что первичная проблема не ограничена (т.е. произвольно хорошие решения).

Обратите внимание, что двойной невозмутимый статус сам по себе (т.е. сопровождается неопределенным первичным статусом) не подразумевает, что первичная проблема не является неограниченной, поскольку мы могли бы быть невозможными. Кроме того, хотя первичное и двойное осуществимое статус может означать существование оптимального решения, он не гарантирует, что решатель фактически обнаружил такое оптимальное решение.

Представление JSON 
{
  "primalStatus": enum (FeasibilityStatusProto),
  "dualStatus": enum (FeasibilityStatusProto),
  "primalOrDualInfeasible": boolean
}
Поля
primalStatus

enum ( FeasibilityStatusProto )

Статус для первичной проблемы.

dualStatus

enum ( FeasibilityStatusProto )

Статус для двойной проблемы (или для двойного непрерывного расслабления).

primalOrDualInfeasible

boolean

Если это правда, решатель утверждает, что первичная или двойная проблема невозможна, но он не знает, что (или если оба являются невозможными). Может быть правдой только тогда, когда primal_problem_status = dual_problem_status = kundetermined. Эта дополнительная информация часто необходима, когда предварительная обработка определяет, что нет оптимального решения проблемы (но не может определить, связано ли это из -за нехватки, неограниченности или обоих).

Обязанность Statusproto

Статус технико -экономического обоснования задачи, утверждаемый решателем (решатель не обязан возвращать сертификат на иск).

Перечисление
FEASIBILITY_STATUS_UNSPECIFIED Значение охраны, не представляющее статуса.
FEASIBILITY_STATUS_UNDETERMINED Согласие не претендует на статус.
FEASIBILITY_STATUS_FEASIBLE Согласие утверждает, что проблема возможна.
FEASIBILITY_STATUS_INFEASIBLE Согласие утверждает, что проблема невозможна.

ObjectBoundSproto

Границы на оптимальном объективном значении.

Представление JSON 
{
  "primalBound": number,
  "dualBound": number
}
Поля
primalBound

number

Решатель утверждает, что оптимальное значение равное или лучше (меньше для минимизации и больше для максимизации), чем первичное до толерантности к решателям достойной технико -экономической технике (см. Предупреждение ниже): * Primalbound является тривиальным (+Inf для минимизации и максимизации -Inf), когда решатель является тривиальным не утверждает, что имеет такую ​​границу. * Primalbound может быть ближе к оптимальному значению, чем целью лучшего первичного осуществимого решения. В частности, primalbound может быть нетривиальным, даже если первичные возможные решения не возвращаются. Предупреждение: точное утверждение заключается в том, что существует первичное решение, которое: * является численно осуществимым (то есть возможно до толерантности к решателям), и * имеет объективное значение, первичное. Это численно осуществимое решение может быть немного невозможным, и в этом случае первичное может быть строго лучше, чем оптимальное значение. Преобразование первичной технико-экономической толерантности к толерантности к первичности является нетривиальной, особенно когда толерантность к осуществлению является относительно большой (например, при решении с помощью PDLP).

dualBound

number

Решатель утверждает, что оптимальное значение равно или хуже (больше для минимизации и меньше для максимизации), чем двойная допустимость двойной технико-экономической технической способности (см. Предупреждение ниже): * DualBound является тривиальным (-inf для минимизации и +максимизация INF), когда решатель- не утверждает, что имеет такую ​​границу. Подобно primalbound, это может произойти для некоторых решателей, даже при возвращении оптимального. Решатели MIP, как правило, сообщают о границе, даже если это неточно. * Для непрерывных задач двойной может быть ближе к оптимальному значению, чем цель лучшего двойного осуществимого решения. Для MIP одним из первых нетривиальных значений для двойного, часто является оптимальным значением релаксации LP MIP. * Dualbound должен быть лучше (меньше для минимизации и больше для максимизации), чем первичная допуски решателей (см. Предупреждение ниже). ПРЕДУПРЕЖДЕНИЕ: * Для непрерывных проблем точное утверждение заключается в том, что существует двойное решение, которое: * является численно осуществимым (то есть возможным до толерантности к решателям), и * имеет объективное значение двойным. Это численно осуществимое решение может быть немного невозможным, и в этом случае двойник может быть строго хуже, чем оптимальное значение и первичное. Подобно первичному случаю, трансляция двойной технико-экономической толерантности к устойчивости к двойной среде является нетривиальной, особенно когда толерантность к осуществлению относительно велика. Тем не менее, некоторые решатели предоставляют исправленную версию двойного, который может быть численно более безопасным. Эта исправленная версия можно получить через конкретный выход решателя (например, для PDLP, pdlp_output.convergence_information.corcrected_dual_objective). * Для решателей MIP двойной может быть связан с двойным решением для некоторой непрерывной релаксации (например, расслабление LP), но это часто является сложным следствием выполнения решателей и обычно более неточно, чем границы, сообщаемые решателями LP.

SolutionProto

То, что включено в решение, зависит от проблемы и решателя. Текущие общие закономерности: 1. Решатели MIP возвращают только первичное решение. 2. Simplex Lp решатели часто возвращают основу и первичные и двойные решения, связанные с этой основой. 3. Другие непрерывные решатели часто возвращают первичное и двойное раствор раствора, которые подключены в зависимой от решающей форме.

Требования: * По крайней мере одно поле должно быть установлено; Решение не может быть пустым.

Представление JSON 
{
  "primalSolution": {
    object (PrimalSolutionProto)
  },
  "dualSolution": {
    object (DualSolutionProto)
  },
  "basis": {
    object (BasisProto)
  }
}
Поля
primalSolution

object ( PrimalSolutionProto )

dualSolution

object ( DualSolutionProto )

basis

object ( BasisProto )

PrimalsolutionProto

Решение проблемы оптимизации.

Например, рассмотрим простую линейную программу: min c * x st a * x> = bx> = 0. Первичное решение - это значения назначения в x. Это возможно, если он удовлетворяет a * x> = b и x> = 0 сверху. В сообщении PrimalSolutionProto ниже, variableValues ​​- это x, а объективное значение - C * x.

Представление JSON 
{
  "variableValues": {
    object (SparseDoubleVectorProto)
  },
  "objectiveValue": number,
  "auxiliaryObjectiveValues": {
    string: number,
    ...
  },
  "feasibilityStatus": enum (SolutionStatusProto)
}
Поля
variableValues

object ( SparseDoubleVectorProto )

Требования: * variablevalues.ids - это элементы переменных .proto.ids. * variableValues. Обнаружения должны быть конечными.

objectiveValue

number

Объективное значение, вычисленное базовым решателем. Не может быть бесконечным или Нэн.

auxiliaryObjectiveValues

map (key: string ( int64 format), value: number)

Вспомогательные объективные значения, вычисленные базовым решателем. Ключи должны быть действительными вспомогательными объективными идентификаторами. Значения не могут быть бесконечными или НАН.

Объект, содержащий список "key": value . Пример: { "name": "wrench", "mass": "1.3kg", "count": "3" } .

feasibilityStatus

enum ( SolutionStatusProto )

Статус осуществимости решения в соответствии с базовым решателем.

DualSolutionProto

Решение двойной проблемы оптимизации.

Например, рассмотрим первичную линейную пару программ с двойной парой: (Primal) (Dual) Min C * x max b * y st a * x> = b St y * a + r = cx> = 0 y, r> = 0. Двойное решение - пара (Y, R). Это возможно, если он удовлетворяет ограничениям от (двойного) выше.

В приведенном ниже сообщении y является DualValues, r - уменьшенные костюмы, а B * y - объективное значение.

Представление JSON 
{
  "dualValues": {
    object (SparseDoubleVectorProto)
  },
  "reducedCosts": {
    object (SparseDoubleVectorProto)
  },
  "feasibilityStatus": enum (SolutionStatusProto),
  "objectiveValue": number
}
Поля
dualValues

object ( SparseDoubleVectorProto )

Требования: * DualValues.ids - это элементы LinearConstraints.ids. * DualValues. Значения должны быть конечными.

reducedCosts

object ( SparseDoubleVectorProto )

Требования: * Сниженные костюмы. * Reducedcosts.clues все должны быть конечными.

feasibilityStatus

enum ( SolutionStatusProto )

Статус осуществимости решения в соответствии с базовым решателем.

objectiveValue

number

Primalrayproto

Направление неограниченного улучшения к проблеме оптимизации; эквивалентно, сертификат об неудовлетворенности для двойной проблемы оптимизации.

Например, рассмотрим простую линейную программу: min c * x st a * x> = bx> = 0 первичный луч - это x, который удовлетворяет: c * x <0 a * x> = 0 x> = 0. Соблюдайте, которые дано осуществимое Решение, любое положительное множество первичных лучей плюс, это решение все еще возможно, и дает лучшую объективную ценность. Первичный луч также доказывает проблему двойной оптимизации невозможной.

В сообщении Primalray ниже VariableValues ​​- это x.

Представление JSON 
{
  "variableValues": {
    object (SparseDoubleVectorProto)
  }
}
Поля
variableValues

object ( SparseDoubleVectorProto )

Требования: * variablevalues.ids - это элементы переменных proto.ids. * variableValues. Обнаружения должны быть конечными.

DualRayProto

Направление неограниченного улучшения к двойному оптимизации, проблеме; эквивалентно, сертификат первичной нехватки.

Например, рассмотрим первичную линейную пару программ с двойной парой: (Primal) (Dual) 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 (SparseDoubleVectorProto)
  },
  "reducedCosts": {
    object (SparseDoubleVectorProto)
  }
}
Поля
dualValues

object ( SparseDoubleVectorProto )

Требования: * DualValues.ids - это элементы LinearConstraints.ids. * DualValues. Значения должны быть конечными.

reducedCosts

object ( SparseDoubleVectorProto )

Требования: * Сниженные костюмы. * Reducedcosts.clues все должны быть конечными.

Solvestatsproto

Представление JSON 
{
  "solveTime": string,
  "problemStatus": {
    object (ProblemStatusProto)
  },
  "simplexIterations": string,
  "barrierIterations": string,
  "firstOrderIterations": string,
  "nodeCount": string
}
Поля
solveTime

string ( Duration format)

Время настенных часов, измеряемое по Math_opt, примерно время внутри Solver :: solve (). Примечание: это не включает в себя работу построения модели.

Продолжительность за секунды с девятью дробными цифрами, заканчивая « s ». Пример: "3.5s" .

problemStatus

object ( ProblemStatusProto )

Статусы осуществимости для первичных и двойных проблем.

simplexIterations

string ( int64 format)

barrierIterations

string ( int64 format)

firstOrderIterations

string ( int64 format)

nodeCount

string ( int64 format)