Package google.research.optimization.v1.mathopt

Индекс

БазисПрото

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

Симплексный метод решения линейных программ всегда возвращает «базовое допустимое решение», которое можно комбинаторно описать базисом. Базис назначает 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.

Поля
constraint_status

SparseBasisStatusVector

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

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

variable_status

SparseBasisStatusVector

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

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

basic_dual_feasibility

SolutionStatusProto

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

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

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

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

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

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

DualRayПрото

Направление неограниченного улучшения двойственной оптимизации задачи; то же самое, свидетельство первичной неосуществимости.

Например, рассмотрим простую двойную пару линейной программы: (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 — это двойные_значения, а r — уменьшенные_затраты.

Поля
dual_values

SparseDoubleVectorProto

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

reduced_costs

SparseDoubleVectorProto

Требования: * Reduced_costs.ids являются элементами VariablesProto.ids. * Все уменьшенные_косты.значения должны быть конечными.

DualSolutionПрото

Решение двойной задачи оптимизации.

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

В сообщении ниже y — это двойные_значения, r — уменьшенные_затраты, а b * y — целевое значение.

Поля
dual_values

SparseDoubleVectorProto

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

reduced_costs

SparseDoubleVectorProto

Требования: * Reduced_costs.ids являются элементами VariablesProto.ids. * Все уменьшенные_косты.значения должны быть конечными.

feasibility_status

SolutionStatusProto

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

objective_value

double

АкцентПрото

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

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

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

Статус технико-экономического обоснованияПрото

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

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

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

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

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

Поля
activate_on_zero

bool

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

expression

SparseDoubleVectorProto

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

lower_bound

double

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

upper_bound

double

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

name

string

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

indicator_id

int64

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

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

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

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

ЛимитПрото

Когда Solve() останавливается раньше времени с помощью TerminationReasonProto FEASIBLE или NO_SOLUTION_FOUND, определенного предела, который был достигнут.

Перечисления
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 может содержать дополнительную информацию о лимите.

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

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

Поля
ids[]

int64

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

lower_bounds[]

double

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

upper_bounds[]

double

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

names[]

string

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

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

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

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

Поля
ids[]

int64

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

coefficients[]

double

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

offset

double

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

МодельПрото

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

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

Поля
name

string

variables

VariablesProto

objective

ObjectiveProto

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

auxiliary_objectives

map<int64, ObjectiveProto >

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

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

linear_constraints

LinearConstraintsProto

linear_constraint_matrix

SparseDoubleMatrixProto

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

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

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

quadratic_constraints

map<int64, QuadraticConstraintProto >

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

second_order_cone_constraints

map<int64, SecondOrderConeConstraintProto >

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

sos1_constraints

map<int64, SosConstraintProto >

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

sos2_constraints

map<int64, SosConstraintProto >

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

indicator_constraints

map<int64, IndicatorConstraintProto >

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

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

Поля
variable_values_filter

SparseVectorFilterProto

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

Требования: * filtered_ids — это элементы VariablesProto.ids.

dual_values_filter

SparseVectorFilterProto

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

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

reduced_costs_filter

SparseVectorFilterProto

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

Требования: * filtered_ids — это элементы VariablesProto.ids.

initial_basis

BasisProto

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

solution_hints[]

SolutionHintProto

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

branching_priorities

SparseInt32VectorProto

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

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

ЦельГраницыПрото

Границы оптимального целевого значения.

Поля
primal_bound

double

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

dual_bound

double

Решатель утверждает, что оптимальное значение равно или хуже (больше для минимизации и меньше для максимизации), чем значение Dual_bound, вплоть до допуска двойной осуществимости решателей (см. предупреждение ниже): * Dual_bound является тривиальным (-inf для минимизации и +inf максимизации), когда решатель не претендует на наличие такой границы. Как и в случае с primal_bound, это может произойти с некоторыми решателями даже при возврате оптимального значения. Решатели MIP обычно сообщают о границе, даже если она неточная. * для непрерывных задач функция Dual_bound может быть ближе к оптимальному значению, чем к целевому наилучшему двойному допустимому решению. Для MIP одним из первых нетривиальных значений Dual_bound часто является оптимальное значение LP-релаксации MIP. * Dual_bound должен быть лучше (меньше для минимизации и больше для максимизации), чем primal_bound, с учетом допусков решателей (см. предупреждение ниже). Предупреждение: * Для непрерывных задач точное утверждение состоит в том, что существует двойное решение, которое: * является осуществимым численно (т.е. осуществимо с точностью до допуска решателя) и * имеет целевое значение Dual_bound. Это численно осуществимое решение может быть немного неосуществимым, и в этом случае значение Dual_bound может быть строго хуже, чем оптимальное значение и Primal_bound. Как и в первом случае, перевод допуска двойной осуществимости в допуск на Dual_bound нетривиален, особенно когда допуск осуществимости относительно велик. Однако некоторые решатели предоставляют исправленную версию Dual_bound, которая может быть более безопасной в числовом отношении. Доступ к этой исправленной версии можно получить через специальный вывод решателя (например, для PDLP, pdlp_output.convergence_information.corrected_dual_objective). * Для решателей MIP функция Dual_bound может быть связана с двойным решением для некоторой непрерывной релаксации (например, релаксации LP), но это часто является сложным следствием выполнения решателей и обычно более неточно, чем границы, сообщаемые решателями LP.

ЦельПрото

Поля
maximize

bool

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

offset

double

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

linear_coefficients

SparseDoubleVectorProto

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

Требования: * Linear_coefficients.ids являются элементами VariablesProto.ids. * Неуказанные переменныеProto соответствуют нулю. * Все значения линейного_коэффициента.значения должны быть конечными. * линейные_коэффициенты.значения могут быть нулевыми, но это приведет к пустой трате места.

quadratic_coefficients

SparseDoubleMatrixProto

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

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

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

name

string

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

priority

int64

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

PrimalRayПрото

Направление неограниченного улучшения оптимизационной задачи; то же самое — свидетельство о невозможности решения двойственной задачи оптимизации.

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

В сообщении PrimalRay ниже переменная_values ​​равна x.

Поля
variable_values

SparseDoubleVectorProto

Требования: *variable_values.ids являются элементами VariablesProto.ids. * Все переменные_значения.значения должны быть конечными.

PrimalSolutionПрото

Решение задачи оптимизации.

Например, рассмотрим простую линейную программу: min c * x st A * x >= bx >= 0. Основным решением является присвоение значений x. Это возможно, если оно удовлетворяет условиям A * x >= b и x >= 0 сверху. В сообщении PrimalSolutionProto ниже переменная_values ​​— это x, а Object_value — это c * x.

Поля
variable_values

SparseDoubleVectorProto

Требования: *variable_values.ids являются элементами VariablesProto.ids. * Все переменные_значения.значения должны быть конечными.

objective_value

double

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

auxiliary_objective_values

map<int64, double>

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

feasibility_status

SolutionStatusProto

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

Статус проблемыПрото

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

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

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

Поля
primal_status

FeasibilityStatusProto

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

dual_status

FeasibilityStatusProto

Статус для двойственной задачи (или для двойственной непрерывной релаксации).

primal_or_dual_infeasible

bool

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

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

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

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

Поля
linear_terms

SparseDoubleVectorProto

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

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

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

quadratic_terms

SparseDoubleMatrixProto

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

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

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

lower_bound

double

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

upper_bound

double

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

name

string

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

SecondOrderConeConstraintProto

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

|| arguments_to_norm ||_2 <= upper_bound ,

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

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

Поля
upper_bound

LinearExpressionProto

arguments_to_norm[]

LinearExpressionProto

name

string

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

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

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

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

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

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

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

Поля
variable_values

SparseDoubleVectorProto

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

dual_values

SparseDoubleVectorProto

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

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

РешениеПрото

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

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

Поля
primal_solution

PrimalSolutionProto

dual_solution

DualSolutionProto

basis

BasisProto

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

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

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

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

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

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

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

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

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

Поля
time_limit

Duration

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

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

enable_output

bool

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

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

lp_algorithm

LPAlgorithmProto

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

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

presolve

EmphasisProto

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

cuts

EmphasisProto

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

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

heuristics

EmphasisProto

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

scaling

EmphasisProto

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

iteration_limit

int64

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

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

node_limit

int64

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

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

cutoff_limit

double

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

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

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

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

objective_limit

double

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

best_bound_limit

double

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

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

solution_limit

int32

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

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

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

threads

int32

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

random_seed

int32

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

absolute_gap_tolerance

double

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

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

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

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

relative_gap_tolerance

double

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

Относительный разрыв-это нормализованная версия абсолютного разрыва (определяется на Absolute_gap_tolerance), где нормализация зависит от решателя, например, абсолютный разрыв, деленный на объективное значение наиболее осуществимого решения.

Решатель может остановиться после того, как относительный разрыв в большинстве относительно_GAP_TOLERANCE (когда установлен) и возвращает завершение_REASES_OPTIMAL.

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

См. Также Absolute_gap_tolerance.

solution_pool_size

int32

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

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

Контракт, когда Primal/Dual Solutions/Rays сложный, см. Dermination_Reasons.md для полного описания.

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

Поля
termination

TerminationProto

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

solutions[]

SolutionProto

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

primal_rays[]

PrimalRayProto

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

dual_rays[]

DualRayProto

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

solve_stats

SolveStatsProto

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

Solvestatsproto

Поля
solve_time

Duration

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

problem_status

ProblemStatusProto

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

simplex_iterations

int64

barrier_iterations

int64

first_order_iterations

int64

node_count

int64

Solvertypepproto

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

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

Решение ограничений целочисленных программ (SCIP) Согласие (третья сторона).

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

SOLVER_TYPE_GUROBI

Gurobi Solver (третья сторона).

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

SOLVER_TYPE_GLOP

Google Glop Solver.

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

SOLVER_TYPE_CP_SAT

Google CP-SAT Solver.

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

SOLVER_TYPE_PDLP

Google PDLP Solver.

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

SOLVER_TYPE_GLPK

GNU Линейный программный комплект (GLPK) (третья сторона).

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

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

При решении LP с предварительным оборудованием решение (и несвязанные лучи) возвращается только в том случае, если обнаружено оптимальное решение. Иначе ничего не возвращается. См. GLPK-5.0/DOC/GLPK.PDF СТРАНИЦА #40 Доступно от GLPK-5.0.TAR.GZ для получения подробной информации.

SOLVER_TYPE_OSQP

Оператор расщепляет квадратичную программу (OSQP) Солятель (третья сторона).

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

SOLVER_TYPE_ECOS

Встроенный конический решатель (EcoS) (третья сторона).

Поддерживает проблемы LP и SOCP. Использует методы внутренней точки (барьер).

SOLVER_TYPE_SCS

Расщепляющий конический решатель (SCS) (третья сторона).

Поддерживает проблемы LP и SOCP. Использует метод первого порядка.

SOLVER_TYPE_HIGHS

Высокий решатель (третья сторона).

Поддерживает проблемы LP и MIP (выпуклые QPS являются невыполненными).

SOLVER_TYPE_SANTORINI

Справочная реализация Mathopt решателя MIP.

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

SosConstraintПрото

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

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

Поля
expressions[]

LinearExpressionProto

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

weights[]

double

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

name

string

Родительские сообщения могут иметь уникальные требования в этой области; Например, см. Modelproto.sos1_constraints и Sosconstraintupdatesproto.new_constraints.

SparsebasisStatusVector

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

Поля
ids[]

int64

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

values[]

BasisStatusProto

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

Sparsedoublematrixproto

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

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

Поля
row_ids[]

int64

column_ids[]

int64

coefficients[]

double

Не может содержать Нэн.

Sparsedoublevectorproto

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

Поля
ids[]

int64

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

values[]

double

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

Sparseint32VectorProto

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

Поля
ids[]

int64

Следует отсортировать (при увеличении упорядочения) со всеми элементами отличительными.

values[]

int32

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

SparsectorfilterProto

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

Поля
skip_zero_values

bool

Для Sparseboolvectorproto "Zero" является false .

filter_by_ids

bool

Когда TRUE верните только значения, соответствующие идентификаторам, перечисленным в Filtreed_IDS.

filtered_ids[]

int64

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

Завершение прото

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

Поля
reason

TerminationReasonProto

Дополнительная информация в limit , когда значение - это завершение_REASESARIBLE или завершение или завершение_REASES_NO_SOLUTION_FOUND, см. limit для получения подробной информации.

limit

LimitProto

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

detail

string

Дополнительная типичная конкретная информация о прекращении.

problem_status

ProblemStatusProto

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

objective_bounds

ObjectiveBoundsProto

Границы на оптимальном объективном значении. По состоянию на 18 июля 2023 года это сообщение может отсутствовать. При отсутствии, Objective_bounds.primal_bound можно найти в solveresultproto.solve.stats.best_primal_bound и obj

Прекращениерезонеспрото

Причина, по которой призыв решить () завершается.

Перечисления
TERMINATION_REASON_UNSPECIFIED
TERMINATION_REASON_OPTIMAL Было обнаружено доказуемо оптимальное решение (до численных допусков).
TERMINATION_REASON_INFEASIBLE Первичная проблема не имеет возможных решений.
TERMINATION_REASON_UNBOUNDED Первичная проблема возможна, и вдоль первичного луча можно найти произвольно хороших решений.
TERMINATION_REASON_INFEASIBLE_OR_UNBOUNDED Первичная проблема либо невозможна, либо неограничена. Более подробная информация о статусе проблемы может быть доступна в solve_stats.problem_status. Обратите внимание, что неограниченный статус Гуроби здесь может быть отображен здесь.
TERMINATION_REASON_IMPRECISE

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

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

TERMINATION_REASON_FEASIBLE Оптимизатор достиг некоторого предела, и возвращается первичное осуществимое решение. См. Solveresultproto.limit_detail для подробного описания вида предела, который был достигнут.
TERMINATION_REASON_NO_SOLUTION_FOUND Оптимизатор достиг некоторого предела, и он не обнаружил первичного осуществимого решения. См. Solveresultproto.limit_detail для подробного описания вида предела, который был достигнут.
TERMINATION_REASON_NUMERICAL_ERROR Алгоритм остановился, потому что он столкнулся с невозможной численной ошибкой. Информация о решении не доступна.
TERMINATION_REASON_OTHER_ERROR Алгоритм остановился из -за ошибки, не покрытой одним из статусов, определенных выше. Информация о решении не доступна.

Переменные

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

Поля
ids[]

int64

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

lower_bounds[]

double

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

upper_bounds[]

double

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

integers[]

bool

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

names[]

string

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

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