解析輸入模型並一次傳回結果。如果您不需要回呼、成效增幅,且不需要追蹤解題進度,請使用這個選項。
HTTP 要求
POST https://optimization.googleapis.com/v1/mathopt:solveMathOptModel
這個網址使用 gRPC 轉碼語法。
要求主體
要求主體的資料會採用以下結構:
JSON 表示法 |
---|
{ "solverType": enum ( |
欄位 | |
---|---|
solverType |
選用設定。以數值表示解題工具類型。請注意,如果解題工具不支援模型中的特定功能,最佳化程序就無法成功。 |
model |
必要欄位。以數學方式表示待解決的最佳化問題。 |
parameters |
選用設定。控制單一解題的參數。系統會特別處理 enableOutput 參數。如果是支援訊息回呼的解題工具,如果設為 true,伺服器就會登錄訊息回呼。產生的訊息會在 ResolveMathOptModelResponse.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 和非 convex 整數二元問題。不過,系統不會傳回 LP 的雙重資料。將 GLOP 用於 LP。 |
SOLVER_TYPE_GUROBI |
Gurobi 解題工具 (第三方)。 支援 LP、MIP 和非 convex 整數二元問題。這通常是最快的選項,但有特殊授權。 |
SOLVER_TYPE_GLOP |
Google 的 Glop 解題工具 支援採用基本和雙 Simplex 方法的 LP。 |
SOLVER_TYPE_CP_SAT |
Google 的 CP-SAT 解題工具 支援所有變數為整數且受限制 (或默示為解析後) 的問題。實驗性支援,可對持續的變數重新調整及區分問題。 |
SOLVER_TYPE_PDLP |
Google 的 PDLP 解題工具 支援到達網頁和對話式對角線二度目標。使用第一排序方法,而非 Simplex。這能解決非常大的問題 |
SOLVER_TYPE_GLPK |
GNU 線性程式設計套件 (GLPK) (第三方)。 支援 MIP 和 LP。 執行緒安全:GLPK 使用執行緒本機儲存空間來分配記憶體。因此,求解器執行個體建立時必須在同一個執行緒上刪除,否則 GLPK 會異常終止。從用來建立求解器的執行緒呼叫「Resolver::Resolver」看起來似乎沒問題,但 GLPK 並未記錄此問題,因此應避免。 使用解析器解決 LP 問題時,只有在找到最佳解決方案時,才會傳回解決方案 (和不繫結的光線)。除此之外不會傳回任何結果。詳情請參閱 glpk-5.0.tar.gz 提供的 glpk-5.0/doc/glpk.pdf 第 40 頁 。 |
SOLVER_TYPE_OSQP |
運算子 Splitting Quadratic Program (OSQP) 解題器 (第三方)。 支援線性限制和線性或凸面二次目標的持續問題。使用先排序方法。 |
SOLVER_TYPE_ECOS |
嵌入式 Conic 求解器 (ECOS) (第三方)。 支援 LP 和 SOCP 問題。使用內部點方方法 (障礙)。 |
SOLVER_TYPE_SCS |
The Splitting Conic Resolver (SCS) (第三方) 工具。 支援 LP 和 SOCP 問題。使用先排序方法。 |
SOLVER_TYPE_HIGHS |
HiGHS 求解器 (第三方)。 支援到達網頁和 MIP 問題 (未實作對話 QP)。 |
SOLVER_TYPE_SANTORINI |
MathOpt 參考實作的 MIP 解題工具。 速度過慢/不建議在正式環境中使用。不是 LP 解題工具 (未傳回雙重資訊)。 |
ModelProto
最佳化問題。MathOpt 支援:- 包含持續和整數決策變數,可選用有限的有限範圍。- 線性和二次目標 (單一或多個目標),可以最小化或最大化。- 一些限制類型,包括:* 線性限制 * 二次序限制 * 第二順位錐 * 邏輯限制 > SOS1 和 SOS2 限制 > 指標限制
根據預設,限制條件是以「 ID 到資料」對應表示。不過,我們使用更有效率的「陣列結構」格式表示線性限制條件。
JSON 表示法 |
---|
{ "name": string, "variables": { object ( |
欄位 | |
---|---|
name |
|
variables |
|
objective |
模型中的主要目標, |
auxiliaryObjectives |
用於多目標模型的輔助目標。 對應鍵 ID 必須介於 [0, max(int64)]。每個優先順序和每個非空白名稱皆不得重複,而且不得與主要 這個物件中包含 |
linearConstraints |
|
linearConstraintMatrix |
線性限制條件的變數係數。 如果刪除這項限制涉及的變數,則會視為設為零。 需求條件:* LinearConstraintMatrix.row_ids 是 LinearConstraints.ids 的元素。* LinearConstraintMatrix.column_ids 是變數的元素。* 未指定矩陣項目為零。* LinearConstraintMatrix.values 必須全部設為有限值。 |
quadraticConstraints |
模型中的二次限制。 這個物件中包含 |
secondOrderConeConstraints |
模型中的第二順位錐。 這個物件中包含 |
sos1Constraints |
模型中的 SOS1 限制條件,會限制最多一個 這個物件中包含 |
sos2Constraints |
模型中的 SOS2 限制,限制了最多兩個 這個物件中包含 |
indicatorConstraints |
模型中的指標限制會強制規定,如果二元「指標變數」設為一,就必須保留「默示限制」。 這個物件中包含 |
VariablesProto
如下方所示,我們定義「#variables」= size(VariablesProto.ids)。
JSON 表示法 |
---|
{ "ids": [ string ], "lowerBounds": [ number ], "upperBounds": [ number ], "integers": [ boolean ], "names": [ string ] } |
欄位 | |
---|---|
ids[] |
不得為負數,並嚴格遞增。max(int64) 值無法使用。 |
lowerBounds[] |
長度應等於 #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 術語。 需求條件:* LinearCoefficiencys.ids 是 VariablesProto.ids 的元素。* 未指定 VariablesProto 會對應到零。* LinearCoefficiencys.values 必須全部為有限。* LinearCoefficiencys.values 可以是零,但這只會浪費空間。 |
quadraticCoefficients |
決策變數中的客觀字詞。 除了 SparseDoubleMatrixProto 訊息之外的規定:* quadraticCoefficiencys.row_ids 的每個元素和 quadraticCoefficiencys.column_ids 的每個元素都必須是 VariablesProto.ids 的元素。* 矩陣必須為上三角形:每個 i, 四分位數係數.row_ids[i] <= quadraticCoefficiencys.column_ids[i]。 附註: * 未明確儲存的字詞具有零係數。* 二次方程式的元素可設為零,但這只是浪費空間。 |
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
如下方所示,我們定義「#Linearconstraints = 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} +Sum{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, 四角條款.row_ids[i] <= quadraticTerms.column_ids[i]。 附註: * 未明確儲存的字詞具有零係數。* quadraticTerms.coefficiencys 的要素可設為零,但這只是浪費空間。 |
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) ꛭ 下邊界 <= 運算式 <= topBound。
如果與這項限制相關的變數 (指標或顯示在 expression
中) 遭到刪除,系統就會將其視為設為零。具體來說,刪除指標變數表示如果 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) 的參數。如果同時在常用和解題工具專用欄位中設定值,系統就會使用解題工具專用設定。
選用的常見參數為選用參數和未設定的參數,或是含有未指定值的列舉,則表示使用解題器預設值。
除非使用中的解題工具,否則系統會忽略解題工具的特定參數。
需根據模型的參數 (例如為每個變數設定分支優先順序) 會傳遞到 ModelResolveParametersProto 中。
JSON 表示法 |
---|
{ "timeLimit": string, "enableOutput": boolean, "lpAlgorithm": enum ( |
欄位 | |
---|---|
timeLimit |
解題工具應花費多少時間來解決問題 (如果未設定,則為無限時間)。 這個值並非硬性限制,解決時間可能會略為超過這個值。這個參數一律會傳送給基礎解題工具,不使用解題工具預設值。 時間長度以秒為單位,最多可有 9 個小數位數,並結尾為「 |
enableOutput |
允許列印解題工具實作追蹤記錄。這些追蹤記錄的位置取決於解題工具。針對 SCIP 和 Gurobi,這會是標準輸出串流。如果是 Glop 和 CP-SAT,這會記錄(INFO)。 請注意,如果解題工具支援訊息回呼,且使用者註冊了回呼的回呼,則系統會忽略此參數值,也不會顯示任何追蹤記錄。 |
lpAlgorithm |
用於解決線性程式的演算法。如為 LP_ALGORITHM_UNSPECIFIED,請使用解題工具預設演算法。 如果是非線性程式的問題,但線性程式設計是子處理常式,解題工具則可使用這個值。例如 MIP 解題工具通常僅用於根 LP 解題 (在其他情況下則使用雙 Simplex 解題)。 |
presolve |
在啟動主要演算法前努力簡化問題,或者如果使用 FOR_UNSPECIFIED,則解題器預設的工作程度。 |
cuts |
會盡力提高 LP 的放鬆成效 (僅限 MIP),或是如果使用 EMPHASIS_UNSPECIFIED,則解題工具的預設處理程度。 注意:停用剪接可能可避免回呼有機會在 MIP_NODE 新增剪輯,此行為是解決器特有的。 |
heuristics |
除了完整搜尋程序中的解決方案外,也能夠輕鬆找出可行的解決方案 (僅限 MIP),或是為 EMPHASIS_UNSPECIFIED 提供解題工具預設的工作量。 |
scaling |
積極調整問題來提高數值穩定性,或者如果 FOR_UNSPECIFIED,則解題器預設的工作量。 |
iterationLimit |
限制基礎演算法的疊代作業 (例如 Simplex 資料透視)。具體行為視解題工具及演算法而定,但通常可以提供確定性解決限制 (可能需要進一步設定,例如一個執行緒)。 通常受 LP、QP 和 MIP 解題工具支援,但如果是 MIP 解題工具,則可參閱 nodeLimit。 |
nodeLimit |
限制列舉搜尋中解決的子問題數量 (例如分支版本和繫結)。對許多解題工具而言,這種方式可決定精確限制運算能力 (可能需要進一步設定,例如一個執行緒)。 一般來說,如果使用 MIP 解題工具,請參閱疊代 Limit。 |
cutoffLimit |
如果解題工具可以證明沒有基本解決方案或終止效果相較良好,則解題工具會提早停止。 早期,解題工具會傳回終止原因 NO_SOLUTION_FOUND 且限制 CUTOFF,且不需要提供任何額外的解決方案資訊。如果沒有提前停靠站,傳回值就不會有任何影響。 如果希望目標與終止作業完全相符,建議您採用容忍度。 如需詳細資訊,以及有關 BestBoundLimit 的比較,請參閱使用手冊。 |
objectiveLimit |
一旦找到一個以上的解決方案,解題工具就會盡早停止,且終止原因並且限制行動。 |
bestBoundLimit |
一旦證明最佳界限至少達到這個目標,解題工具就會立即停止作業,終止原因為 FEASIBLE 或 NO_SOLUTION_FOUND 並限制 OBJECTIVE。 如需詳細資訊,請參閱使用手冊和 deckoffLimit 的比較資訊。 |
solutionLimit |
找到許多可行的解決方案後,解題工具會盡早停止,且終止原因並降低解決方案。必須大於零 (如有設定)。大家通常會使用這個方法,讓求解器停止第一個可行的解決方案。請注意,不保證任何傳回解決方案的目標價值。 求解器傳回的解決方案通常不會超過解決方案限制,但這並非由 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 達到最絕對平衡 (設定時) 並傳回 TERMINATION_REASON_OPTIMAL 時,解譯器可以停止。 必須大於或等於 0 (如果已設定)。 另請參閱「relativeGapTolerance」相關說明。 |
relativeGapTolerance |
相對於 MIP 解題工具的相對最佳性容忍度 (主要為)。 相對 GAP 是絕對 GAP (以絕對 GapTolerance 定義) 的正規化版本,其中正規化需依賴解題工具。舉例來說,將絕對 GAP 除以最佳可行解決方案的目標值後,所得出的數值。 在相對 GAP 設為最相對 GapTolerance (設定時) 的情況下,解題工具可以停止,並傳回 TERMINATION_REASON_OPTIMAL。 必須大於或等於 0 (如果已設定)。 另請參閱絕對 GapTolerance。 |
solutionPoolSize |
搜尋時最多更新 |
LPAlgorithmProto
選取用來解決線性程式的演算法。
列舉 | |
---|---|
LP_ALGORITHM_UNSPECIFIED |
|
LP_ALGORITHM_PRIMAL_SIMPLEX |
(原始) Simplex 方法。一般來說,您可以選擇提供原始和雙重解,針對主要/雙重問題和基本問題提供基本/雙射線索。 |
LP_ALGORITHM_DUAL_SIMPLEX |
雙 Simplex 方法。一般來說,您可以選擇提供原始和雙重解,針對主要/雙重問題和基本問題提供基本/雙射線索。 |
LP_ALGORITHM_BARRIER |
阻隔方法,通常稱為內部點方法 (IPM)。通常可以同時提供原始和雙重解決方案。有些實作也會在無界/無法解決的問題上產生光線。除非基礎解題工具會「交叉轉移」並採用 Simplex 完成,否則系統不會提供基準。 |
LP_ALGORITHM_FIRST_ORDER |
以第一順位方法為基礎的演算法。這類解決方案通常會產生基本和雙重解決方案,也可能是初級和/或雙權不可的證明。第一排序方法提供的解決方案通常準確度較低,因此使用者應謹慎設定解決方案品質參數 (例如容忍度),並驗證解決方案。 |
EmphasisProto
在解題時適用於選用工作的難易度 (請參閱 SolveParametersProto 的說明)。
強調效果的用途是設定解題工具功能,如下所示:* 如果解題工具不支援該功能,則只有 UNSPECIFIED 一律有效,其他設定一般都會導致無效的引數錯誤 (部分解題工具也可能接受「關閉」)。* 如果解題工具支援此功能:- 設為 UNSPECIFIED 時,系統會使用基本預設值。- 無法關閉功能時,「關閉」會傳回錯誤。- 如果這項功能預設為啟用,解題工具預設會對應至 MEDIUM。- 如果功能支援,「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) 中相應變數所傳回的 Sparse 容器。 需求條件:* filterIds 是 VariablesProto.ids 的元素。 |
dualValuesFilter |
這個篩選器會套用至 DualSolutionProto 和 DualRay (DualSolutionProto.dual_values、DualRay.dual_values) 中設有線性限制所傳回的所有 sparse 容器。 需求條件:*filterIds 是 LinearConstraints.ids 的元素。 |
reducedCostsFilter |
這個篩選器會套用至 DualSolutionProto 和 DualRay (DualSolutionProto.reduced_costs、DualRay.reduced_costs) 中由變數存在的所有傳回的稀疏容器。 需求條件:* filterIds 是 VariablesProto.ids 的元素。 |
initialBasis |
選用暖啟動 Simplex LP 解題工具的初始基礎。如果已設定,會根據目前 |
solutionHints[] |
可選用的解決方案提示。如果基礎解題工具只接受單一提示,則會使用第一個提示。 |
branchingPriorities |
選用的分支優先順序。值較高的變數會先分支。如未設定優先順序的變數,則會取得解題工具的預設優先順序 (通常為零)。 需求條件:*分支 Priorities.values 必須為有限值。* 分支版本 ingPriorities.ids 必須是 VariablesProto.ids 的元素。 |
SparseVectorFilterProto
這則訊息允許查詢/設定 SparseXxxxVector 的特定部分。預設行為並不會篩除任何項目。常見的用法是僅查詢解決方案的某些部分 (僅查詢非零值及/或手動挑選的一組變數值)。
JSON 表示法 |
---|
{ "skipZeroValues": boolean, "filterByIds": boolean, "filteredIds": [ string ] } |
欄位 | |
---|---|
skipZeroValues |
SparseBoolVectorProto 的「zero」為 |
filterByIds |
如果為 true,則只傳回與 filterIds 中所列 ID 相對應的值。 |
filteredIds[] |
系統在 filterByIds 為 true 時要使用的 ID 清單。如果 filterByIds 為 false,就必須留空。注意:如果這個欄位空白,且 filterByIds 為 true,即代表您不希望結果中的任何資訊。 |
BasisProto
線性程式解決方案的組合特性。
用來解決線性程式的 Simplex 方法一律會傳回「基本可行的解決方案」,此解決方案可透過 Basis 描述合併。基礎會為每個變數和線性限制指派 BasisStatusProto。
舉例來說,假設標準格式是到達網頁: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 在某些極端案例中可能有所不同 (例如使用原始 Simplex 的不完整解析)。 如果您透過 ModelResolveParametersProto.initial_basis 做為起點,系統會忽略這個值。這只與 SolutionProto.basis 傳回的依據相關。 |
SparseBasisStatusVector
基礎狀態向量的稀疏表示法。
JSON 表示法 |
---|
{
"ids": [
string
],
"values": [
enum ( |
欄位 | |
---|---|
ids[] |
所有元素都必須依遞增順序排序,且所有元素均不同。 |
values[] |
長度必須與 ID 相同。 |
BasisStatusProto
到達網頁中的變數/限制狀態。
列舉 | |
---|---|
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 |
解題工具聲稱解決方案可行。 |
SOLUTION_STATUS_INFEASIBLE |
解題工具聲稱該解法不可行。 |
SolutionHintProto
建議的解題工具起始解決方案。
MIP 解題工具通常只想使用原始資訊 (variableValues
),而 LP 解題工具則需要原始和雙重資訊 (dualValues
)。
許多 MIP 解題工具可以:(1) 部分解決方案未指定所有變數,或 (2) 無法實現的解決方案。在這類情況下,解題工具通常會解決子 MIP 的問題,以便完成/修正提示。
解題工具如何使用提示 (如果有設定的話),主要取決於解題工具、問題類型和使用的演算法。如要確保提示發揮效果,最可靠的方法就是讀取基礎解題工具記錄,並在其中包含及不使用提示。
以 Simplex 為基礎的 LP 求解器通常會偏好初步基礎,因此會需要交叉運用,將提示轉換成基本可行的解決方案。
JSON 表示法 |
---|
{ "variableValues": { object ( |
欄位 | |
---|---|
variableValues |
可能是將部分值指派給問題的原始變數。此子訊息的解題工具獨立規定為:*variableValues.ids 是 VariablesProto.ids 的元素。* varValues.values 必須全部為有限值。 |
dualValues |
將值指派至問題的線性限制條件 (可能是部分)。 需求:* doubleValues.ids 是 LinearConstraintsProto.ids 的元素。* TwoValues.values 必須全部為有限。 |
SparseInt32VectorProto
整數向量的稀疏表示法。
JSON 表示法 |
---|
{ "ids": [ string ], "values": [ integer ] } |
欄位 | |
---|---|
ids[] |
應按順序遞增排序,而且所有元素都不同。 |
values[] |
長度必須與 ID 相同。 |
SolveResultProto
基本/雙解解決方案/射線的合約複雜,如需完整說明,請參閱 End_reasons.md。
在完全合約敲定前,建議您只檢查是否存在解決方案/灰色,而不要仰賴終止原因。
JSON 表示法 |
---|
{ "termination": { object ( |
欄位 | |
---|---|
termination |
解題工具停止的原因。 |
solutions[] |
日後解題工具應採取的通解順序原則如下:1. 提供採用基本可行解決方案的解決方案,以最佳入門目標排序。2. 提供雙可行解決方案的解決方案,按照最佳雙目標排序 (未知的雙目標最為嚴重) 3. 其餘解決方案可按任何順序退回。 |
primalRays[] |
介紹了無可匹敵的初衷改善方法,或同等的雙可行性認證。通常針對 TerminationReasonProtos UNBOUNDED 和 DUAL_INFEASIBLE 提供 |
dualRays[] |
說明無限的雙重改進 (或相等的根本不可行認證指示)。通常針對 TerminationReasonProto INFEASIBLE 提供。 |
solveStats |
解題程序的統計資料,例如執行時間、疊代次數。 |
TerminationProto
所有有關 Resolve() 呼叫終止的原因的相關資訊。
JSON 表示法 |
---|
{ "reason": enum ( |
欄位 | |
---|---|
reason |
如果值為 TERMINATION_REASON_FEASIBLE 或 TERMINATION_REASON_NO_SOLUTION_FOUND,請參閱 |
limit |
為 LIMIT_UNSPECIFIED,除非原因為 TERMINATION_REASON_FEASIBLE 或 TERMINATION_REASON_NO_SOLUTION_FOUND。並非所有解題工具都能判斷導致終止的原因,在無法判斷原因時會使用 LIMIT_UNDETERMINED。 |
detail |
其他一般解題工具專屬終止資訊。 |
problemStatus |
原始和雙重問題的可行性狀態。自 2023 年 7 月 18 日起,這封郵件可能遺失。如果缺少此項目,您可以在 SolveResultProto.solve_stats 中找到 issueStatus。 |
objectiveBounds |
最佳目標值的範圍。自 2023 年 7 月 18 日起,這封郵件可能遺失。如果缺少此項目,可在 SolveResultProto.solve.stats.best_primal_bound 和 goalBounds.dual_bound 中找到 bSPF |
TerminationReasonProto
呼叫 Solve() 終止的原因。
列舉 | |
---|---|
TERMINATION_REASON_UNSPECIFIED |
|
TERMINATION_REASON_OPTIMAL |
結果發現一個確實最理想的解決方案 (最多可達數值容忍度)。 |
TERMINATION_REASON_INFEASIBLE |
原始問題沒有可行的解決方案。 |
TERMINATION_REASON_UNBOUNDED |
主要問題是可行的,也是合理的解決方法。 |
TERMINATION_REASON_INFEASIBLE_OR_UNBOUNDED |
基本問題是無法解決的,也可能不受限。如果想進一步瞭解問題狀態,請參閱 helpStats.problem_status。請注意,Gurobi 的無限制狀態可能對應在這裡。 |
TERMINATION_REASON_IMPRECISE |
問題已解決,而且符合上述其中一項條件 (Optimal、Infeasible、Unbounded 或 InfeasibleOrUnbounded),但不符合一或多項容忍度。可能會提供一些基本/雙解解決方案/反射,但他們可能會有些微不可能,或者 (如果問題已近乎最佳) 可能與最佳解決方案目標和最佳目標繫結之間存在落差。 使用者仍可查詢基本/雙解解決方案/射線和解法統計資料,但他們需負責處理數值的精確度。 |
TERMINATION_REASON_FEASIBLE |
最佳化工具已達某種限制,並傳回一個可行的解決方案。請參閱 SolveResultProto.limit_detail ,進一步瞭解已達的限制類型。 |
TERMINATION_REASON_NO_SOLUTION_FOUND |
最佳化工具已達到某種限制,但並未找到基本可行的解決方案。請參閱 SolveResultProto.limit_detail ,進一步瞭解已達的限制類型。 |
TERMINATION_REASON_NUMERICAL_ERROR |
演算法發生無法復原的數值錯誤,因此已停止。無法提供解決方案資訊。 |
TERMINATION_REASON_OTHER_ERROR |
發生上述其中一個狀態未涵蓋的錯誤,導致演算法停止。無法提供解決方案資訊。 |
LimitProto
如果 Solve() 以 TerminationReasonProto FEASIBLE 或 NO_SOLUTION_FOUND 的方式提早停止,就會達到達到的特定上限。
列舉 | |
---|---|
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 |
演算法停止了,因為找到的解決方案或繫結超過使用者設定的限制 (請參閱 ResolveParameters.objective_limit 和 SolveParameters.best_bound_limit)。 |
LIMIT_NORM |
疊代頻率過大,因此演算法已停止。 |
LIMIT_INTERRUPTED |
發生中斷信號或使用者中斷要求,因此演算法已停止。 |
LIMIT_SLOW_PROGRESS |
演算法無法繼續採用解決方案,因此已停止。 |
LIMIT_OTHER |
由於超出上述其中一項上限,演算法已停止。請注意,當系統無法判斷原因時,就會使用 LIMIT_UNDETERMINED,且在已知原因無法使用上述任一替代字詞時,則使用 LIMIT_OTHER。 TerminationProto.detail 可能包含限制的額外資訊。 |
ProblemStatusProto
解題工具宣稱原始問題的可行性狀態,及其雙重 (或持續放鬆的雙重)。解題工具不需要傳回這個組合狀態會完整說明解題工具對於解開問題的可行性和無限程度的說法。舉例來說:
- 基本和雙重問題的可行狀態表示原始和雙重問題的可行且有限,且可能擁有最佳解決方法 (保證適用於沒有非線性限制的問題)。
- 最小可行性,且雙不可行的狀態表示原始問題尚未無界限 (意即毫無爭議)。
請注意,如果兩個問題本身無法完全解決,並不表示原始問題已無界限 (如果伴隨無法確定的初級狀態)。此外,基本和雙可行性狀態可能意味著找到最佳解決方案,但不保證解題工具確實找到了最佳解決方案。
JSON 表示法 |
---|
{ "primalStatus": enum ( |
欄位 | |
---|---|
primalStatus |
原始問題的狀態。 |
dualStatus |
雙問題的狀態 (或持續放鬆的雙重問題狀態)。 |
primalOrDualInfeasible |
如果為 true,解題工具宣稱基本或雙重問題無法執行,但不知道該問題為何 (或兩者皆不可行)。只有在 primal_problem_status = Two_problem_status = kUndefinedd 時,才有可能為 true。如果預先處理判定問題沒有最佳解決方案,您通常需要提供這些額外資訊 (但因為無法判斷問題是出自於性或不受限,還是兩者皆是)。 |
FeasibilityStatusProto
解題工具主張的問題可行性狀態 (不需要為解題傳回憑證)。
列舉 | |
---|---|
FEASIBILITY_STATUS_UNSPECIFIED |
代表無狀態的防護值。 |
FEASIBILITY_STATUS_UNDETERMINED |
求解工具不會聲明狀態。 |
FEASIBILITY_STATUS_FEASIBLE |
解題工具表示問題是否可行。 |
FEASIBILITY_STATUS_INFEASIBLE |
解題工具聲稱問題不可能。 |
ObjectiveBoundsProto
最佳目標值的範圍。
JSON 表示法 |
---|
{ "primalBound": number, "dualBound": number } |
欄位 | |
---|---|
primalBound |
解題工具聲稱最佳值等於或優於解題器原始的可行性,則小於或優於 primalBound (最小化可最大化,而較大者) 與 primalBound 相同 (請參閱下方警告):* primalBound 是微小 (+inf 表示最小化和 -inf 最大化)。* primalBound 可以更接近最佳值,而非最符合最佳基本可行解決方案的目標。特別要注意的是,即使未傳回可行的解決方案,primalBound 仍有可能並不重要。警告:確切說法是指現有的基本解法為:* 可為數值可行 (亦即在解題工具容許範圍內),而 * 具有客觀值 primalBound。這個可行的數值可能略為不可行,在這種情況下,primalBound 可以確實優於最佳值。將原始可行性容忍度轉化為 primalBound 的容忍度具有非凡性,尤其在可行性相對較大的情況下 (例如使用 PDLP 解決時)。 |
dualBound |
解題工具聲稱最佳值等於或更差 (盡可能最小化,以最大化的方式最大化,最大化;如果達到最大化,則比 DuBound 更小),而與解題工具的雙可行性相較 (請參閱下面的警告內容):* 在解題工具並未宣稱,與 primalBound 類似,部分解題工具即使傳回最佳結果,也會發生這種情形。即使 MIP 解題工具不夠精確,仍會回報繫結。* 表示連續性問題,DoubleBound 可以更接近最佳值,而不是最佳的雙可行性解決方案的目標。DuBound 是 MIP 的第一項重要值,通常就是 MIP 的 LP 放鬆設定的最佳值。* 比起 primalBound,在解題器的容忍度更佳 (請參閱下方警告),則雙重邊界應該比 primalBound 要更小,才能達到最大化。警告:* 如為持續性問題,準確聲明為現有雙重解法為:* 值可行 (亦即在解題工具容忍度上可行),而 * 具有客觀值 DuBound。這個數字可行的解決方案可能略為不可行,在這種情況下,DoubleBound 可能會嚴重低於最佳值和 primalBound。與原始案例類似,將雙可行性容忍度轉化為 DoubleBound 的容忍度是非常重要的,尤其是當可行性容忍度相對較大時。不過,部分解題工具提供的 DuBound 修正版本較安全。您可以透過解題工具的特定輸出內容 (例如 PDLP、pdlp_output.convergence_information.corrected_dual_objective) 存取這個修正版本。* 對 MIP 解題器而言,DoubleBound 可能會與進行某些持續放鬆 (例如 LP 放鬆) 的雙重解決方案相關聯,但這通常是解題工具的執行結果相當複雜,而且通常比 LP 解題器回報的邊界更不精確。 |
SolutionProto
解決方案包含的內容會因問題類型和解題工具而異。目前的常見模式為 1。MIP 解題工具只會傳回基本解決方案,2. Simplex 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 的元素。* varValues.values 必須全部為有限值。 |
objectiveValue |
基礎解題工具計算出的目標值。不得為無限或 NaN。 |
auxiliaryObjectiveValues |
由基礎解題工具計算出的輔助目標值。鍵必須是有效的輔助目標 ID。值不得為無限或 NaN。 這個物件中包含 |
feasibilityStatus |
根據基礎解題工具算出的解決方案的可行性狀態。 |
DualSolutionProto
解決雙重最佳化問題的解決方案。
例如雙解則是配對 (y、r)。可以符合上述 (Dual) 的限制。
在下方訊息中,y 是 DuValues,r 是縮減成本,b * y 則是「目標值」。
JSON 表示法 |
---|
{ "dualValues": { object ( |
欄位 | |
---|---|
dualValues |
需求:* doubleValues.ids 是 LinearConstraints.ids 的元素。* TwoValues.values 必須全部為有限。 |
reducedCosts |
需求條件:*lessCosts.ids 是 VariablesProto.ids 的元素。* 減低 Costs.values 必須全部為無限。 |
feasibilityStatus |
根據基礎解題工具算出的解決方案的可行性狀態。 |
objectiveValue |
|
PrimalRayProto
針對最佳化問題帶來無限可能的進步方向;同樣地,這是最佳化問題雙重不確定性的憑證。
例如,假設有一個簡單的線性程式:最小值 c * x s.t。 A * x >= b x >= 0 原型為符合以下需求的 x:c * x < 0 A * x >= 0 x >= 0 觀察,如果給予原始光學也證明瞭雙重最佳化問題是不可能的。
在下方的訊息 PrimalRay 中,variableValues 為 x。
JSON 表示法 |
---|
{
"variableValues": {
object ( |
欄位 | |
---|---|
variableValues |
需求:*variableValues.ids 是 VariablesProto.ids 的元素。* varValues.values 必須全部為有限值。 |
DualRayProto
對最佳化雙重技術帶來無可限量的進步方向;這等同於原始不可行的證書。
例如雙反射 (y, r) 能滿足組合 (y, r) 滿足下列條件:b * y > 0 y * A + r = 0 y,r >= 0 觀察,將正數的 (y, r) 增加雙可行性解決方案,不但能維持雙可行性,還能改善目標 (證明雙重皆不受限制)。此外,雙射光也證明瞭基本問題是無法辦到的。
在以下訊息中,DualRay 表示 y 是 DualValues,且 r 是縮減成本。
JSON 表示法 |
---|
{ "dualValues": { object ( |
欄位 | |
---|---|
dualValues |
需求:* doubleValues.ids 是 LinearConstraints.ids 的元素。* TwoValues.values 必須全部為有限。 |
reducedCosts |
需求條件:*lessCosts.ids 是 VariablesProto.ids 的元素。* 減低 Costs.values 必須全部為無限。 |
SolveStatsProto
JSON 表示法 |
---|
{
"solveTime": string,
"problemStatus": {
object ( |
欄位 | |
---|---|
solveTime |
以 math_opt 測得的實時時鐘時間,約為 Resolver::Resolve() 內的時間。注意:這不包括建立模型完成的工作。 時間長度以秒為單位,最多可有 9 個小數位數,並結尾為「 |
problemStatus |
原始和雙重問題的可行性狀態。 |
simplexIterations |
|
barrierIterations |
|
firstOrderIterations |
|
nodeCount |
|