入力モデルを解いて、結果を一度に返します。コールバックやインクリメンタリティが不要で、解決の進捗状況を追跡する必要がない場合に使用します。
HTTP リクエスト
POST https://optimization.googleapis.com/v1/mathopt:solveMathOptModel
この URL は gRPC Transcoding 構文を使用します。
リクエスト本文
リクエストの本文には、次の構造のデータが含まれます。
JSON 表現 |
---|
{ "solverType": enum ( |
フィールド | |
---|---|
solverType |
省略可。問題を数値的に解くための解法タイプ。解法がモデル内の特定の特徴をサポートしていない場合、最適化手順は成功しません。 |
model |
必須。解く最適化問題を数学的に表したもの。 |
parameters |
省略可。単一の解をコントロールするパラメータ。enableOutput パラメータは特別に処理されます。メッセージ コールバックをサポートするソルバーの場合、true に設定すると、サーバーはメッセージ コールバックを登録します。生成されたメッセージは SolveMathOptModelResponse.messages で返されます。他のソルバーでは、enableOutput を true に設定すると、エラーが発生します。 |
modelParameters |
省略可。入力モデルに固有の単一の解法を制御するパラメータ(モデルに依存しないパラメータについては、SolveParametersProto をご覧ください)。 |
レスポンスの本文
MathOpt での単項リモート解法に対するレスポンス。
成功すると、レスポンスの本文に次の構造のデータが含まれます。
JSON 表現 |
---|
{
"result": {
object ( |
フィールド | |
---|---|
result |
リクエストに含まれるモデルの解法による出力の説明。 |
messages[] |
SolveParametersProto.enable_output が使用されている場合は、メッセージ コールバックをサポートするソルバーのログメッセージが含まれます。 |
SolverTypeProto
MathOpt でサポートされている解法。
列挙型 | |
---|---|
SOLVER_TYPE_UNSPECIFIED |
|
SOLVER_TYPE_GSCIP |
制約整数プログラム(SCIP)の解法(サードパーティ)。 LP、MIP、非凸整数二次問題をサポートします。ただし、LP の二重データは返されません。LP には GLOP を優先する。 |
SOLVER_TYPE_GUROBI |
Gurobi のソルバー(サードパーティ)。 LP、MIP、非凸整数二次問題をサポートします。一般的には最も速い方法ですが、特別なライセンスが必要になります。 |
SOLVER_TYPE_GLOP |
Google の Glop ソルバー。 プライマル メソッドとデュアル シンプレックス メソッドで LP をサポートします。 |
SOLVER_TYPE_CP_SAT |
Google の CP-SAT ソルバー。 すべての変数が整数で有限である(または暗黙のうちに presolve の後に存在することになる)問題をサポートします。連続変数を使用して問題を再スケーリングおよび離散化するための試験運用版のサポート。 |
SOLVER_TYPE_PDLP |
Google の PDLP ソルバーです LP と凸対角二次方程式をサポートします。シンプレックスではなく 1 次メソッドを使用します。非常に大きな問題を解決できます。 |
SOLVER_TYPE_GLPK |
GNU リニア プログラミング キット(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)ソルバー(サードパーティ)。 線形制約と線形または凸の二次目標を持つ連続的な問題をサポートします。1 次メソッドを使用します。 |
SOLVER_TYPE_ECOS |
The Embedded Conic Solver(ECOS)(サードパーティ)。 LP と SOCP の問題をサポート。内部ポイント方式(バリア)を使用します。 |
SOLVER_TYPE_SCS |
分割円錐ソルバー(SCS)(サードパーティ)。 LP と SOCP の問題をサポート。1 次メソッドを使用します。 |
SOLVER_TYPE_HIGHS |
HiGHS Solver(サードパーティ)。 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 |
モデル内の 2 次円錐制約。
|
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[] |
長さは #変数と同じにする必要があります。連続変数の値は false、整数変数の値は true です。 |
names[] |
設定されていない場合、すべて空の文字列とみなされます。それ以外の場合は、長さを #variables にする必要があります。 空でない名前は、すべて重複していない必要があります。 |
ObjectiveProto
JSON 表現 |
---|
{ "maximize": boolean, "offset": number, "linearCoefficients": { object ( |
フィールド | |
---|---|
maximize |
false が最小、true が最大 |
offset |
NaN ではなく、有限でなければなりません。 |
linearCoefficients |
決定変数において線形である ObjectiveProto の用語。 要件: * linearCoefficients.ids は VariablesProto.ids の要素です。* 指定されていない VariablesProto はゼロになります。* linearCoefficients.values はすべて有限である必要があります。* linearCoefficients.values をゼロにできますが、その場合はスペースが浪費されるだけです。 |
quadraticCoefficients |
決定変数において二次関数となる客観的な用語。 SparseDoubleMatrixProto メッセージの要件以外の要件: * quadraticCoefficients.row_ids の各要素と quadraticCoefficients.column_ids の各要素は VariablesProto.ids の要素である必要があります。* 行列は上三角形でなければなりません。つまり、各 i に対して、quadraticCoefficients.row_ids[i] <= quadraticCoefficients.column_ids[i] になります。 注: * 明示的に保存されていない用語の係数はゼロです。* quadraticCoefficients.coefficients の要素をゼロにできますが、これは単にスペースを浪費するだけです。 |
name |
親メッセージでは、このフィールドに一意性の要件を設定できます(例: ModelProto.objectives と AuxiliaryObjectivesUpdatesProto.new_objectives)。 |
priority |
多目的問題の場合、他の目標に対するこの目標の優先度(低いほど重要)。この値は負でない値にする必要があります。さらに、モデルの各客観的優先度は、解決時に異なるものでなければなりません。この条件はプロトコル レベルでは検証されないため、モデルに一時的に同じ優先度の目標が設定されている場合があります。 |
SparseDoubleVectorProto
倍精度ベクトルのスパース表現。
JSON 表現 |
---|
{ "ids": [ string ], "values": [ number ] } |
フィールド | |
---|---|
ids[] |
すべての要素が異なる、(昇順で)並べ替える必要があります。 |
values[] |
ID と同じ長さにする必要があります。NaN を含めることはできません。 |
SparseDoubleMatrixProto
倍精度行列のスパース表現。
行列は、行 ID、列 ID、係数のトリプルとして保存されます。これら 3 つのベクトルは、同じ長さにする必要があります。すべての 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[] |
長さは #線形制約に等しく、値は [-inf, inf) にする必要があります。 |
upperBounds[] |
長さは #線形制約に等しく、値は (-inf, inf] の範囲) である必要があります。 |
names[] |
設定されていない場合、すべて空の文字列とみなされます。それ以外の場合、長さは #線形制約と等しい 空でない名前は、すべて重複していない必要があります。 |
QuadraticConstraintProto
lb <= sum{linearTerms} + sum{quadraticTerms} <= ub の形式の 1 つの二次制約。
この制約に関連する変数が削除されると、ゼロに設定されたものとして処理されます。
JSON 表現 |
---|
{ "linearTerms": { object ( |
フィールド | |
---|---|
linearTerms |
決定変数において線形の用語。 SparseDoubleVectorProto メッセージの要件に加えて、以下が必要です。* linearTerms.ids は VariablesProto.ids の要素です。* linearTerms.values はすべて有限であり、NaN ではない必要があります。 注: * 省略された変数 ID は、対応する係数が 0 です。* linearTerms.values はゼロにできますが、その場合はスペースが浪費されるだけです。 |
quadraticTerms |
決定変数において二次関数である項。 * quadraticTerms.row_ids の各要素と quadraticTerms.column_ids の各要素は、VariablesProto.ids の要素にする必要があります。* 行列は上三角形でなければなりません。つまり、i ごとに quadraticTerms.row_ids[i] <= quadraticTerms.column_ids[i] となります。 注: * 明示的に保存されていない用語の係数はゼロです。* quadraticTerms.coefficients の要素をゼロにできますが、これは単にスペースを浪費するだけです。 |
lowerBound |
[-inf, inf) の値を持ち、 |
upperBound |
値は(-inf, inf])で、 |
name |
親メッセージには、このフィールドで一意性の要件を指定できます。たとえば、ModelProto.quadratic_constraints と QuadraticConstraintUpdatesProto.new_constraints をご覧ください。 |
SecondOrderConeConstraintProto
次の形式の 1 つの 2 次コーン制約:
||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: 0 以外の値を取る要素は 1 つまで。* SOS2: 最大 2 つの要素がゼロ以外の値を取り、繰り返し順序において隣接していなければなりません。 |
weights[] |
空、または式と同じ長さ。空の場合、デフォルトの重みは 1、2、... です。存在する場合、エントリは一意である必要があります。 |
name |
親メッセージでは、このフィールドで一意性の要件を指定できます。たとえば、ModelProto.sos1_constraints と SosConstraintUpdatesProto.new_constraints をご覧ください。 |
IndicatorConstraintProto
次の形式の単一インジケーター制約を表すデータ: Variable(indicatorId) = (activateOnZero ?0 : 1) ⇒lowerBound <= 式 <= upperBound.
この制約に関連する変数(インジケーターまたは 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、または設定されていない 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 の場合は LOG(INFO) です。 ソルバーがメッセージ コールバックをサポートしており、ユーザーがそのコールバックを登録している場合、このパラメータ値は無視され、トレースは出力されません。 |
lpAlgorithm |
線形計画を解くアルゴリズム。LP_ALGORITHM_UNSPECIFIED の場合は、ソルバーのデフォルト アルゴリズムを使用します。 線形計画ではないが、線形計画法がサブルーチンである問題では、解法でこの値を使用できます。たとえば、MIP ソルバーは通常、ルート LP ソルバーにのみこれを使用します(それ以外の場合はデュアル シンプレックスを使用します)。 |
presolve |
メインのアルゴリズムを開始する前に問題を簡素化する取り組み、または、ソルバーのデフォルトの労力レベルが INSTANCE_UNSPECIFIED の場合。 |
cuts |
より強い LP 緩和(MIP のみ)を得るための労力、またはソルバーのデフォルトの労力レベルが AGENT_UNSPECIFIED の場合。 注: カットを無効にすると、コールバックが MIP_NODE にカットを追加できなくなる場合があります。この動作はソルバー固有です。 |
heuristics |
完全な検索手順(MIP のみ)、またはソルバーのデフォルトの労力レベル(INSTANCE_UNSPECIFIED)で見つかる範囲を超えて、実行可能な解決策を見つける労力。 |
scaling |
数値の安定性を改善するための問題の再スケーリングの労力。または、ソルバーのデフォルトの作業量レベルが ENCE_UNSPECIFIED の場合。 |
iterationLimit |
基になるアルゴリズムの反復回数の制限(例: シンプレックス ピボット)。具体的な動作は、使用するソルバーとアルゴリズムによって異なりますが、多くの場合、決定論的な解法限界を与える可能性があります(1 つのスレッドなど、さらなる構成が必要になる場合があります)。 通常、LP、QP、MIP ソルバーでサポートされますが、MIP ソルバーの場合は nodeLimit も参照してください。 |
nodeLimit |
列挙検索(例: 分岐や境界など)で解決できるサブ問題の数を制限する。多くのソルバーでは、これを使用して計算を決定論的に制限できます(1 つのスレッドなど、さらに構成が必要になる場合があります)。 通常、MIP ソルバーの場合は、iterationLimit もご覧ください。 |
cutoffLimit |
少なくともカットオフと同程度の優れた基本解がないことを証明できる場合、解法は早期に停止します。 早期停止では、解法は終了理由 NO_SOLUTION_FOUND を上限 CUTOFF とともに返します。追加の解情報を提供する必要はありません。早期停止がない場合、戻り値には影響しません。 目的がカットオフと完全に一致する解答が返されるようにする場合は、許容値を使用することをおすすめします。 詳細と、bestBoundLimit との比較については、ユーザーガイドをご覧ください。 |
objectiveLimit |
解法は、少なくともこの良好な解が見つかるとすぐに停止し、終了理由が「FEASIBLE」で、「OBJECTIVE」が制限されます。 |
bestBoundLimit |
最適な境界が少なくともこの良好であることが証明されると、ソルバーはすぐに停止します。終了理由は FEASIBLE または NO_SOLUTION_FOUND で、制限は OBJECTIVE です。 詳細と、CutoffLimit との比較については、ユーザーガイドをご覧ください。 |
solutionLimit |
実現可能な多くの解が見つかって早期に停止し、終了理由が「実行可能」で、「解決策」が限られています。設定する場合は 0 より大きい値を指定してください。多くの場合、解法が最初に見つかった実行可能な解で止めるために使用されます。なお、返される解決策の客観値は保証されません。 通常、ソルバーは解の上限を超える解を返すことはありませんが、これは MathOpt によって強制されません。b/214041169 も参照してください。 現在、Gurobi と SCIP、および CP-SAT では値 1 のみがサポートされています。 |
threads |
設定する場合は、1 以上にする必要があります。 |
randomSeed |
基盤となるソルバーの疑似乱数ジェネレータのシードです。すべての解法は、疑似乱数を使用して、LP アルゴリズムにおける摂動などの選択、タイ分割のルール、ヒューリスティックな固定を行うことに注意してください。これを変えると、解法の動作に大きな影響を与える可能性があります。 すべてのソルバーにはシードという概念がありますが、有効な値は実際のソルバーによって異なります。- Gurobi: [0:GRB_MAXINT](Gurobi 9.0 では 2x10^9 です)- GSCIP: [0:2147483647](MAX_INT、kint32max、または 2^31-1)。- GLOP: [0:2147483647](同上) すべてのケースで、解法は MAX(0, MIN(MAX_VALID_VALUE_FOR_SOLVER, randomSeed)) に等しい値を受け取ります。 |
absoluteGapTolerance |
(主に)MIP ソルバーの絶対最適度許容差。 絶対ギャップは、* 見つかった最適な実現可能な解の客観値 * 検索によって生成される二重境界の差の絶対値です。ソルバーは、絶対 GAP が absoluteGapTolerance 以下であれば(設定されている場合)、停止し、TERMINATION_REASON_OPTIMAL を返すことができます。 設定する場合は 0 以上にする必要があります。 「relativeGapTolerance」もご覧ください。 |
relativeGapTolerance |
(主に)MIP ソルバーの相対最適度許容度。 相対 GAP は絶対 GAP(絶対 GapTolerance で定義)の正規化バージョンであり、正規化は解法に依存します。たとえば、絶対 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)の変数をキーとする、返されたすべてのスパース コンテナに適用されるフィルタ。 要件: * filterId は VariablesProto.ids の要素です。 |
dualValuesFilter |
DualSolutionProto と DualRay の線形制約をキーとする、返されたすべてのスパース コンテナに適用されるフィルタ(DualSolutionProto.dual_values、DualRay.dual_values)。 要件: * filterId は LinearConstraints.ids の要素です。 |
reducedCostsFilter |
DualSolutionProto と DualRay(DualSolutionProto.reduced_costs、DualRay.reduced_costs)の変数をキーとする、返されたすべてのスパース コンテナに適用されるフィルタ。 要件: * filterId は VariablesProto.ids の要素です。 |
initialBasis |
ウォーム スタートのシンプレックス LP ソルバーのオプションの初期ベース。設定されている場合、現在の |
solutionHints[] |
ソリューションのヒント(省略可)。基盤となるソルバーが 1 つのヒントのみを受け入れる場合は、最初のヒントが使用されます。 |
branchingPriorities |
オプションの分岐優先度。値が大きい変数から先に分岐されます。優先度が設定されていない変数には、解法のデフォルトの優先度(通常はゼロ)が適用されます。 要件: * branchingPriorities.values は有限である必要があります。* branchingPriorities.ids は VariablesProto.ids の要素にする必要があります。 |
SparseVectorFilterProto
このメッセージにより、SparseXxxxVector の特定の部分に対してクエリや設定を行うことができます。デフォルトの動作では、何も除外されません。一般的な用途は、ソリューションの一部のみ(ゼロ以外の値や、手動で選択した変数値のセット)のみをクエリすることです。
JSON 表現 |
---|
{ "skipZeroValues": boolean, "filterByIds": boolean, "filteredIds": [ string ] } |
フィールド | |
---|---|
skipZeroValues |
SparseBoolVectorProto の場合、「zero」は |
filterByIds |
true の場合、filteredIds にリストされている ID に対応する値のみが返されます。 |
filteredIds[] |
filterByIds が true の場合に使用する ID のリスト。filterByIds が false の場合は空にする必要があります。注: これが空で、filterByIds が true の場合は、結果に情報が含まれないことを意味します。 |
BasisProto
線形プログラムの解に対する組み合わせ特性。
線形計画法を解くシンプレックス法は、常に「基本的な実行可能な解」を返します。これは、ベーシスによって組み合わせ的に記述できます。基底では、すべての変数と線形制約に BasisStatusProto が割り当てられます。
たとえば、制約よりも多くの変数を持ち、行全体のランクが A の標準形 LP: min c * x s.t. A * x = b x >= 0 を考えてみましょう。
変数の数を n、線形制約の数を m とします。この問題の有効な基礎は、以下のように構築できます。* すべての制約は、基底ステータスが「FIXED」になります。* A の列が線形に独立するように m 個の変数を選択し、ステータス「BASIC」を割り当てます。* 残りの n ~ m 個の変数にステータス AT_LOWER を代入する。
この基礎に関する基本的な解は、ステータスが AT_LOWER のすべての変数が下限(すべてゼロ)に固定されている、A * x = b の一意の解です。結果として得られる解を、x >= 0 も満たす場合を基本実現可能解と呼びます。
JSON 表現 |
---|
{ "constraintStatus": { object ( |
フィールド | |
---|---|
constraintStatus |
制約ベースのステータス。 要件: * constraintStatus.ids が LinearConstraints.ids と等しい |
variableStatus |
変数ベースのステータス。 要件: * constraintStatus.ids が VariablesProto.ids と等しい |
basicDualFeasibility |
これは、最適とはいえない LP ソリューションの実現可能性を評価するために MathOpt が使用する高度な機能です(最適なソリューションは常に 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 |
ソルバーが、そのソリューションは実現可能であると主張している。 |
SOLUTION_STATUS_INFEASIBLE |
解決役は、そのソリューションは実現不可能であると主張している。 |
SolutionHintProto
ソルバーに対して推奨される開始ソリューション。
通常、MIP ソルバーは基本情報(variableValues
)のみを必要としますが、LP ソルバーは基本情報と二重情報の両方(dualValues
)を必要とします。
多くの MIP ソルバーは、(1)すべての変数を指定していない部分解、または(2)実行不可能な解と併用できます。このような場合、ソルバーは通常、ヒントを補完/修正するためにサブ MIP を解決します。
解法でヒントがどのように使用されるかは、解法、問題のタイプ、使用するアルゴリズムに大きく依存します。ヒントの効果を確認する最も信頼できる方法は、ヒントの有無にかかわらず、基盤となるソルバーのログを読み取ることです。
一般的に、シンプレックス ベースの 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
原理/二重解/射線が複雑な場合の規定。詳細な説明については、termining_reasons.md をご覧ください。
正確な契約が確定するまでは、契約解除の理由に頼るのではなく、ソリューション/レイが存在するかどうかを単純に確認することをおすすめします。
JSON 表現 |
---|
{ "termination": { object ( |
フィールド | |
---|---|
termination |
解法が停止した理由。 |
solutions[] |
将来のソルバーが実装する必要があるソリューションの順番は、一般的に次の基準で決められます。1. 実現可能な主要なソリューションを含むソリューションを、最も望ましい基本目標の順に並べます。2. 実現可能なデュアル ソリューションを含むソリューションを、最適なデュアル目標(未知のデュアル目標が最悪)の順に並べます。3. 残りのソリューションはすべて、任意の順序で返品できます。 |
primalRays[] |
無限の根本的な改善、または同等の二重実行不可能証明書。通常、TerminationReasonProtos UNBOUNDED と DUAL_INFEASIBLE に提供されます |
dualRays[] |
無限の二重改善、または同等の主要な非実現可能性証明書の方向性。通常、TerminationReasonProto 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 日現在、このメッセージは存在しない可能性があります。指定されていない場合、 problemStatus は SolveResultProto.solve_stats で確認できます。 |
objectiveBounds |
最適な目標値の範囲。2023 年 7 月 18 日現在、このメッセージは存在しない可能性があります。欠落している場合、ObjectiveBounds.primal_bound は SolveResultProto.solve.stats.best_primal_bound にあり、ObjectiveBounds.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、Unbounded、InfeasibleOrUnbounded)で問題が解決されたが、1 つ以上の許容差を満たしていない。いくつかの原理/二重解/光線は存在しますが、それらはわずかに実行不可能であるか、または(問題がほぼ最適である場合)最適解と目的境界のギャップである可能性があります。 ユーザーは引き続き基本/二重解/射影と解の統計情報をクエリできますが、数値の不精度に対処する責任があります。 |
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 |
制限以外で終了した場合に null 値として使用されます(TERMINATION_REASON_OPTIMAL など)。 |
LIMIT_UNDETERMINED |
基になるソルバーでは、どの制限に達したかは公開されません。 |
LIMIT_ITERATION |
反復アルゴリズムが最大反復回数(シンプレックスやバリア反復など)を行ったら停止した。 |
LIMIT_TIME |
ユーザーが指定した計算時間の経過後にアルゴリズムが停止した。 |
LIMIT_NODE |
「ブランチ アンド バインド」ツリー内の最大数のノードを探索したため、ブランチ アンド バインド アルゴリズムが停止しました。 |
LIMIT_SOLUTION |
必要な数の解が見つかったため、アルゴリズムが停止しました。これは、解法が最初に遭遇した実行可能な解を返すようにするために、MIP でよく使用されます。 |
LIMIT_MEMORY |
メモリ不足のため、アルゴリズムが停止しました。 |
LIMIT_CUTOFF |
ソルバーを目標にカットオフ(例: SolveParameters.cutoff_limit が設定された)を指定して実行しました。これは、ユーザーがそのカットオフより悪い解を望まないことを示し、ソルバーは少なくともそのカットオフ以上の解は存在しないと結論付けました。通常、これ以上のソリューション情報は提供されません。 |
LIMIT_OBJECTIVE |
解法またはユーザーが設定した制限値(SolveParameters.objective_limit および SolveParameters.best_bound_limit を参照)よりも適切な境界を見つけたため、アルゴリズムが停止しました。 |
LIMIT_NORM |
反復のノルムが大きすぎるため、アルゴリズムが停止しました。 |
LIMIT_INTERRUPTED |
割り込み信号またはユーザー割り込みリクエストが原因でアルゴリズムが停止しました。 |
LIMIT_SLOW_PROGRESS |
解決に向けた処理を続行できなかったため、アルゴリズムが停止しました。 |
LIMIT_OTHER |
上記のいずれにも該当しない制限のため、アルゴリズムが停止しました。LIMIT_UNDETERMINED は理由が特定できない場合に使用されます。LIMIT_OTHER は、理由がわかっているが上記のいずれの選択肢にも当てはまらない場合に使用します。 TerminationProto.detail には、制限に関する追加情報が含まれる場合があります。 |
ProblemStatusProto
解法が主張する基本問題とその二重(または連続緩和の二重)の実現可能性状態。ソルバーは、クレームについて証明書を返す必要はありません(たとえば、ソルバーは、主要な実現可能な溶解を返さずに主要な実現可能性を主張できる)。この複合的なステータスにより、解決された問題の実現可能性と無限性に関する解法の主張が包括的に説明されます。次に例を示します。
- 原数問題と二重問題の実行可能状態とは、原理が実行可能で有限であり、最適な解がある可能性が高いことを意味します(非線形制約のない問題に対して保証されます)。
- 主要な実行可能ステータスと二重実行不可能なステータスは、主要な問題が無限にある(つまり、任意の適切な解決策がある)ことを示します。
二重実行不可能な状態(つまり、未決定の基本状態を伴う)は、両方の問題が実現不可能である可能性があるため、基本の問題が無限にあることを意味しません。また、基本的かつ二重の実現可能な状況は、最適解が存在することを示唆しているかもしれませんが、解法がそのような最適解を実際に見つけたことを保証するものではありません。
JSON 表現 |
---|
{ "primalStatus": enum ( |
フィールド | |
---|---|
primalStatus |
主要な問題のステータス。 |
dualStatus |
二重問題(または連続緩和の二重の問題)のステータス。 |
primalOrDualInfeasible |
true の場合、解法は基本問題または二重の問題は実現不可能であると主張しますが、どちらが実現可能かはわかりません(または両方が実現不可能かどうか)。primal_problem_status = dual_problem_status = kUncertaind の場合にのみ、true となります。この追加情報が必要になるのは、問題に対する最適な解決策がないと前処理が判断した場合です(ただし、それが実現可能性、無限性、またはその両方によるものかを判断できない場合)。 |
FeasibilityStatusProto
ソルバーが主張する問題の実現可能性ステータス(ソルバーは申し立てに対して証明書を返す必要はありません)。
列挙型 | |
---|---|
FEASIBILITY_STATUS_UNSPECIFIED |
ステータスなしを表すガード値。 |
FEASIBILITY_STATUS_UNDETERMINED |
ソルバーがステータスを申請していません。 |
FEASIBILITY_STATUS_FEASIBLE |
ソルバーが問題は実現可能であると主張している。 |
FEASIBILITY_STATUS_INFEASIBLE |
ソルバーが問題は実現不可能であると主張している。 |
ObjectiveBoundsProto
最適な目標値の範囲。
JSON 表現 |
---|
{ "primalBound": number, "dualBound": number } |
フィールド | |
---|---|
primalBound |
ソルバーは、最適値が primalBound と、ソルバーの主要な実現可能性の許容差まで同等以上(最小化の場合は小さい、最大化の場合は大きい)であると主張しています(以下の警告を参照)。* primalBound は、実現可能な最適なソリューションの目標よりも最適値に近づくことができる。特に、primalBound は、実現可能な主要なソリューションが返されないとしても、重要でない場合があります。警告: 正確な主張は、* が数値的に実行可能(すなわち、解法の許容値まで実行可能)であり、* が客観的値 primalBound を持つ基本解が存在するということです。この数値的に実現可能な解決策は、わずかに実行不可能であり、その場合、primalBound が最適値よりも厳密に改善される可能性があります。特に実現可能性の許容範囲が比較的大きい場合(PDLP で解く場合など)、主要な実現可能性の許容値を primalBound の許容値に変換するのは容易ではありません。 |
dualBound |
ソルバーは、最適値が dualBound より(最小化の場合は大きく、最大化の場合は小さい)ソルバーの二重実現可能性の許容値以下であると主張しています(以下の警告を参照)。* dualBound は単純です(最小化の場合は -inf、最大化の場合は最大化)。primalBound と同様に、ソルバーによっては、最適な値を返してもこの現象が発生することがあります。MIP ソルバーは通常、それが不正確であっても境界を報告します。* 連続的な問題の場合、dualBound は最適な二重化可能なソリューションの目標よりも最適値に近づく可能性があります。MIP の場合、dualBound の最初の非自明値の 1 つは、多くの場合、MIP の LP 緩和の最適値です。* dualBound は、ソルバーの許容範囲までは primalBound よりも小さく(最小化では小さく、最大化では大きい)べきです(以下の警告を参照)。警告: * 連続問題の場合、厳密に言えば、* が数値的に実行可能(すなわち、解法の許容値まで実行可能)で、* が客観値 dualBound を持つ二重解が存在するということです。この数値的に実現可能な解決策は、わずかに現実的でない可能性があります。この場合、dualBound は最適値や primalBound よりも厳しく悪化する可能性があります。基本的なケースと同様に、デュアル 実現可能性の許容範囲を dualBound の許容値に変換するのは容易ではありません。特に実現可能性の許容範囲が比較的大きい場合です。ただし、一部のソルバーでは、数値的に安全性の高い dualBound の修正版が提供されています。この修正バージョンには、ソルバー固有の出力(例: PDLP の場合は pdlp_output.convergence_information.corrected_dual_objective)からアクセスできます。* MIP ソルバーの場合、dualBound はなんらかの連続緩和(LP 緩和など)のために二重解と関連付けられることがありますが、多くの場合、ソルバー実行の複雑な結果であり、通常は LP ソルバーによって報告される境界よりも精度が低くなります。 |
SolutionProto
ソリューションに何が含まれるかは、問題の種類と解法によって異なります。現在の一般的なパターンは 1 です。MIP ソルバーは主要な解のみを返します。2. シンプレックス LP は、多くの場合、基底とその基底に関連する基本解と二重解を返します。3.他の連続解法では、多くの場合、解法に依存する形で結合された元解と二重解の解が返されます。
要件: * 少なくとも 1 つのフィールドを設定する必要があります。ソリューションは空白にできません。
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、ObjectiveValue が c * x です。
JSON 表現 |
---|
{ "variableValues": { object ( |
フィールド | |
---|---|
variableValues |
要件: * variableValues.ids は VariablesProto.ids の要素です。* variableValues.values はすべて有限である必要があります。 |
objectiveValue |
基になるソルバーによって計算された客観値。無制限または NaN は指定できません。 |
auxiliaryObjectiveValues |
基になるソルバーによって計算された補助目的値。鍵は有効な補助目標 ID である必要があります。値を無限大または NaN にすることはできません。
|
feasibilityStatus |
基盤となるソルバーに基づくソリューションの実現可能性ステータス。 |
DualSolutionProto
2 つの最適化問題の解決策。
例: (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) のペアです。上記の(Dual)の制約を満たしていることが実現可能です。
以下のメッセージでは、y は dualValues、r は discountCosts、b * y は客観的な値です。
JSON 表現 |
---|
{ "dualValues": { object ( |
フィールド | |
---|---|
dualValues |
要件: * dualValues.ids は LinearConstraints.ids の要素です。* dualValues.values はすべて有限である必要があります。 |
reducedCosts |
要件: * reduceCosts.ids は VariablesProto.ids の要素です。* ReducedCosts.values はすべて有限でなければなりません。 |
feasibilityStatus |
基盤となるソルバーに基づくソリューションの実現可能性ステータス。 |
objectiveValue |
|
PrimalRayProto
最適化の問題を無限に改善する方向。最適化の問題の二重が実現不可能であることを示す証明書と同等です。
例:min c * x s.t. A * x >= b x >= 0 という単純な線形計画を考える c * x < 0 A * x >= 0 x >= 0 である x * x < 0 A * x >= 0 x >= 0原子光線についても、二重最適化問題は実現不可能であることが証明されています。
以下のメッセージ 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。二重レイは、b * y > 0 y * A + r = 0 y, r >= 0 を満たすペア (y, r) です。二重実行可能解に正の倍数 (y, r) を追加すると、二重の実現可能性が維持され、目的が明確になります(二重が無限であることを証明する)。このデュアルレイは、この根本的な問題は実現不可能であることも証明しています。
以下の DualRay メッセージでは、y は dualValues で、r は discountCosts です。
JSON 表現 |
---|
{ "dualValues": { object ( |
フィールド | |
---|---|
dualValues |
要件: * dualValues.ids は LinearConstraints.ids の要素です。* dualValues.values はすべて有限である必要があります。 |
reducedCosts |
要件: * reduceCosts.ids は VariablesProto.ids の要素です。* ReducedCosts.values はすべて有限でなければなりません。 |
SolveStatsProto
JSON 表現 |
---|
{
"solveTime": string,
"problemStatus": {
object ( |
フィールド | |
---|---|
solveTime |
math_opt で測定される経過時間の経過時間。Solver::Solve() 内のおおよそ時間。注: モデルの構築が完了した作業は含まれません。 「 |
problemStatus |
主要な問題と二重の問題の実現可能性ステータス。 |
simplexIterations |
|
barrierIterations |
|
firstOrderIterations |
|
nodeCount |
|