求解输入模型并一次性返回结果。当您不需要回调、增量并且不需要跟踪求解进度时,请使用此方法。
HTTP 请求
POST https://optimization.googleapis.com/v1/mathopt:solveMathOptModel
网址采用 gRPC 转码语法。
请求正文
请求正文中包含结构如下的数据:
JSON 表示法 |
---|
{ "solverType": enum ( |
字段 | |
---|---|
solverType |
可选。用于以数字方式求解问题的求解器类型。请注意,如果求解器不支持模型中的特定特征,则优化过程将失败。 |
model |
必需。表示要解决的优化问题的数学表示形式。 |
parameters |
可选。用于控制单次求解的参数。系统会专门处理 enableOutput 参数。对于支持消息回调的求解器,将其设置为 true 会使服务器注册消息回调。生成的消息将在 SolveMathOptModelResponse.messages 中返回。对于其他求解器,将 enableOutput 设置为 true 会导致错误。 |
modelParameters |
可选。用于控制输入模型特有的单个求解的参数(如需了解与模型无关的参数,请参阅 SolveParametersProto)。 |
响应正文
MathOpt 中一元远程求解的响应。
如果成功,响应正文将包含结构如下的数据:
JSON 表示法 |
---|
{
"result": {
object ( |
字段 | |
---|---|
result |
请求中求解模型的输出说明。 |
messages[] |
如果使用了 SolveParametersProto.enable_output,则会包含支持消息回调的求解器的日志消息。 |
SolverTypeProto
MathOpt 支持的求解器。
枚举 | |
---|---|
SOLVER_TYPE_UNSPECIFIED |
|
SOLVER_TYPE_GSCIP |
求解约束整数程序 (SCIP) 求解器(第三方)。 支持 LP、MIP 和非凸整数二次问题。但不会返回 LP 的双重数据。对于 LP,首选 GLOP。 |
SOLVER_TYPE_GUROBI |
Gurobi 求解器(第三方)。 支持 LP、MIP 和非凸整数二次问题。通常速度最快,但有特殊许可。 |
SOLVER_TYPE_GLOP |
Google 的 Glop 求解器。 支持使用原始和双单工方法使用语言包。 |
SOLVER_TYPE_CP_SAT |
Google 的 CP-SAT 求解器。 支持所有变量均为整数且有界限(或暗示在 presolve 之后)的问题。实验性支持,可对连续变量问题进行重新缩放和离散化。 |
SOLVER_TYPE_PDLP |
Google 的 PDLP 求解器。 支持 LP 和凸对角二次目标。使用一阶方法,而不是单纯法。可以解决非常大的问题。 |
SOLVER_TYPE_GLPK |
GNU Linear Programming Kit (GLPK)(第三方)。 支持 MIP 和 LP。 线程安全:GLPK 使用线程本地存储空间进行内存分配。因此,求解器实例必须在创建时在同一线程上销毁,否则 GLPK 会崩溃。似乎可以从用于创建求解器的线程以外的其他线程调用 Solver::Solve(),但 GLPK 没有对此进行记录,应避免这样做。 使用解析器解析 LP 时,只有在找到最佳解决方案时才会返回解决方案(和未绑定光线)。否则,系统不会返回任何内容。有关详情,请参阅 glpk-5.0.tar.gz 上提供的 glpk-5.0/doc/glpk.pdf 第 40 页, |
SOLVER_TYPE_OSQP |
运算符拆分二次规划 (OSQP) 求解器(第三方)。 支持具有线性约束条件和线性或凸二次目标的连续问题。使用一阶方法。 |
SOLVER_TYPE_ECOS |
嵌入式圆锥求解器 (ECOS)(第三方)。 支持 LP 和 SOCP 问题。使用内部点方法(屏障)。 |
SOLVER_TYPE_SCS |
分割圆锥求解器 (SCS)(第三方)。 支持 LP 和 SOCP 问题。使用一阶方法。 |
SOLVER_TYPE_HIGHS |
HiGHS 求解器(第三方)。 支持 LP 和 MIP 问题(凸面 QP 未实现)。 |
SOLVER_TYPE_SANTORINI |
MathOpt MIP 求解器的参考实现。 速度慢/不建议用于生产环境。不是 LP 求解器(不会返回双重信息)。 |
ModelProto
优化问题。MathOpt 支持:- 连续和整数决策变量,具有可选的有限边界。- 线性目标和二次目标(单个或多个目标),可最小化或最大化。- 多种约束条件类型,包括:* 线性约束条件 * 二次约束条件 * 二阶圆锥约束条件 * 逻辑约束条件 > SOS1 和 SOS2 约束条件 > 指示器约束条件
默认情况下,约束以“id-to-data”映射表示。不过,我们以更高效的“数组结构”格式表示线性约束。
JSON 表示法 |
---|
{ "name": string, "variables": { object ( |
字段 | |
---|---|
name |
|
variables |
|
objective |
模型中的主要目标。 |
auxiliaryObjectives |
在多目标模型中使用的辅助目标。 映射键 ID 必须采用 [0, max(int64)) 格式。每个优先级以及每个非空名称都必须是唯一的,且也与主要 包含一系列 |
linearConstraints |
|
linearConstraintMatrix |
线性约束的变量系数。 如果删除此限制条件涉及的变量,系统会将其视为已设置为零。 要求:* linearConstraintMatrix.row_ids 是 linearConstraints.ids 的元素。* linearConstraintMatrix.column_ids 是 variables.ids 的元素。* 未指定的矩阵条目为零。* linearConstraintMatrix.values 必须全部为有限。 |
quadraticConstraints |
模型中的二次约束条件。 包含一系列 |
secondOrderConeConstraints |
模型中的二阶圆锥约束。 包含一系列 |
sos1Constraints |
模型中的 SOS1 约束条件,约束最多只有一个 包含一系列 |
sos2Constraints |
模型中的 SOS2 约束条件,约束 包含一系列 |
indicatorConstraints |
模型中的指示器约束条件,它会强制规定:如果二元“指示器变量”设置为 1,则必须适用“隐含约束条件”。 包含一系列 |
VariablesProto
如下所示,我们定义“#variables”= size(VariablesProto.ids)。
JSON 表示法 |
---|
{ "ids": [ string ], "lowerBounds": [ number ], "upperBounds": [ number ], "integers": [ boolean ], "names": [ string ] } |
字段 | |
---|---|
ids[] |
必须是非负数,并且必须严格递增。不能使用 max(int64) 值。 |
lowerBounds[] |
长度应等于 #variables,值应采用 [-inf, inf)。 |
upperBounds[] |
长度应等于 #variables,值在 (-inf, inf]) 中。 |
integers[] |
长度应等于 #variables。对于连续变量,值为 false;对于整数变量,值为 true。 |
names[] |
如果未设置,则假定为全部空字符串。否则,长度应等于 #variables。 所有非空名称必须互不相同。 |
ObjectiveProto
JSON 表示法 |
---|
{ "maximize": boolean, "offset": number, "linearCoefficients": { object ( |
字段 | |
---|---|
maximize |
false 表示最小化,true 表示最大化 |
offset |
必须为有限值,而非 NaN。 |
linearCoefficients |
决策变量中的线性 ObjectiveProto 字词。 要求:* linearCoeffectives.ids 是 VariablesProto.ids 的元素。* 未指定 VariablesProto 对应于零。* linearCoefficiencys.values 必须全部为有限值。* linearCoefficiencys.values 可以为零,但这样只会浪费空间。 |
quadraticCoefficients |
在决策变量中二次处理的客观字词。 除了 SparseDoubleMatrixProto 消息的要求之外:* 矩阵必须为上三角形:对于每个 i, quadraticCo 验证.row_ids[i] <= quadraticCo 验证.column_ids[i]。 注意:* 未明确存储的字词的系数为零。* quadraticCoistics.coefficiencys 的元素可以为零,但这样会浪费空间。 |
name |
父级消息可能对此字段有唯一性要求;例如,请参阅 ModelProto.objectives 和 AuxiliaryObjectivesUpdatesProto.new_objectives。 |
priority |
对于多目标问题,此目标相对于其他目标的优先级(越低越重要)。此值必须是非负数。此外,模型中的每个目标优先级在求解时必须各不相同。未在 proto 级别验证此条件,因此模型可能暂时具有具有相同优先级的目标。 |
SparseDoubleVectorProto
双精度向量的稀疏表示法。
JSON 表示法 |
---|
{ "ids": [ string ], "values": [ number ] } |
字段 | |
---|---|
ids[] |
必须进行排序(以升序排列),且所有元素均不重复。 |
values[] |
长度必须与 ID 相同。不得包含 NaN。 |
SparseDoubleMatrixProto
双精度矩阵的稀疏表示法。
矩阵存储为行 ID、列 ID 和系数的三元组。这三个矢量的长度必须相等。对于所有 i,元组(rowIds[i]、columnIds[i])应该是不同的。条目必须按行主顺序排列。
JSON 表示法 |
---|
{ "rowIds": [ string ], "columnIds": [ string ], "coefficients": [ number ] } |
字段 | |
---|---|
rowIds[] |
|
columnIds[] |
|
coefficients[] |
不得包含 NaN。 |
LinearConstraintsProto
如下所示,我们定义“#linear constraints” = size(LinearConstraintsProto.ids)。
JSON 表示法 |
---|
{ "ids": [ string ], "lowerBounds": [ number ], "upperBounds": [ number ], "names": [ string ] } |
字段 | |
---|---|
ids[] |
必须是非负数,并且必须严格递增。不能使用 max(int64) 值。 |
lowerBounds[] |
长度应等于 #linear 约束条件,值应采用 [-inf, inf) 格式。 |
upperBounds[] |
长度应等于 #linear 约束条件,值应位于 (-inf, inf] 中。 |
names[] |
如果未设置,则假定为全部空字符串。否则,其长度应等于 #linear 约束条件。 所有非空名称必须互不相同。 |
QuadraticConstraintProto
形式为 lb <= sum{linearTerms} + total{quadraticTerms} <= ub. 的单二次约束。
如果删除此限制条件涉及的变量,系统会将其视为已设置为零。
JSON 表示法 |
---|
{ "linearTerms": { object ( |
字段 | |
---|---|
linearTerms |
决策变量中的线性字词。 除了对 SparseDoubleVectorProto 消息的要求之外,我们还要求:* linearTerms.ids 是 VariablesProto.ids 的元素。* linearTerms.values 必须全部为有限且非 NaN。 注意:* 省略的变量 ID 对应的系数为零。* linearTerms.values 可以为零,但这样只会浪费空间。 |
quadraticTerms |
决策变量中的二次项。 除了对 SparseDoubleMatrixProto 消息的要求之外,我们还要求:* quadraticTerms.row_ids 的每个元素和 quadraticTerms.column_ids 的每个元素都必须是 VariablesProto.ids 的一个元素。* 矩阵必须为上三角形:对于每个 i,quadraticTerms.row_ids[i] <= quadraticTerms.column_ids[i]。 注意:* 未明确存储的字词的系数为零。* quadraticTerms.coistics 的元素可以为零,但这样会浪费空间。 |
lowerBound |
该值必须在 [-inf, inf) 中指定,并且小于或等于 |
upperBound |
值必须介于 (-inf, inf] 内,并且大于或等于 |
name |
父级消息可能对此字段有唯一性要求;例如,请参阅 ModelProto.quadratic_constraints 和 QuadraticConstraintUpdatesProto.new_constraints。 |
SecondOrderConeConstraintProto
一个二阶圆锥约束条件,形式如下:
||argumentsToNorm
||_2 <= upperBound
,
其中 upperBound
和 argumentsToNorm
的每个元素都是线性表达式。
如果删除此限制条件涉及的变量,系统会将其视为已设置为零。
JSON 表示法 |
---|
{ "upperBound": { object ( |
字段 | |
---|---|
upperBound |
|
argumentsToNorm[] |
|
name |
父级消息可能对此字段有唯一性要求;例如,请参阅 |
LinearExpressionProto
线性表达式的稀疏表示法(变量的加权和加上常量偏移量)。
JSON 表示法 |
---|
{ "ids": [ string ], "coefficients": [ number ], "offset": number } |
字段 | |
---|---|
ids[] |
变量的 ID。必须进行排序(以升序排列),且所有元素均不重复。 |
coefficients[] |
长度必须与 ID 相同。值必须为有限值,不得为 NaN。 |
offset |
必须为有限值,且不能为 NaN。 |
SosConstraintProto
用于表示单个 SOS1 或 SOS2 限制的数据。
如果删除此限制条件涉及的变量,系统会将其视为已设置为零。
JSON 表示法 |
---|
{
"expressions": [
{
object ( |
字段 | |
---|---|
expressions[] |
要应用 SOS 约束条件的表达式:* SOS1:最多一个元素采用非零值。* SOS2:最多两个元素采用非零值,并且它们在重复排序中必须相邻。 |
weights[] |
值可以是空的,也可以是与表达式相同的长度。如果为空,则默认权重为 1、2...。如果存在,则条目必须是唯一的。 |
name |
父级消息可能对此字段有唯一性要求;例如,请参阅 ModelProto.sos1_constraints 和 SosConstraintUpdatesProto.new_constraints。 |
IndicatorConstraintProto
用于表示以下形式的单个指示器约束条件的数据:Variable(indicatorId) = (activateOnZero ?0 : 1) Settings lowerBound <= 表达式 <= topBound。
如果此限制条件涉及的变量(指示符或出现在 expression
中)被删除,系统会将其视为 0。特别是,删除指示变量意味着,如果 activateOnZero
为 false,指示符约束条件是空的;如果 activateOnZero
为 true,则相当于线性约束条件。
JSON 表示法 |
---|
{
"activateOnZero": boolean,
"expression": {
object ( |
字段 | |
---|---|
activateOnZero |
如果为 true,则如果指示器变量的值为 0,则隐式约束条件必须成立。否则,如果指示器变量的值为 1,则必须保持隐含的约束条件。 |
expression |
必须是关于所含模型的有效线性表达式:* |
lowerBound |
值必须在 [-inf, inf) 内;不能为 NaN。 |
upperBound |
值必须在 (-inf, inf]) 内;不能为 NaN。 |
name |
父级消息可能对此字段有唯一性要求;例如,请参阅 |
indicatorId |
与二元变量对应的 ID,或未设置。如果未设置,系统会忽略指示符约束条件。如果已设置,则要求:* VariablesProto.integers[indicatorId] = true, * VariablesProto.Lower_bounds[indicatorId] >= 0, * VariablesProto.upper_bounds[indicatorId] <= 1。MathOpt 不会验证这些条件,但如果不满足这些条件,则求解器在求解时会返回错误。 |
SolveParametersProto
用于控制单次求解的参数。
包含所有求解器通用的参数(例如 timeLimit)和特定求解器的参数(例如 gscip)。如果同时在常用和求解器专用字段中设置了值,则使用求解器专用设置。
如果常见参数为可选且未设置,或枚举未指定值,则表示使用了求解器默认值。
除了正在使用的求解器,系统会忽略其他求解器的特定参数。
依赖于模型的参数(例如为每个变量设置分支优先级)会在 ModelSolveParametersProto 中传递。
JSON 表示法 |
---|
{ "timeLimit": string, "enableOutput": boolean, "lpAlgorithm": enum ( |
字段 | |
---|---|
timeLimit |
求解器在问题上花费的时间上限(如果未设置,则为无限)。 此值不是硬性限制,解决时间可能会略微超过此值。此参数始终会传递给底层求解器,不使用求解器默认值。 此时长以秒为单位,最多包含九个小数位,以“ |
enableOutput |
允许输出求解器实现轨迹。这些轨迹的位置取决于求解器。对于 SCIP 和 Gurobi,这将是标准输出流。对于 Glop 和 CP-SAT,这将记录(信息)。 请注意,如果求解器支持消息回调并且用户为其注册了回调,则此参数值会被忽略,并且不会输出任何轨迹。 |
lpAlgorithm |
求解线性程序的算法。如果 LP_ALGORITHM_UNSPECIFIED,使用求解器默认算法。 对于非线性程序但线性规划是子例程的问题,求解器可以使用此值。例如,MIP 求解器通常仅将其用于根 LP 求解(否则使用双单工)。 |
presolve |
启动主算法前简化问题的工作量,如果 RULE_UNSPECIFIED,则应用求解器默认的工作量级别。 |
cuts |
尝试更强的 LP 放宽(仅限 MIP),或求解器默认工作量级别(如果 RULE_UNSPECIFIED)。 注意:停用剪切可能会使回调有机会在 MIP_NODE 处添加剪切,此行为特定于求解器。 |
heuristics |
寻找完整搜索过程中遇到的可行解决方案(仅限 MIP)或求解器默认工作量级别(如果 RULE_UNSPECIFIED 的话)。 |
scaling |
尝试重新缩放问题以提高数值稳定性,或求解器默认工作量级别(如果 RULE_UNSPECIFIED)。 |
iterationLimit |
限制底层算法(例如单工数据透视)的迭代次数。具体行为取决于所使用的求解器和算法,但通常会给出确定性的求解极限(可能需要更多配置,例如一个线程)。 通常受 LP、QP 和 MIP 求解器支持,但对于 MIP 求解器,另请参阅 nodeLimit。 |
nodeLimit |
限制通过枚举搜索(例如分支和边界)所解决的子问题数量。对于许多求解器,这可用于确定性地限制计算(可能需要更多配置,例如一个线程)。 通常,对于 MIP 求解器,另请参阅 iterLimit。 |
cutoffLimit |
如果求解器能够证明不存在至少与临界点一样好的原始解,则它会提前停止。 提前停止时,求解器会返回终止原因 NO_SOLUTION_FOUND 且限制值为 CUTOFF,并且不需要提供任何额外的解信息。如果没有提前停止,则对返回值没有影响。 如果您希望返回目标完全等于截止时间的解决方案,我们建议您使用公差值。 如需了解详情以及与 bestBoundLimit 的比较,请参阅用户指南。 |
objectiveLimit |
一旦找到至少这么好的解决方案,求解器就会立即停止,终止原因为“可行”(FEASIBLE),并限制目标 (OBJECTIVE)。 |
bestBoundLimit |
当求解器证明最佳边界至少达到这个值时,求解器会立即停止,终止原因为 FEASIBLE 或 NO_SOLUTION_FOUND 并限制 OBJECTIVE。 如需了解详情以及与 cutoffLimit 的比较,请参阅用户指南。 |
solutionLimit |
在找到这么多可行的解决方案后,求解器提前停止,终止原因为 FEASIBLE(可行),并限制了 SOLUTION。必须大于零(如果已设置)。通常用它来让求解器停止找到第一个可行的解。请注意,我们无法保证返回的任何解决方案的目标值。 求解器通常返回的解数不会超过解限制,但 MathOpt 不会强制执行此操作,另请参阅 b/214041169。 目前支持 Gurobi 和 SCIP,并且仅支持值为 1 的 CP-SAT。 |
threads |
如果设置,则此值必须大于等于 1。 |
randomSeed |
底层求解器中的伪随机数生成器的种子。请注意,所有求解器都使用伪随机数字来选择某些因素,例如 LP 算法中的扰乱、联系分解规则和启发式修正。更改此值可能会对求解器行为产生显著影响。 虽然所有求解器都有种子的概念,但请注意,有效值取决于实际求解器。- Gurobi:[0:GRB_MAXINT](从 Gurobi 9.0 开始为 2x10^9)。- GSCIP:[0:2147483647](即 MAX_INT、kint32max 或 2^31-1)。- GLOP:[0:2147483647](同上)在任何情况下,求解器都会收到等于 MAX(0, MIN(MAX_VALID_VALUE_FOR_SOLVER, randomSeed)) 的值。 |
absoluteGapTolerance |
MIP 求解器的绝对最优容忍度(主要)。 绝对 GAP 为以下两者之间的差异的绝对值:* 找到的最佳可行解决方案的目标值,* 搜索产生的双边界。当绝对 GAP 达到 absoluteGapTolerance(如果设置)时,求解器可以停止,并返回 TERMINATION_REASON_OPTIMAL。 如果设置,则必须大于等于 0。 另请参阅 relativeGapTolerance。 |
relativeGapTolerance |
MIP 求解器的相对最优容忍度(主要)。 相对 GAP 是绝对 GAP 的标准化版本(根据 absoluteGapTolerance 定义),其中标准化取决于求解器,例如,绝对 GAP 除以找到的最佳可行解决方案的目标值。 当相对 GAP 达到最大 relativeGapTolerance(若已设置)时,求解器可停止,并返回 TERMINATION_REASON_OPTIMAL。 如果设置,则必须大于等于 0。 另请参阅 absoluteGapTolerance。 |
solutionPoolSize |
在搜索时维护多达 |
LPAlgorithmProto
选择求解线性程序的算法。
枚举 | |
---|---|
LP_ALGORITHM_UNSPECIFIED |
|
LP_ALGORITHM_PRIMAL_SIMPLEX |
(原)单工法。通常可以提供原始解和双重解、原始/双射线以解决原始/双重无界限问题以及基础。 |
LP_ALGORITHM_DUAL_SIMPLEX |
双单工方法。通常可以提供原始解和双重解、原始/双射线以解决原始/双重无界限问题以及基础。 |
LP_ALGORITHM_BARRIER |
屏障方法,通常也称为内部点方法 (IPM)。通常可以给出原始解和双重解。一些实现还会对无界限/不可行问题产生光线。除非底层求解器执行“交叉”且以单项形式结束,否则不给出基数。 |
LP_ALGORITHM_FIRST_ORDER |
一种基于一阶方法的算法。这类模型通常会生成原始解决方案和双重解决方案,还可能生成“原始和/或双重不可行”证书。一阶方法提供的解决方案通常准确度较低,因此用户应谨慎设置解决方案质量参数(例如公差)并验证解决方案。 |
EmphasisProto
解决过程中可选任务的执行工作量(如需使用,请参阅 SolveParametersProto)。
Emphasis 用于按如下方式配置求解器功能:* 如果求解器不支持该功能,则只有 UNSPECIFIED 始终有效,任何其他设置通常会导致参数无效错误(某些求解器也可能会接受 OFF)。* 如果求解器支持该功能:- 如果设置为 UNSPECIFIED,则使用基础默认值。- 如果无法关闭该功能,则“OFF”将返回错误。- 如果默认启用此功能,则求解器默认设置通常会映射到中等。- 如果支持该功能,则 LOW、MEDIUM、HIGH 和 VERY HIGH 绝对不会出错,并会将其映射到最匹配的值。
枚举 | |
---|---|
EMPHASIS_UNSPECIFIED |
|
EMPHASIS_OFF |
|
EMPHASIS_LOW |
|
EMPHASIS_MEDIUM |
|
EMPHASIS_HIGH |
|
EMPHASIS_VERY_HIGH |
ModelSolveParametersProto
JSON 表示法 |
---|
{ "variableValuesFilter": { object ( |
字段 | |
---|---|
variableValuesFilter |
此过滤器适用于返回的由 PrimalSolutionProto 和 PrimalRayProto 中的变量(PrimalSolutionProto.variable_values、PrimalRayProto.variable_values 中的变量)键控的过滤器。 要求:*filteredId 是 VariablesProto.ids 的元素。 |
dualValuesFilter |
该过滤器应用于所有返回的稀疏容器,由 DualSolutionProto 和 DualRay 中的线性约束条件进行键控(DualSolutionProto.dual_values、DualRay.dual_values)。 要求:*filteredIds 是 LinearConstraints.ids 的元素。 |
reducedCostsFilter |
过滤器,应用于所有返回的稀疏容器,由 DualSolutionProto 和 DualRay 中的变量(DualSolutionProto.reduced_costs、DualRay.reduced_costs)变量键控。 要求:*filteredId 是 VariablesProto.ids 的元素。 |
initialBasis |
温启动单工 LP 求解器的可选初始基础。如果设置了此字段,则根据 |
solutionHints[] |
可选的解决方案提示。如果底层求解器只接受一个提示,系统会使用第一个提示。 |
branchingPriorities |
可选的分支优先级。值较高的变量将首先分支。未设置优先级的变量会获得求解器的默认优先级(通常为零)。 要求:* branchingPriorities.values 必须为有限。* branchingPriorities.ids 必须是 VariablesProto.ids 的元素。 |
SparseVectorFilterProto
此消息允许查询/设置 SparseXxxxVector 的特定部分。默认行为不是过滤掉任何内容,一种常见用法是仅查询解决方案的部分内容(仅限非零值和/或仅手动选择的一组变量值)。
JSON 表示法 |
---|
{ "skipZeroValues": boolean, "filterByIds": boolean, "filteredIds": [ string ] } |
字段 | |
---|---|
skipZeroValues |
对于 SparseBoolVectorProto,“zero”为 |
filterByIds |
如果为 true,则仅返回与过滤器 ID 中列出的 ID 对应的值。 |
filteredIds[] |
当 filterByIds 为 true 时,要使用的 ID 列表。当 filterByIds 为 false 时,必须为空。注意:如果此字段为空,并且 filterByIds 为 true,则表示您不需要在结果中包含任何信息。 |
BasisProto
线性程序解的组合表征。
求解线性程序的单例方法总是会返回“基本可行的解”,该解可以用基础组合进行描述。基础会为每个变量和线性约束条件分配一个 BasisStatusProto。
例如,假设采用标准形式 LP:min c * x s.t. A * x = b x >= 0,其变量多于约束条件且行排名为 A。
n 是变量的数量,m 是线性约束的数量。此问题的有效基础可按以下方式构建:* 所有约束条件都将具有基础状态 FIXED。* 选择 m 个变量,使 A 的列成为线性独立的,并为其指定“BASIC”状态。* 为其余 n - m 个变量分配状态 AT_LOWER。
在此基础上,基本解决方案是 A * x = b 的唯一解,其中所有状态为 AT_LOWER 的变量都固定在下限(全部为零)。如果所得到的解也满足 x >= 0,则称为基本可行解。
JSON 表示法 |
---|
{ "constraintStatus": { object ( |
字段 | |
---|---|
constraintStatus |
限制条件基础状态。 要求:* constraintStatus.ids 等于 LinearConstraints.ids。 |
variableStatus |
变量基本状态。 要求:* constraintStatus.ids 等于 VariablesProto.ids。 |
basicDualFeasibility |
这是 MathOpt 使用的一项高级功能,用于确定效果欠佳的 LP 解决方案的可行性(最佳解决方案的状态始终为 SOLUTION_STATUS_FEASIBLE)。 对于单端 LP,它应该等于相关双解决方案的可行性状态。对于双面 LP,在某些极端情况下可能会有所不同(例如,用原始单工数求解不完整)。 如果您通过 ModelSolveParametersProto.initial_basis 提供起始基础,此值会被忽略。它仅与 SolutionProto.basis 返回的基础相关。 |
SparseBasisStatusVector
基础状态矢量的稀疏表示法。
JSON 表示法 |
---|
{
"ids": [
string
],
"values": [
enum ( |
字段 | |
---|---|
ids[] |
必须进行排序(以升序排列),且所有元素均不重复。 |
values[] |
长度必须与 ID 相同。 |
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 |
变量/约束条件是基本的。 |
SolutionStatusProto
求解器声明的原始解或双重解的可行性。
枚举 | |
---|---|
SOLUTION_STATUS_UNSPECIFIED |
表示无状态的保护值。 |
SOLUTION_STATUS_UNDETERMINED |
求解器未声明可行性状态。 |
SOLUTION_STATUS_FEASIBLE |
Solver 声称这个解决方案是可行的。 |
SOLUTION_STATUS_INFEASIBLE |
Solver 声称这个解决方案是不可行的。 |
SolutionHintProto
推荐的求解器起始解决方案。
MIP 求解器通常只需要原始信息 (variableValues
),而 LP 求解器则同时需要原始和双重信息 (dualValues
)。
许多 MIP 求解器适用于:(1) 未指定所有变量的部分解或 (2) 不可行的解。在这些情况下,求解器通常会求解子 MIP 以完成/更正提示。
求解器使用提示的方式(如果有的话)在很大程度上取决于求解器、问题类型和所使用的算法。确保提示有效的最可靠方式是读取有提示和不使用提示的底层求解器日志。
基于 Simplex 的 LP 求解器通常优先使用初始基础,而不是解决方案提示(否则,它们需要进行组合,将提示转换为基本可行的解决方案)。
JSON 表示法 |
---|
{ "variableValues": { object ( |
字段 | |
---|---|
variableValues |
可能对问题的原始变量进行部分赋值。对于此子消息,独立于求解器的要求是:*variableValues.ids 是 VariablesProto.ids 的元素。* variableValues.values 都必须是有限值。 |
dualValues |
向问题线性约束条件赋值(可能是部分值)。 要求:* dualValues.ids 是 LinearConstraintsProto.ids 的元素。* dualValues.values 都必须是有限值。 |
SparseInt32VectorProto
整数向量的稀疏表示法。
JSON 表示法 |
---|
{ "ids": [ string ], "values": [ integer ] } |
字段 | |
---|---|
ids[] |
应进行排序(以升序排列),且所有元素均不重复。 |
values[] |
长度必须与 ID 相同。 |
SolveResultProto
有关原始/双解决方案/光线何时复杂的合同,请参阅 terminate_reasons.md,了解完整说明。
在最终敲定确切的合同之前,最稳妥的做法是检查是否存在解决方案/射线,而不是依靠终止原因。
JSON 表示法 |
---|
{ "termination": { object ( |
字段 | |
---|---|
termination |
求解器停止的原因。 |
solutions[] |
未来求解器应实施的解决方案的顺序一般规定如下:1. 具有基本可行解决方案的解,按最佳基本目标排序。2. 包含两种可行解决方案的解决方案,按最佳双目标排序(未知的双目标最差)3. 其余所有溶液可按任意顺序返回。 |
primalRays[] |
提供无界限的原始改进或等效的双重不可行证书的说明。通常针对 TeralityReasonProtos UNBOUNDED 和 DUAL_INFEASIBLE 提供 |
dualRays[] |
提供无界限双重改进或同等原始不可行性证书的说明。通常针对 TeralityReasonProto INFEASIBLE 提供。 |
solveStats |
有关求解过程的统计信息,例如运行时间和迭代。 |
TerminationProto
有关 Solve() 调用终止原因的所有信息。
JSON 表示法 |
---|
{ "reason": enum ( |
字段 | |
---|---|
reason |
当值为 TERMINATION_REASON_FEASIBLE 或 TERMINATION_REASON_NO_SOLUTION_FOUND 时, |
limit |
除非原因是 TERMINATION_REASON_FEASIBLE 或 TERMINATION_REASON_NO_SOLUTION_FOUND,否则值为 LIMIT_UNSPECIFIED。并非所有求解器都可以确定导致终止的极限,当无法确定原因时,使用 LIMIT_UNDETERMINED。 |
detail |
有关终止的其他通常求解器专用信息。 |
problemStatus |
原始问题和双重问题的可行性状态。自 2023 年 7 月 18 日起,此消息可能会缺失。如果缺失,可以在 SolveResultProto.solve_stats 中找到 issueStatus。 |
objectiveBounds |
最佳目标值的边界。自 2023 年 7 月 18 日起,此消息可能会缺失。如果缺少,targetBounds.primal_bound 可在 SolveResultProto.solve.stats.best_primal_bound 中找到,goalBounds.dual_bound 可在 SolveResultProto.solve.stats.best_dual_bound 中找到 |
TerminationReasonProto
调用 Solve() 的原因终止。
枚举 | |
---|---|
TERMINATION_REASON_UNSPECIFIED |
|
TERMINATION_REASON_OPTIMAL |
找到了一种可证明的最佳解决方案(最高可达数值公差)。 |
TERMINATION_REASON_INFEASIBLE |
这个首要问题没有可行的解决方案。 |
TERMINATION_REASON_UNBOUNDED |
原始问题是可行的,并且可以通过原始射线找到任意好解。 |
TERMINATION_REASON_INFEASIBLE_OR_UNBOUNDED |
这个原始问题要么不可行,要么没有界限。有关问题状态的更多详细信息,请参阅 resolveStats.problem_status。请注意,Gurobi 的无限状态可能映射在这里。 |
TERMINATION_REASON_IMPRECISE |
问题已根据上述条件之一(Optimal、Infeasible、UnfeasibleOrUnbounded 或一些原始/双解/射线存在,但它们微乎其微,或者(如果问题几乎是最佳的)它们可能在最佳解决方案目标和最佳目标之间存在差距。 用户仍然可以查询原始/双解/射线和解统计数据,但要负责处理数值不精确问题。 |
TERMINATION_REASON_FEASIBLE |
优化器达到了某种限制,然后返回了基本可行的解决方案。如需详细了解所达到的限制类型,请参阅 SolveResultProto.limit_detail。 |
TERMINATION_REASON_NO_SOLUTION_FOUND |
优化器已达到某种限值,并未找到基本可行的解决方案。如需详细了解所达到的限制类型,请参阅 SolveResultProto.limit_detail。 |
TERMINATION_REASON_NUMERICAL_ERROR |
由于遇到不可恢复的数值错误,算法已停止。没有可用的解决方案信息。 |
TERMINATION_REASON_OTHER_ERROR |
由于上述某个状态未涵盖的错误,算法已停止。没有可用的解决方案信息。 |
LimitProto
当 Solve() 通过 TerrationReasonProto FEASIBLE 或 NO_SOLUTION_FOUND 提前停止时,达到了所达到的特定限制。
枚举 | |
---|---|
LIMIT_UNSPECIFIED |
在我们未受限制终止(例如 TERMINATION_REASON_OPTIMAL)时用作 null 值。 |
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。 TerdefinitionProto.detail 可能包含有关此限制的更多信息。 |
ProblemStatusProto
求解器声明的基本问题及其双重(或持续放宽的双重)的可行性状态。求解器无需为版权主张返回证书(例如,求解器可以声称具备基本可行性,而不会返回原始可行的解决方案)。这种组合状态全面描述了求解器关于所解决问题的可行性和无限性的声明。例如:
- 原始问题和对偶问题的可行状态表示原始问题是可行且有界限的,并且可能有最优解决方案(对于没有非线性约束的问题,保证)。
- 原始可行状态和双重不可行状态表示原始问题是无界限的(即具有任意好解)。
请注意,这种两种不可行状态本身(即附带未确定的原始状态)并不意味着原始问题是无限制的,因为我们可能让这两个问题都不可行。此外,虽然原始和双重可行状态可能暗示存在最佳解决方案,但这并不能保证求解器确实已经找到这种最佳解决方案。
JSON 表示法 |
---|
{ "primalStatus": enum ( |
字段 | |
---|---|
primalStatus |
主要问题的状态。 |
dualStatus |
双重问题(或持续放松的双重问题)的状态。 |
primalOrDualInfeasible |
如果为 true,求解器会声称此原始问题或双重问题不可行,但它不知道哪个(或者两者都不可行)。仅当 primal_problem_status = dual_problem_status = kUnspecifiedd 时,才为 true。在预处理确定没有问题的最佳解决方案时,通常需要这些额外信息(但无法确定是由于不可行、无限性或二者皆有)。 |
FeasibilityStatusProto
求解器声明的问题可行性状态(求解器无需为声明返回证书)。
枚举 | |
---|---|
FEASIBILITY_STATUS_UNSPECIFIED |
表示无状态的保护值。 |
FEASIBILITY_STATUS_UNDETERMINED |
求解器不会声明状态。 |
FEASIBILITY_STATUS_FEASIBLE |
Solver 声称此问题是可行的。 |
FEASIBILITY_STATUS_INFEASIBLE |
Solver 声称这个问题不可行。 |
ObjectiveBoundsProto
最佳目标值的边界。
JSON 表示法 |
---|
{ "primalBound": number, "dualBound": number } |
字段 | |
---|---|
primalBound |
求解器声明最优值等于或优于 primalBound,达到求解器原始可行性(见以下警告):* primalBound 微不足道(+inf 用于最小化,-inf 最大化),当求解器没有声明拥有此边界时。* primalBound 可能更接近最佳值,而不是最佳原始可行解决方案的目标。特别是,即使没有返回初始可行解,primalBound 也可能非常重要。警告:确切地说,存在以下基本解决方案:* 在数值上可行(即在求解器容限范围内可行),且 * 的目标值为 primalBound。这种在数值上可行的解决方案可能不太可行,在这种情况下,primalBound 可以绝对优于最佳值。将原始可行性容忍度转换为对 primalBound 的公差非常重要,尤其是在可行性容差相对较大时(例如,使用 PDLP 解决问题时)。 |
dualBound |
求解器声明最优值等于或小于 dualBound(对于最小化,最大为最大),小于 dualBound,最高为求解器双重可行性(请参见下面的警告):* 如果求解器未声明拥有此边界,则 dualBound 无关紧要(-inf 代表最小化,+inf 最大化)。与 primalBound 类似,即使返回最佳求解器,某些求解器也可能会发生这种情况。通常,MIP 求解器会报告限制,即使该限制并不精确。* 对于连续问题,dualBound 可能比最佳双可行解决方案的目标更接近最佳值。对于 MIP,dualBound 的一个重要值通常是 MIP 的 LP 放宽的最佳值。* dualBound 应该优于 primalBound(用于最小化,大于 primalBound),最高可达到求解器公差(请参阅下面的警告)。警告:* 对于连续问题,确切的说法是存在一种双重解:* 在数值上可行(即在求解器容限范围内可行),* 的目标值为 dualBound。这种在数值上可行的解决方案可能不太可行,在这种情况下,dualBound 可能会远远低于最佳值和 primalBound。与原始情况类似,将双重可行性公差转换为 dualBound 的公差是非常重要的,尤其是在可行性公差相对较大时。不过,有些求解器会提供经过更正的 dualBound 版本,它可以在数值上更安全。您可以通过求解器的特定输出访问该更正后的版本(例如,对于 PDLP,可以使用 pdlp_output.convergence_information.corrected_dual_objective)。* 对于 MIP 求解器,dualBound 可能与一些连续放宽(例如 LP 放宽)的双解相关联,但这通常是求解器执行的一个复杂结果,并且通常比 LP 求解器报告的边界更为不精确。 |
SolutionProto
解决方案中包含的内容取决于问题的类型和求解器。目前的常见模式是 1。MIP 求解器仅返回原始解决方案。2. 单层 LP 求解器通常会返回一个基础,以及与该基础相关的原始解和双重解。3. 其他连续求解器通常会返回原始解和双解,这些解根据求解器的形式连接在一起。
要求:* 必须至少设置一个字段;解决方案不得为空。
JSON 表示法 |
---|
{ "primalSolution": { object ( |
字段 | |
---|---|
primalSolution |
|
dualSolution |
|
basis |
|
PrimalSolutionProto
一种优化问题的解决方案。
例如,假设有一个简单的线性程序:min c * x s.t. A * x >= b x >= 0。一种基本解决方案是为 x 赋值。如果满足上述 A * x >= b 且 x >= 0,则是可行的。在下面的消息 PrimalSolutionProto 中,variableValues 为 x,goalValue 为 c * x。
JSON 表示法 |
---|
{ "variableValues": { object ( |
字段 | |
---|---|
variableValues |
要求:*variableValues.ids 是 VariablesProto.ids 的元素。* variableValues.values 都必须是有限值。 |
objectiveValue |
由底层求解器计算的目标值。不能为无限或 NaN。 |
auxiliaryObjectiveValues |
由底层求解器计算的辅助目标值。键必须是有效的辅助目标 ID。值不能为无限或 NaN。 包含一系列 |
feasibilityStatus |
根据底层求解器的解决方案的可行性状态。 |
DualSolutionProto
优化问题对偶的解。
例如,假设原始双对线性节目对:(Primal) (Dual) min c * x max b * y s.t. A * x >= b s.t. y * A + r = c x >= 0 y, r >= 0。双重解是对 (y, r)。如果满足上述(二)项的约束条件是可行的。
在下面的消息中,y 是 dualValues,r 是 savedCosts,b * y 是目标值。
JSON 表示法 |
---|
{ "dualValues": { object ( |
字段 | |
---|---|
dualValues |
要求:* dualValues.ids 是 LinearConstraints.ids 的元素。* dualValues.values 都必须是有限值。 |
reducedCosts |
要求:*reduceCosts.ids 是 VariablesProto.ids 的元素。* reduceCosts.values 必须是有限值。 |
feasibilityStatus |
根据底层求解器的解决方案的可行性状态。 |
objectiveValue |
|
PrimalRayProto
优化问题无限改进的方向;等效于优化问题双重求解不可行的证书。
例如,设想一个简单的线性程序:min c * x s.t。A * x >= b x >= 0。原始射线是满足 c * x < 0 A * x >= 0 x >= 0 的 x,可得到更好的解,且仍然是可行的原始射线也证明双重优化问题不可行。
在下面的消息 PrimalRay 中,variableValues 为 x。
JSON 表示法 |
---|
{
"variableValues": {
object ( |
字段 | |
---|---|
variableValues |
要求:*variableValues.ids 是 VariablesProto.ids 的元素。* variableValues.values 都必须是有限值。 |
DualRayProto
一种无限改进优化问题的双方面发展方向;相当于从根本上不可行的证明。
例如,假设原始双对线性节目对:(Primal) (Dual) min c * x max b * y s.t. A * x >= b s.t. y * A + r = c x >= 0 y, r >= 0。双射线是满足两个条件 (y, r) 的对:b * y > 0 y * A + r = 0 y, r >= 0。请注意,向双可行解决方案添加 (y, r) 的正倍数可保持双可行性并改进目标(前提是双重可行)。双射线也证明了原始问题是不可行的。
在下面的消息 DualRay 中,y 是 dualValues 且 r 是优惠成本。
JSON 表示法 |
---|
{ "dualValues": { object ( |
字段 | |
---|---|
dualValues |
要求:* dualValues.ids 是 LinearConstraints.ids 的元素。* dualValues.values 都必须是有限值。 |
reducedCosts |
要求:*reduceCosts.ids 是 VariablesProto.ids 的元素。* reduceCosts.values 必须是有限值。 |
SolveStatsProto
JSON 表示法 |
---|
{
"solveTime": string,
"problemStatus": {
object ( |
字段 | |
---|---|
solveTime |
由 math_opt 测量的已用时钟时间,大致为 Solver::Solve() 内部的时间。注意:这不包括完成的模型构建时间。 此时长以秒为单位,最多包含九个小数位,以“ |
problemStatus |
原始问题和双重问题的可行性状态。 |
simplexIterations |
|
barrierIterations |
|
firstOrderIterations |
|
nodeCount |
|