Package google.research.optimization.v1.mathopt

Index

BasisProto

Eine kombinatorische Charakterisierung für eine Lösung in einem linearen Programm.

Die Simplex-Methode zum Lösen linearer Programme gibt immer eine "grundlegende durchführbare Lösung" zurück, die durch eine Basis kombinatorisch beschrieben werden kann. Eine Basis weist jeder Variablen und linearen Einschränkung einen BasisStatusProto zu.

Nehmen wir als Beispiel eine LP in Standardform: min c * x s.t. A * x = b x >= 0 mit mehr Variablen als Einschränkungen und mit vollständigem Zeilenrang A.

Lass n die Anzahl der Variablen und m die Anzahl der linearen Einschränkungen sein. Eine gültige Basis für dieses Problem kann wie folgt erstellt werden: * Alle Einschränkungen haben den Basisstatus FIXED. * Wählen Sie m Variablen so aus, dass die Spalten von A linear unabhängig sind und den Status BASIC zuweisen. * Weisen Sie den verbleibenden n - m Variablen den Status AT_LOWER zu.

Die grundlegende Lösung für diese Basis ist die einzigartige Lösung A * x = b, bei der alle Variablen mit dem Status AT_LOWER an ihren unteren Grenzen (alle null) fixiert sind. Die daraus resultierende Lösung wird als einfache durchsetzbare Lösung bezeichnet, wenn sie auch die Anforderung x >= 0 erfüllt.

Felder
constraint_status

SparseBasisStatusVector

Status der Einschränkungsgrundlage.

Anforderungen: * constraint_status.ids ist gleich LinearConstraints.ids.
variable_status

SparseBasisStatusVector

Variablenbasisstatus.

Anforderungen: * constraint_status.ids ist gleich VariablesProto.ids.
basic_dual_feasibility

SolutionStatusProto

Dies ist eine erweiterte Funktion, die von MathOpt verwendet wird, um die Durchführbarkeit von suboptimalen Lösungen für die Landingpage zu charakterisieren (optimale Lösungen haben immer den Status SOLUTION_STATUS_FEASIBLE).

Bei einseitigen LPs sollte dieser dem Machbarkeitsstatus der zugehörigen doppelten Lösung entsprechen. Bei zweiseitigen LPs kann es in einigen Sonderfällen abweichen (z.B. bei unvollständigen Lösungen mit einem ursprünglichen Simplex).

Wenn Sie eine Ausgangsbasis über ModelSolveParametersProto.initial_basis bereitstellen, wird dieser Wert ignoriert. Sie ist nur für die von SolutionProto.basis zurückgegebene Basis relevant.

BasisStatusProto

Status einer Variablen/Beschränkung auf LP-Basis.

Enums
BASIS_STATUS_UNSPECIFIED Guard-Wert, der keinen Status darstellt.
BASIS_STATUS_FREE Die Variable/Beschränkung ist kostenlos (sie hat keine endlichen Grenzen).
BASIS_STATUS_AT_LOWER_BOUND Die Variable/Beschränkung befindet sich an der Untergrenze (die endlich sein muss).
BASIS_STATUS_AT_UPPER_BOUND Die Variable/Beschränkung befindet sich an der Obergrenze (die endlich sein muss).
BASIS_STATUS_FIXED_VALUE Die Variable/Beschränkung hat identische endliche Unter- und Obergrenzen.
BASIS_STATUS_BASIC Die Variable/Einschränkung ist einfach.

DualRayProto

Eine Richtung der unbegrenzten Verbesserung des Dual einer Optimierung bzw. eines Problems; entsprechend ein Zertifikat der ursprünglichen Undurchführbarkeit.

Betrachten wir zum Beispiel das lineare Programmpaar des primären Dual-Paares: (Primal) (Dual) min c * x max b * y s.t. A * x >= b s.t. y * A + r = c x >= 0 y, r >= 0. Der Dual-Ray-Wert ist das Paar (y, r), das die folgenden Punkte erfüllt: b * y > 0 y * A + r = 0 y, r >= 0. Beobachten Sie, dass durch das Hinzufügen eines positiven Vielfachen von (y, r) zu einer zwei durchführbaren Lösung die doppelte Machbarkeit gewährleistet ist und das Ziel verbessert wird (was beweist, dass das Dual-Ray-Prinzip unbegrenzt ist). Der Dualstrahl beweist auch, dass das Grundproblem nicht umsetzbar ist.

In der nachstehenden Nachricht „DualRay“ steht y für „Dual_values“ und „r“ für „reduzierte_Kosten“.

Felder
dual_values

SparseDoubleVectorProto

Anforderungen: * Dual_values.ids sind Elemente von „LinearConstraints.ids“. * Dual_values.values müssen alle endlich sein.
reduced_costs

SparseDoubleVectorProto

Anforderungen: *„Reduced_costs.ids“ ist Elemente von „VariablesProto.ids“. * Reduce_costs.values müssen alle endlich sein.

DualSolutionProto

Eine Lösung für das Zweifache eines Optimierungsproblems.

Betrachten wir zum Beispiel das lineare Programmpaar des primären Dual-Paares: (Primal) (Dual) min c * x max b * y s.t. A * x >= b s.t. y * A + r = c x >= 0 y, r >= 0. Die doppelte Lösung ist das Paar (y, r). Dies ist machbar, wenn sie die oben genannten Einschränkungen (Dual) erfüllt.

In der folgenden Nachricht ist y dual_values, r ist reduzierte_Kosten und b * y ein Zielwert.

Felder
dual_values

SparseDoubleVectorProto

Anforderungen: * Dual_values.ids sind Elemente von „LinearConstraints.ids“. * Dual_values.values müssen alle endlich sein.
reduced_costs

SparseDoubleVectorProto

Anforderungen: *„Reduced_costs.ids“ ist Elemente von „VariablesProto.ids“. * Reduce_costs.values müssen alle endlich sein.
feasibility_status

SolutionStatusProto

Machbarkeitsstatus der Lösung entsprechend dem zugrunde liegenden Rechner.
objective_value

double

EmphasisProto

Der Aufwand, der beim Lösen einer optionalen Aufgabe auf eine optionale Aufgabe angewendet wird (siehe SolveParametersProto)

Mit Betonung wird eine Solver-Funktion folgendermaßen konfiguriert: * Wenn ein Matherechner die Funktion nicht unterstützt, ist nur UNSPECIFIED immer gültig. Alle anderen Einstellungen führen in der Regel zu einem Fehler wegen ungültiger Argumente (einige Solver akzeptieren möglicherweise auch AUS). * Wenn der Matherechner die Funktion unterstützt: – Wenn auf UNSPECIFIED festgelegt ist, wird der zugrunde liegende Standardwert verwendet. - Wenn die Funktion nicht deaktiviert werden kann, wird bei Verwendung von AUS ein Fehler zurückgegeben. – Wenn die Funktion standardmäßig aktiviert ist, wird der Matherechner normalerweise MITTELWERT zugeordnet. - Wenn das Element unterstützt wird, wird mit LOW, MEDIUM, HIGH und SEY HIGH kein Fehler ausgegeben und es wird die beste Übereinstimmung angezeigt.

Enums
EMPHASIS_UNSPECIFIED
EMPHASIS_OFF
EMPHASIS_LOW
EMPHASIS_MEDIUM
EMPHASIS_HIGH
EMPHASIS_VERY_HIGH

FeasibilityStatusProto

Status der Machbarkeit des Problems, wie vom Löser angegeben. Der Löser muss kein Zertifikat für den Anspruch zurückgeben.

Enums
FEASIBILITY_STATUS_UNSPECIFIED Guard-Wert, der keinen Status darstellt.
FEASIBILITY_STATUS_UNDETERMINED Solver beansprucht keinen Status.
FEASIBILITY_STATUS_FEASIBLE Der Löser behauptet, das Problem sei machbar.
FEASIBILITY_STATUS_INFEASIBLE Der Löser behauptet, das Problem sei nicht umsetzbar.

IndicatorConstraintProto

Daten zur Darstellung einer einzelnen Indikatoreinschränkung im folgenden Format: Variable(indicator_id) = (activate_on_zero ? 0 : 1) Δ Untergrenze <= Ausdruck <= Obergrenze.

Wenn eine Variable, die an dieser Einschränkung beteiligt ist (entweder der Indikator oder in expression erscheint), gelöscht wird, wird sie so behandelt, als wäre sie auf null gesetzt. Insbesondere bedeutet das Löschen der Indikatorvariable, dass die Indikatoreinschränkung leer ist, wenn activate_on_zero falsch ist, und dass sie einer linearen Einschränkung entspricht, wenn activate_on_zero wahr ist.

Felder
activate_on_zero

bool

Bei „true“ und wenn die Indikatorvariable den Wert 0 annimmt, muss die implizite Einschränkung gelten. Wenn die Indikatorvariable den Wert 1 annimmt, muss die implizite Einschränkung gelten.
expression

SparseDoubleVectorProto

Muss ein gültiger linearer Ausdruck in Bezug auf das enthaltende Modell sein: * Alle angegebenen Bedingungen für SparseDoubleVectorProto, * Alle Elemente von expression.values müssen endlich sein. * expression.ids ist eine Teilmenge von VariablesProto.ids.
lower_bound

double

Muss einen Wert in [-inf, inf] enthalten; darf nicht NaN sein.
upper_bound

double

Muss einen Wert in (-inf, inf] enthalten; darf nicht NaN sein.
name

string

Für übergeordnete Nachrichten gelten möglicherweise Anforderungen an die Eindeutigkeit dieses Feldes, z.B. „ModelProto.indicator_constraints“ und „IndicatorConstraintUpdatesProto.new_constraints“.
indicator_id

int64

ID, die einer Binärvariablen entspricht oder nicht festgelegt ist. Wenn die Richtlinie nicht konfiguriert ist, wird die Einschränkung des Indikators ignoriert. Wenn festgelegt, ist Folgendes erforderlich: * VariablesProto.integers[indicator_id] = true, * VariablesProto.lower_bounds[indicator_id] >= 0, * VariablesProto.upper_bounds[indicator_id] <= 1. Diese Bedingungen werden von MathOpt nicht validiert, wenn sie jedoch nicht erfüllt werden, gibt der Solver nach der Lösung einen Fehler zurück.

LPAlgorithmProto

Wählt einen Algorithmus zur Lösung linearer Programme aus.

Enums
LP_ALGORITHM_UNSPECIFIED
LP_ALGORITHM_PRIMAL_SIMPLEX Die (primäre) Simplex-Methode. In der Regel können Primär- und Dual-Lösungen, Prima-/Dualstrahlen für primäre/doppelte unbegrenzte Probleme und eine Basis bereitgestellt werden.
LP_ALGORITHM_DUAL_SIMPLEX Die Dual-Simplex-Methode. In der Regel können Primär- und Dual-Lösungen, Prima-/Dualstrahlen für primäre/doppelte unbegrenzte Probleme und eine Basis bereitgestellt werden.
LP_ALGORITHM_BARRIER Die Barrieremethode, auch als Interior Point Method (IPM) bezeichnet. Kann in der Regel sowohl Primär- als auch Dual-Lösungen liefern. Einige Implementierungen können auch Strahlen bei unbegrenzten/undurchführbaren Problemen erzeugen. Eine Basis wird nur angegeben, wenn der zugrunde liegende Solver ein Crossover durchführt und mit einem Uniformat beendet wird.
LP_ALGORITHM_FIRST_ORDER Algorithmus, der auf einer Methode der ersten Ordnung basiert. Mit ihnen werden in der Regel sowohl grundlegende als auch doppelte Lösungen sowie möglicherweise auch Zertifikate der ursprünglichen und/oder doppelten Durchführbarkeit erzeugt. First-Order-Methoden bieten in der Regel Lösungen mit geringerer Genauigkeit. Daher sollten Nutzer darauf achten, Parameter für die Lösungsqualität (z. B. Toleranzen) festzulegen und die Lösungen zu validieren.

LimitProto

Wenn ein Solve() vorzeitig mit TerminationReasonProto FEASIBLE oder NO_SOLUTION_FOUND endet, ist dies der spezifische Grenzwert, der erreicht wurde.

Enums
LIMIT_UNSPECIFIED Wird als Nullwert verwendet, wenn das Limit nicht eingehalten wurde (z.B. TERMINATION_REASON_OPTIMAL).
LIMIT_UNDETERMINED Der zugrunde liegende Solver erkennt nicht, welches Limit erreicht wurde.
LIMIT_ITERATION Ein iterativer Algorithmus, der nach der Durchführung der maximalen Anzahl von Iterationen beendet wurde (z.B. Simplex- oder Barriere-Iterationen).
LIMIT_TIME Der Algorithmus wurde nach einer vom Nutzer angegebenen Rechenzeit beendet.
LIMIT_NODE Ein Branch-and-bound-Algorithmus wurde gestoppt, da er die maximale Anzahl von Knoten im Branch-and-bound-Baum untersucht hat.
LIMIT_SOLUTION Der Algorithmus wurde angehalten, weil die erforderliche Anzahl von Lösungen gefunden wurde. Dies wird häufig in MIPs verwendet, damit der Solver die erste mögliche Lösung zurückgibt, die er findet.
LIMIT_MEMORY Der Algorithmus wurde beendet, weil nicht genügend Arbeitsspeicher vorhanden ist.
LIMIT_CUTOFF Der Matherechner wurde mit einem Grenzwert ausgeführt (z. B. „SolveParameters.cutoff_limit“ festgelegt) für das Ziel. Dies deutete darauf hin, dass der Nutzer keine Lösung wünschte, die schlechter als der Grenzwert war, und er kam zu dem Schluss, dass es keine Lösungen gibt, die mindestens so gut wie der Grenzwert sind. Normalerweise werden keine weiteren Lösungsinformationen angegeben.
LIMIT_OBJECTIVE Der Algorithmus wurde gestoppt, da entweder eine Lösung oder eine Grenze gefunden wurde, die über dem vom Nutzer festgelegten Grenzwert liegt (siehe SolveParameters.objective_limit und SolveParameters.best_bound_limit).
LIMIT_NORM Der Algorithmus stoppte, weil die Norm einer Iteration zu groß wurde.
LIMIT_INTERRUPTED Der Algorithmus wurde aufgrund eines Unterbrechungssignals oder einer Anforderung einer Nutzerunterbrechung gestoppt.
LIMIT_SLOW_PROGRESS Der Algorithmus wurde angehalten, weil er nicht weiter an der Lösung arbeiten konnte.
LIMIT_OTHER

Der Algorithmus wurde aufgrund eines Grenzwerts angehalten, der nicht durch eine der oben genannten Optionen abgedeckt ist. Beachten Sie, dass LIMIT_UNDETERMINED verwendet wird, wenn der Grund nicht ermittelt werden kann, und LIMIT_OTHER wird verwendet, wenn der Grund bekannt ist, aber zu keiner der oben genannten Alternativen passt.

TerminationProto.detail enthält möglicherweise zusätzliche Informationen zur Beschränkung.

LinearConstraintsProto

Wie unten verwendet, definieren wir "#linearconstraints" = size(LinearConstraintsProto.ids).

Felder
ids[]

int64

Darf nicht negativ und nur ansteigend sein. Der Wert „max(int64)“ kann nicht verwendet werden.
lower_bounds[]

double

Sollte die Länge der #linearen Einschränkungen entsprechen, Werte in [-inf, inf).
upper_bounds[]

double

Sollte die Länge der #linearen Einschränkungen entsprechen, Werte in (-inf, inf].
names[]

string

Wenn nichts festgelegt ist, werden alle leeren Strings angenommen. Andernfalls sollte die Länge der Länge von #linearen Einschränkungen entsprechen.

Alle nicht leeren Namen müssen eindeutig sein.

LinearExpressionProto

Eine dünnbesetzte Darstellung eines linearen Ausdrucks (eine gewichtete Summe von Variablen plus einem konstanten Offset).

Felder
ids[]

int64

IDs von Variablen. Muss (in aufsteigender Reihenfolge) sortiert werden, wobei sich alle Elemente unterscheiden müssen.
coefficients[]

double

Muss dieselbe Länge wie IDs haben. Die Werte müssen endlich sein und dürfen nicht NaN sein.
offset

double

Muss endlich sein und darf nicht NaN sein.

ModelProto

Ein Optimierungsproblem. MathOpt unterstützt: – Kontinuierliche und ganzzahlige Entscheidungsvariablen mit optionalen endlichen Grenzen. – Lineare und quadratische Ziele (ein oder mehrere), entweder minimiert oder maximiert. - Eine Reihe von Einschränkungstypen, darunter: * Lineare Einschränkungen * Quadratische Einschränkungen * Kegeleinschränkungen zweiter Ordnung * Logische Einschränkungen > SOS1- und SOS2-Einschränkungen > Indikatoreinschränkungen

Standardmäßig werden Einschränkungen in „ID-zu-Daten“-Zuordnungen dargestellt. Lineare Einschränkungen werden jedoch in einem effizienteren "Struct-of-Arrays"-Format dargestellt.

Felder
name

string
variables

VariablesProto
objective

ObjectiveProto

Das primäre Ziel des Modells.
auxiliary_objectives

map<int64, ObjectiveProto>

Zusätzliche Ziele zur Verwendung in Modellen mit mehreren Zielen.

Zuordnungsschlüssel-IDs müssen in [0, max(int64)] angegeben werden. Jede Priorität und jeder nicht leere Name müssen eindeutig und auch vom primären objective unterscheidbar sein.
linear_constraints

LinearConstraintsProto
linear_constraint_matrix

SparseDoubleMatrixProto

Die variablen Koeffizienten für die linearen Einschränkungen.

Wenn eine Variable, die an dieser Einschränkung beteiligt ist, gelöscht wird, wird sie so behandelt, als wäre sie auf null gesetzt.

Anforderungen: * linear_constraint_matrix.row_ids sind Elemente von linear_constraints.ids. * linear_constraint_matrix.column_ids sind Elemente der Variablen.ids. * Nicht angegebene Matrixeinträge sind null. * linear_constraint_matrix.values müssen alle endlich sein.
quadratic_constraints

map<int64, QuadraticConstraintProto>

Quadratische Einschränkungen im Modell.
second_order_cone_constraints

map<int64, SecondOrderConeConstraintProto>

Kegeleinschränkungen zweier Ordnung im Modell.
sos1_constraints

map<int64, SosConstraintProto>

SOS1-Einschränkungen im Modell, die einschränken, dass höchstens eine expression ungleich null sein darf. Die optionalen weights-Einträge sind Implementierungsdetails, die vom Solver verwendet werden, um (hoffentlich) schneller zu konvergieren. Im Einzelnen können Rechner diese Gewichtungen verwenden (oder auch nicht), um Verzweigungsentscheidungen auszuwählen, die „ausgeglichene“ untergeordnete Knoten erzeugen.
sos2_constraints

map<int64, SosConstraintProto>

SOS2-Einschränkungen im Modell, die einschränken, dass höchstens zwei Einträge von expression ungleich null sein können und in ihrer Reihenfolge nebeneinander sein müssen. Wenn keine weights angegeben sind, ist diese Reihenfolge die lineare Reihenfolge in der expressions-Liste. Wenn weights angegeben ist, wird die Reihenfolge in aufsteigender Reihenfolge in Bezug auf diese Werte betrachtet.
indicator_constraints

map<int64, IndicatorConstraintProto>

Einschränkungen für Indikatoren im Modell, die dies erzwingen, wenn eine binäre „Indikatorvariable“ auf eins festgelegt ist, muss eine „implizierte Einschränkung“ gelten.

ModelSolveParametersProto

Felder
variable_values_filter

SparseVectorFilterProto

Filter, der auf alle zurückgegebenen, dünnbesetzten Container angewendet wird, die durch Variablen in PrimalSolutionProto und PrimalRayProto (PrimalSolutionProto.variable_values, PrimalRayProto.variable_values) verschlüsselt sind.

Anforderungen: * Filter_ids sind Elemente der Variablen „VariablesProto.ids“.
dual_values_filter

SparseVectorFilterProto

Filter, der auf alle zurückgegebenen dünnbesetzten Container mit linearen Einschränkungen in DualSolutionProto und DualRay angewendet wird (DualSolutionProto.dual_values, DualRay.dual_values).

Anforderungen: * „Filtered_ids“ sind Elemente von „LinearConstraints.ids“.
reduced_costs_filter

SparseVectorFilterProto

Filter, der auf alle zurückgegebenen dünnbesetzten Container angewendet wird, die durch Variablen in DualSolutionProto und DualRay (DualSolutionProto.Reduced_costs, DualRay.Reduced_costs) verschlüsselt sind.

Anforderungen: * Filter_ids sind Elemente der Variablen „VariablesProto.ids“.
initial_basis

BasisProto

Optionale Ausgangsbasis für einfache LP-Löser mit Warmstartfunktion. Wenn festgelegt, muss sie laut ValidateBasis in validators/solution_validator.h für die aktuelle ModelSummary gültig sein.
solution_hints[]

SolutionHintProto

Optionale Lösungshinweise. Wenn der zugrunde liegende Solver nur einen einzelnen Hinweis akzeptiert, wird der erste Hinweis verwendet.
branching_priorities

SparseInt32VectorProto

Optionale Verzweigungsprioritäten. Variablen mit höheren Werten werden zuerst verzweigt. Variablen, für die keine Prioritäten festgelegt sind, erhalten die Standardpriorität des Solver (normalerweise null).

Anforderungen: * branching_priorities.values muss endlich sein. * branching_priorities.ids müssen Elemente von VariablesProto.ids sein.

ObjectiveBoundsProto

Beschränkt auf den optimalen Zielwert.

Felder
primal_bound

double

Der Löser gibt an, dass der optimale Wert gleich oder besser (kleinerer für die Minimierung und größer für die Maximierung) als „prima_bound“ bis zur primären Machbarkeitstoleranz des Lösers ist (siehe Warnung unten): * prial_bound ist trivial (+inf für Minimierung und -inf-Maximierung), wenn der Solver nicht behauptet, eine solche Grenze zu haben. * „prial_bound“ kann näher am optimalen Wert liegen als das Ziel der besten prinzipierbaren Lösung. Insbesondere ist „prial_bound“ möglicherweise nicht trivial, auch wenn keine urprägsamen Lösungen zurückgegeben werden. Warnung: Die genaue Behauptung ist, dass es eine Grundlösung gibt, bei der Folgendes zutrifft: * ist numerisch, d.h. bis zur Toleranz des Rechners durchführbar, und * einen objektiven Wert hat: primal_bound. Diese numerisch durchsetzbare Lösung ist möglicherweise geringfügig undurchführbar, in diesem Fall könnte primal_bound besser als der optimale Wert sein. Die Übertragung einer ursprünglichen Machbarkeitstoleranz auf eine Toleranz für primal_bound ist nicht trivial, insbesondere wenn die Machbarkeitstoleranz relativ groß ist (z.B. bei Lösung mit PDLP).
dual_bound

double

Der Rechner gibt an, dass der optimale Wert gleich oder schlechter (größer für Minimierung und kleiner für Maximierung) als „dual_bound“ bis zur doppelten Machbarkeitstoleranz des Rechners ist (siehe Warnung unten): * Dual_bound ist trivial (-inf für die Minimierung und +inf-Maximierung), wenn der Rechner nicht behauptet, eine solche Grenze zu haben. Ähnlich wie bei primal_bound kann dies bei einigen Lösern vorkommen, selbst wenn die Rückgabe optimal ist. MIP-Rechner melden in der Regel Grenzen, auch wenn diese ungenau sind. * Für kontinuierliche Probleme kann „Dual_bound“ näher am optimalen Wert liegen als das Ziel der besten doppelt durchführbaren Lösung. Bei MIP ist einer der ersten nicht trivialen Werte für Dual_bound häufig der optimale Wert für die LP-Lockerung des MIP. * Dual_bound sollte besser sein (kleiner für die Minimierung und größer für die Maximierung) als primal_bound bis zu den Toleranzen des Solver (siehe Warnung unten). Warnung: * Für kontinuierliche Probleme ist die exakte Behauptung, dass es eine zweifache Lösung gibt, die: * numerisch durchführbar (d.h. bis zur Toleranz des Rechners durch Rechner durchsetzbar) und * einen objektiven Wert „Dual_bound“ hat. Diese numerisch durchsetzbare Lösung ist möglicherweise etwas nicht machbar, wobei „dual_bound“ wesentlich schlechter als der optimale Wert und „prial_bound“ sein könnte. Ähnlich wie im ursprünglichen Fall ist es nicht einfach, eine doppelte Machbarkeitstoleranz auf eine Toleranz für „Dual_bound“ zu übertragen, insbesondere wenn die Machbarkeitstoleranz relativ groß ist. Einige Rechner bieten jedoch eine korrigierte Version von Dual_bound, die numerisch sicherer sein kann. Auf diese korrigierte Version kann über die spezifische Ausgabe des Solver zugegriffen werden (z.B. für PDLP, pdlp_output.convergence_information.Corrected_dual_objective). * Bei MIP-Lösungen wird „Dual_bound“ unter Umständen zu einer Dual-Lösung für eine kontinuierliche Lockerung (z. B. LP-Lockerung) in Verbindung gebracht. Es ist jedoch oft eine komplexe Folge der Ausführung des Solver und ist in der Regel ungenauer als die von LP-Resolvern gemeldeten Grenzen.

ObjectiveProto

Felder
maximize

bool

„false“ bedeutet „minimieren“, „wahr“ bedeutet „maximieren“
offset

double

Muss endlich sein und nicht NaN sein.
linear_coefficients

SparseDoubleVectorProto

ObjectiveProto-Begriffe, die in den Entscheidungsvariablen linear sind.

Anforderungen: * linear_coefficiencys.ids sind Elemente von „VariablesProto.ids“. * Nicht angegebene VariablesProto entspricht null. * linear_coeffizients.values muss alle endlich sein. * linear_coeffizients.values kann null sein, aber das verschwendet einfach Platz.
quadratic_coefficients

SparseDoubleMatrixProto

Objektive Begriffe, die in den Entscheidungsvariablen quadratisch sind.

Anforderungen, zusätzlich zu denen für SparseDoubleMatrixProto-Nachrichten: * Jedes Element von quadratic_coeffizients.row_ids und jedes Element von quadratic_coeffizients.column_ids muss ein Element von VariablesProto.ids sein. * Die Matrix muss ein oberes Dreieck sein: Für jedes i gilt „quadratic_coeffizients.row_ids[i] <= quadratic_coeffizients.column_ids[i].

Hinweis: * Nicht explizit gespeicherte Begriffe haben einen Koeffizienten von 0. * Die Elemente von „quadratic_coeffizients.coeffizients“ können null sein, doch dadurch wird Platz verschwendet.
name

string

Für übergeordnete Nachrichten gelten möglicherweise Anforderungen an die Eindeutigkeit dieses Feldes. Beispiele: „ModelProto.objectives“ und „AuxiliaryObjectivesUpdatesProto.new_objectives“.
priority

int64

Bei Problemen mit mehreren Zielen die Priorität dieses Ziels im Vergleich zu den anderen (niedrigere ist wichtiger). Dieser Wert darf nicht negativ sein. Außerdem muss jede objektive Priorität im Modell zum Zeitpunkt der Lösung unterschiedlich sein. Diese Bedingung wird nicht auf Proto-Ebene validiert. Daher können Modelle vorübergehend Ziele mit derselben Priorität haben.

PrimalRayProto

Eine Richtung der unbegrenzten Verbesserung eines Optimierungsproblems; entsprechend ein Zertifikat der Undurchführbarkeit für den Dual des Optimierungsproblems.

Stellen Sie sich z. B. ein einfaches lineares Programm vor: min c * x s.t. A * x >= b x >= 0 Ein Primastrahl ist ein x, das folgende Anforderungen erfüllt: c * x < 0 A * x >= 0 x >= 0. Beachten Sie, dass bei einer praktikablen Lösung ein positives Vielfaches der Grundlösung ist. Ein Primastrahl beweist auch, dass das doppelte Optimierungsproblem nicht umsetzbar ist.

In der folgenden Nachricht PrimalRay ist „variable_values“ der Wert x.

Felder
variable_values

SparseDoubleVectorProto

Anforderungen: * variable_values.ids sind Elemente von „VariablesProto.ids“. * variable_values.values müssen alle endlich sein.

PrimalSolutionProto

Eine Lösung für ein Optimierungsproblem.

Betrachten wir beispielsweise ein einfaches lineares Programm: min c * x s.t. A * x >= b x >= 0. Eine Grundlösung besteht darin, x Werte zuzuweisen. Dies ist möglich, wenn sie den oben genannten Werten A * x >= b und x >= 0 erfüllt. In der Mitteilung PrimalSolutionProto unten ist „variable_values“ der Wert „x“ und „object_value“ durch „c * x“.

Felder
variable_values

SparseDoubleVectorProto

Anforderungen: * variable_values.ids sind Elemente von „VariablesProto.ids“. * variable_values.values müssen alle endlich sein.
objective_value

double

Zielwert, wie vom zugrunde liegenden Solver berechnet. Darf nicht unendlich oder NaN sein.
auxiliary_objective_values

map<int64, double>

Zusätzliche Zielwerte, die vom zugrunde liegenden Solver berechnet werden. Schlüssel müssen gültige IDs des Hilfsziels sein. Werte dürfen nicht unendlich oder NaN sein.
feasibility_status

SolutionStatusProto

Machbarkeitsstatus der Lösung entsprechend dem zugrunde liegenden Rechner.

ProblemStatusProto

Machbarkeitsstatus des ursprünglichen Problems und seines Dual (oder Dual einer kontinuierlichen Entspannung) wie vom Löser angegeben. Der Solver muss kein Zertifikat für die Behauptung zurückgeben (z.B. kann er die grundlegende Machbarkeit behaupten, ohne eine grundlegende durchsetzbare Lösung zurückzugeben). Dieser kombinierte Status liefert eine umfassende Beschreibung der Behauptungen eines Rechners bezüglich der Machbarkeit und Begrenzung des gelösten Problems. Beispiel:

  • Ein Machbarkeitsstatus für Primär- und Duale Probleme zeigt an, dass das Primärbild realisierbar und begrenzt ist und wahrscheinlich eine optimale Lösung hat (garantiert für Probleme ohne nicht lineare Einschränkungen).
  • ein Primäreffekt und ein Status doppelt undurchführbar bedeutet, dass das Grundproblem unbegrenzt ist (d.h. es gibt beliebig gute Lösungen).

Beachten Sie, dass ein zweifach undurchführbarer Status an sich (d.h. ein unbestimmter Grundstatus) nicht impliziert, dass das Grundproblem unbegrenzt ist, da beide Probleme undurchführbar sein könnten. Auch wenn ein primärer und zweifach durchführbarer Status die Existenz einer optimalen Lösung andeuten kann, garantiert er nicht, dass der Solver diese optimale Lösung tatsächlich gefunden hat.

Felder
primal_status

FeasibilityStatusProto

Status für das Grundproblem.
dual_status

FeasibilityStatusProto

Status für das duale Problem (oder das doppelte Problem einer kontinuierlichen Lockerung).
primal_or_dual_infeasible

bool

Wenn dieser Wert „wahr“ ist, behauptet der Rechner, dass das grundlegende oder doppelte Problem nicht durchführbar ist, weiß aber nicht, welches (oder ob beides nicht umsetzbar ist). Kann nur wahr sein, wenn primal_problem_status = dual_problem_status = kUnbestimmt. Diese zusätzlichen Informationen werden häufig benötigt, wenn die Vorverarbeitung feststellt, dass es keine optimale Lösung für das Problem gibt (aber nicht feststellen kann, ob es an Undurchführbarkeit, Unbegrenztheit oder beidem liegt).

QuadraticConstraintProto

Eine einzelne quadratische Einschränkung der Form: lb <= sum{linear_terms} + sum{quadratic_terms} <= ub.

Wenn eine Variable, die an dieser Einschränkung beteiligt ist, gelöscht wird, wird sie so behandelt, als wäre sie auf null gesetzt.

Felder
linear_terms

SparseDoubleVectorProto

Begriffe, die in den Entscheidungsvariablen linear sind.

Zusätzlich zu den Anforderungen für SparseDoubleVectorProto-Nachrichten gilt Folgendes: * linear_terms.ids sind Elemente von VariablesProto.ids. * linear_terms.values müssen alle endlich und nicht-NaN sein.

Hinweis: * Ausgelassene Variablen-IDs haben einen Koeffizienten von null. * linear_terms.values kann null sein, aber das verschwendet einfach Platz.
quadratic_terms

SparseDoubleMatrixProto

Begriffe, die in den Entscheidungsvariablen quadratisch sind.

Zusätzlich zu den Anforderungen für SparseDoubleMatrixProto-Nachrichten verlangen wir Folgendes: * Jedes Element von „quadratic_terms.row_ids“ und jedes Element von „quadratic_terms.column_ids“ muss ein Element von „VariablesProto.ids“ sein. * Die Matrix muss das obere Dreieck sein: Für jedes i gilt „quadratic_terms.row_ids[i] <= quadratic_terms.column_ids[i].

Hinweis: * Nicht explizit gespeicherte Begriffe haben einen Koeffizienten von 0. * Die Elemente von „quadratic_terms.coeffizients“ können null sein, doch dadurch wird Platz verschwendet.
lower_bound

double

Muss einen Wert in [-inf, inf) haben und kleiner oder gleich upper_bound sein.
upper_bound

double

Muss einen Wert in (-inf, inf] haben und größer oder gleich lower_bound sein.
name

string

Für übergeordnete Nachrichten gelten möglicherweise Anforderungen an die Eindeutigkeit dieses Feldes. Siehe z. B. „ModelProto.quadratic_constraints“ und „QuadraticConstraintUpdatesProto.new_constraints“.

SecondOrderConeConstraintProto

Eine einzelne Kegeleinschränkung zweiter Ordnung im folgenden Format:

||arguments_to_norm||_2 <= upper_bound,

Dabei sind upper_bound und jedes Element von arguments_to_norm lineare Ausdrücke.

Wenn eine Variable, die an dieser Einschränkung beteiligt ist, gelöscht wird, wird sie so behandelt, als wäre sie auf null gesetzt.

Felder
upper_bound

LinearExpressionProto
arguments_to_norm[]

LinearExpressionProto
name

string

Für übergeordnete Nachrichten gelten möglicherweise Anforderungen an die Eindeutigkeit dieses Feldes, z.B. „ModelProto.second_order_cone_constraints“ und „SecondOrderConeConstraintUpdatesProto.new_constraints“.

SolutionHintProto

Eine empfohlene Ausgangslösung für den Matherechner.

MIP-Rechner benötigen in der Regel nur Urinformationen (variable_values), während LIP-Rechner sowohl primäre als auch duale Informationen (dual_values) benötigen.

Viele MIP-Lösungen können mit (1) Teillösungen, bei denen nicht alle Variablen angegeben werden, oder (2) nicht machbaren Lösungen verwendet werden. In solchen Fällen lösen die Solver ein Sub-MIP normalerweise aus, um den Hinweis zu vervollständigen oder zu korrigieren.

Wie der Hinweis vom Solver verwendet wird, hängt, wenn überhaupt, stark vom Matherechner, vom Problemtyp und vom verwendeten Algorithmus ab. Die zuverlässigste Methode, um sicherzustellen, dass ein Hinweis einen Effekt hat, besteht darin, die zugrunde liegenden Solver-Protokolle mit und ohne Hinweis zu lesen.

Simplex-basierte LP-Resolver bevorzugen in der Regel eine Ausgangsbasis gegenüber einem Lösungshinweis. Andernfalls muss ein Crossover ausgeführt werden, um den Hinweis in eine einfach machbare Lösung umzuwandeln.

Felder
variable_values

SparseDoubleVectorProto

Eine möglicherweise teilweise Zuweisung von Werten zu den Primvariablen des Problems. Die Solver-unabhängigen Anforderungen für diese Untermitteilung lauten: * variable_values.ids sind Elemente von „VariablesProto.ids“. * variable_values.values müssen alle endlich sein.
dual_values

SparseDoubleVectorProto

Eine (möglicherweise teilweise) Zuweisung von Werten zu den linearen Einschränkungen des Problems.

Anforderungen: * Dual_values.ids sind Elemente der LinearConstraintsProto.ids. * Dual_values.values müssen alle endlich sein.

SolutionProto

Was in einer Lösung enthalten ist, hängt von der Art des Problems und des Lösers ab. Die aktuellen gemeinsamen Muster sind 1. MIP-Rechner geben nur eine Grundlösung zurück. 2. Simplex-LP-Resolver geben oft eine Basis und die mit dieser Basis verbundenen ursprünglichen und Dual-Lösungen zurück. 3. Andere Continuous-Llöser geben oft eine Primär- und Dual-Lösung zurück, die in einer Solver-abhängigen Form verbunden sind.

Anforderungen: * Es muss mindestens ein Feld festgelegt werden. Eine Lösung darf nicht leer sein.

Felder
primal_solution

PrimalSolutionProto
dual_solution

DualSolutionProto
basis

BasisProto

SolutionStatusProto

Machbarkeit einer Grund- oder Doppellösung, wie vom Rechner angegeben.

Enums
SOLUTION_STATUS_UNSPECIFIED Guard-Wert, der keinen Status darstellt.
SOLUTION_STATUS_UNDETERMINED Der Rechner beansprucht keinen Machbarkeitsstatus.
SOLUTION_STATUS_FEASIBLE Der Löser behauptet, die Lösung sei machbar.
SOLUTION_STATUS_INFEASIBLE Der Löser behauptet, die Lösung sei nicht umsetzbar.

SolveParametersProto

Parameter zur Steuerung einer Lösung.

Enthält beide Parameter, die alle Rechner gemeinsam haben (z.B. „time_limit“), und Parameter für einen bestimmten Solver, z.B. gscip. Wenn ein Wert sowohl im allgemeinen als auch im Solver-spezifischen Feld festgelegt ist, wird die Solver-spezifische Einstellung verwendet.

Die gängigen Parameter, die optional und nicht festgelegt sind, oder eine Aufzählung mit nicht angegebenem Wert weisen darauf hin, dass der Solver-Standardwert verwendet wird.

Solver-spezifische Parameter für andere als den verwendeten Solver-Parameter werden ignoriert.

Parameter, die vom Modell abhängen (z.B. für jede Variable wird eine Verzweigungspriorität festgelegt), werden in ModelSolveParametersProto übergeben.

Felder
time_limit

Duration

Maximale Zeit, die ein Matherechner für das Problem aufwenden sollte (oder unendlich, wenn er nicht festgelegt ist).

Dieser Wert ist kein festes Limit. Die Lösungszeit kann diesen Wert leicht überschreiten. Dieser Parameter wird immer an den zugrunde liegenden Solver übergeben. Die Standardeinstellung des Solver wird nicht verwendet.
enable_output

bool

Aktiviert das Drucken der Tracer-Implementierungs-Traces. Wo sich diese Traces befinden, hängt vom Solver ab. Bei SCIP und Gurobi sind dies die Standard-Ausgabestreams. Für Glop und CP-SAT wird PROTOKOLLIERT(INFO).

Wenn der Solver den Nachrichten-Callback unterstützt und der Nutzer einen Callback dafür registriert, wird dieser Parameterwert ignoriert und es werden keine Traces gedruckt.
lp_algorithm

LPAlgorithmProto

Der Algorithmus zur Lösung eines linearen Programms. Wenn LP_ALGORITHM_UNSPECIFIED lautet, wird der Standardalgorithmus des Solver verwendet.

Dieser Wert kann bei Problemen verwendet werden, die keine linearen Programme sind, bei denen die lineare Programmierung aber eine Unterroutine ist. MIP-Resolver verwenden diese beispielsweise in der Regel nur für die Stamm-LP-Lösung. Andernfalls wird Dual Simplex verwendet.
presolve

EmphasisProto

Versuchen Sie, das Problem zu vereinfachen, bevor Sie den Hauptalgorithmus starten, oder versuchen Sie, die Standardaufwandsstufe des Lösers zu verwenden, wenn {9}_UNSPECIFIED verwendet wird.
cuts

EmphasisProto

Versuche, eine stärkere LP-Entspannung (nur MIP) zu erreichen, oder die Standardanstrengung des Lösers, falls heizt_UNSPECIFIED.

HINWEIS: Das Deaktivieren von Schnitten kann verhindern, dass Callbacks Schnitte unter MIP_NODE hinzufügen. Dieses Verhalten ist spezifisch.
heuristics

EmphasisProto

Der Aufwand zur Suche nach durchführbaren Lösungen, die über die Lösungen hinausgehen, die bei der vollständigen Suche (nur MIP) aufgetreten sind, oder des Standardaufwandslevels des Solver, falls Θ_UNSPECIFIED angegeben ist.
scaling

EmphasisProto

Aufwand zur Neuskalierung des Problems, um die numerische Stabilität zu verbessern, oder die Standardaufwand des Solver, falls Θ_UNSPECIFIED.
iteration_limit

int64

Begrenzung der Iterationen des zugrunde liegenden Algorithmus (z.B. unidirektionale Pivots). Das spezifische Verhalten hängt vom verwendeten Solver und Algorithmus ab, kann jedoch häufig ein deterministisches Lösungslimit vorgeben (weitere Konfigurationsschritte sind erforderlich, z.B. ein Thread).

In der Regel von LP-, QP- und MIP-Resolvern unterstützt, aber für MIP-Resolver siehe auch node_limit.
node_limit

int64

Begrenzung der Anzahl der bei der Aufzählungssuche gelösten Teilprobleme (z.B. Zweig und Bindung). Bei vielen Rechnern kann dies verwendet werden, um die Berechnung deterministisch einzuschränken (weitere Konfigurationsschritte sind möglicherweise erforderlich, z.B. ein Thread).

In der Regel für MIP-Rechner, siehe auch iteration_limit.
cutoff_limit

double

Der Solver stoppt vorzeitig, wenn er beweisen kann, dass es keine Grundlösungen gibt, die mindestens so gut wie den Grenzwert sind.

Bei einem vorzeitigen Beenden gibt der Solver den Beendigungsgrund NO_SOLUTION_FOUND und mit dem Limit CUTOFF zurück und muss keine zusätzlichen Lösungsinformationen angeben. Hat keine Auswirkungen auf den Rückgabewert, wenn es keinen vorzeitigen Stopp gibt.

Die Verwendung einer Toleranz wird empfohlen, wenn Lösungen zurückgegeben werden sollen, deren Ziel genau dem Grenzwert entspricht.

Weitere Informationen und einen Vergleich mit „best_bound_limit“ finden Sie im Nutzerhandbuch.
objective_limit

double

Der Solver bricht ab, sobald er eine mindestens so gute Lösung gefunden hat. Der Beendigungsgrund ist FEASIBLE und begrenzt ZIEL.
best_bound_limit

double

Der Solver stoppt früh, sobald sich herausstellt, dass die beste Grenze mindestens so gut ist, mit dem Kündigungsgrund FEASIBLE oder NO_SOLUTION_FOUND und begrenzt auf TARGETIVE.

Weitere Informationen und einen Vergleich mit dem Wert für „cutoff_limit“ finden Sie im Nutzerhandbuch.
solution_limit

int32

Der Solver stoppt früh, nachdem so viele machbare Lösungen gefunden wurden, mit Kündigungsgrund FEASIBLE und begrenzter LÖSUNG. Muss größer als null sein, wenn festgelegt. Sie wird häufig verwendet, um den Solver dazu zu bringen, bei der ersten praktikablen Lösung anzuhalten. Der Zielwert kann für keine der zurückgegebenen Lösungen garantiert werden.

Solver geben üblicherweise nicht mehr Lösungen als den Lösungsgrenzwert zurück, aber dies wird nicht von MathOpt erzwungen, siehe auch b/214041169.

Derzeit unterstützt für Gurobi und SCIP sowie für CP-SAT nur mit dem Wert 1.
threads

int32

Wenn festgelegt, muss der Wert ≥ 1 sein.
random_seed

int32

Seed für den Pseudozufallszahlengenerator im zugrunde liegenden Solver. Beachten Sie, dass alle Rechner Pseudozufallszahlen verwenden, um Dinge wie Störungen im LP-Algorithmus, für Tie-Break-up-Regeln und für heuristische Korrekturen auszuwählen. Wenn du diesen Wert änderst, kann sich das spürbar auf das Verhalten des Solver auswirken.

Obwohl alle Solver ein Basiskonzept haben, beachten Sie, dass gültige Werte vom tatsächlichen Rechner abhängig sind. - Gurobi: [0:GRB_MAXINT] (ab Gurobi 9.0 ist 2x10^9). – GSCIP: [0:2147483647] (MAX_INT, kint32max oder 2^31-1). - GLOP: [0:2147483647] (wie oben) Der Solver erhält in allen Fällen einen Wert gleich: MAX(0; MIN(MAX_VALID_VALUE_FOR_SOLVER; random_seed)).
absolute_gap_tolerance

double

Eine absolute Optialitätstoleranz (hauptsächlich) für MIP-Rechner.

Der absolute GAP ist der absolute Wert der Differenz zwischen: * dem Zielwert der am besten geeigneten Lösung gefunden, * der durch die Suche erzeugten doppelten Grenze. Der Löser kann stoppen, sobald der absolute GAP-Wert höchstens absolute_gap_toleranz erreicht ist (falls festgelegt) und TERMINATION_REASON_OPTIMAL zurückgeben.

Muss >= 0 sein, wenn festgelegt.

Siehe auch relative_gap_Toleranz.
relative_gap_tolerance

double

Eine relative Optimitätstoleranz (hauptsächlich) für MIP-Rechner.

Der relative GAP ist eine normalisierte Version des absoluten GAP (definiert auf absolute_gap_Toleranz), wobei die Normalisierung lösungsabhängig ist, z.B. der absolute GAP geteilt durch den objektiven Wert der am besten geeigneten Lösung.

Der Solver kann stoppen, sobald der relative GAP höchstens relative_gap_Toleranz (wenn festgelegt) liegt, und TERMINATION_REASON_OPTIMAL zurückgeben.

Muss >= 0 sein, wenn festgelegt.

Siehe auch absolute_gap_Toleranz.
solution_pool_size

int32

Du kannst während der Suche bis zu solution_pool_size Lösungen beibehalten. Der Lösungspool hat in der Regel zwei Funktionen: (1) Bei Lösern, die mehr als eine Lösung zurückgeben können, wird dadurch eingeschränkt, wie viele Lösungen zurückgegeben werden. (2) Einige Rechner führen möglicherweise Heuristiken mit Lösungen aus dem Lösungspool aus. Eine Änderung dieses Werts kann sich also auf den Pfad des Algorithmus auswirken. Wenn der Solver den Lösungspool z.B. mit der n besten Lösung füllen soll, ist eine weitere, löserspezifische Konfiguration erforderlich.

SolveResultProto

Der Vertrag, wann primäre/doppelte Lösungen/Strahlen komplex sind, finden Sie unter „termination_reasons.md“ für eine vollständige Beschreibung.

Bis ein genauer Vertrag abgeschlossen ist, solltest du am besten einfach prüfen, ob eine Lösung bzw. ein Dienst vorhanden ist, anstatt dich auf den Kündigungsgrund zu verlassen.

Felder
termination

TerminationProto

Der Grund, warum der Solver gestoppt wurde.
solutions[]

SolutionProto

Der allgemeine Vertrag für die Reihenfolge der Lösungen, die zukünftige Löser implementieren sollten, besagt: 1. Die Lösungen mit einer primären realisierbaren Lösung, sortiert nach dem besten ursprünglichen Ziel. 2. Die Lösungen mit einer doppelt durchführbaren Lösung, sortiert nach dem besten Dual Objective (unbekanntes Dual Objective ist am schlechtesten) 3. Alle verbleibenden Lösungen können in beliebiger Reihenfolge zurückgegeben werden.
primal_rays[]

PrimalRayProto

Richtung unbegrenzter grundlegender Verbesserung bzw. gleichwertige Zertifikate für die doppelte Undurchführbarkeit. In der Regel für TerminationReasonProtos UNBOUNDED und DUAL_INFEASIBLE
dual_rays[]

DualRayProto

Richtungen für unbegrenzte doppelte Verbesserung oder gleichwertige Zertifikate für die grundlegende Undurchführbarkeit. Wird in der Regel für TerminationReasonProto NICHT FEASIBLE bereitgestellt.
solve_stats

SolveStatsProto

Statistiken zum Lösungsprozess, z.B. Laufzeit, Iterationen.

SolveStatsProto

Felder
solve_time

Duration

Verstrichene Wanduhrzeit, gemessen von math_opt, ungefähr der Zeit in Solver::Solve(). Hinweis: Dies beinhaltet nicht die Arbeit, die beim Erstellen des Modells durchgeführt wurde.
problem_status

ProblemStatusProto

Machbarkeitsstatus für grundlegende und doppelte Probleme.
simplex_iterations

int64
barrier_iterations

int64
first_order_iterations

int64
node_count

int64

SolverTypeProto

Die von MathOpt unterstützten Rechner.

Enums
SOLVER_TYPE_UNSPECIFIED
SOLVER_TYPE_GSCIP

Solving Constraint Integer Programs (SCIP)-Resolver (Drittanbieter).

Unterstützt LP-, MIP- und nichtkonvexe quadratische Probleme mit Ganzzahlen. Es werden jedoch keine doppelten Daten für LPs zurückgegeben. GLOP für LPs bevorzugen
SOLVER_TYPE_GUROBI

Gurobi Solver (Drittanbieter).

Unterstützt LP-, MIP- und nichtkonvexe quadratische Probleme mit Ganzzahlen. In der Regel die schnellste Option, hat jedoch eine spezielle Lizenzierung.
SOLVER_TYPE_GLOP

Der Glop-Rechner von Google.

Unterstützt LP mit Primär- und Dual-Simplex-Methoden.
SOLVER_TYPE_CP_SAT

Der CP-SAT-Rechner von Google.

Unterstützt Probleme, bei denen alle Variablen ganzzahlig und begrenzt sind (oder impliziert werden, dass sie nach der Vorlösung liegen). Experimentelle Unterstützung für die Reskalierung und Diskretisierung von Problemen mit kontinuierlichen Variablen.
SOLVER_TYPE_PDLP

Der PDLP-Resolver von Google.

Unterstützt LP- und konvexe diagonale quadratische Ziele. Es werden First-Order-Methoden anstelle von Simplex-Methoden verwendet. Kann sehr große Probleme lösen.
SOLVER_TYPE_GLPK

GNU Linear Programming Kit (GLPK) (Drittanbieter).

Unterstützt MIP und LP.

Thread-Sicherheit: GLPK verwendet den lokalen Thread-Speicher für Arbeitsspeicherzuweisungen. Infolgedessen müssen Solver-Instanzen im selben Thread gelöscht werden, in dem sie erstellt werden, da sonst GLPK abstürzt. Es scheint in Ordnung zu sein, Solver::Solve() aus einem anderen Thread als dem aufzurufen, mit dem der Solver erstellt wurde. Dieser Thread ist jedoch nicht von der GLPK dokumentiert und sollte vermieden werden.

Beim Lösen einer LP mit dem Presolver werden nur dann eine Lösung (und die ungebundenen Strahlen) zurückgegeben, wenn eine optimale Lösung gefunden wurde. Andernfalls wird nichts zurückgegeben. Weitere Informationen finden Sie unter glpk-5.0/doc/glpk.pdf Seite Nr. 40 unter glpk-5.0.tar.gz.
SOLVER_TYPE_OSQP

Der OSQP-Rechner (Operator Splitting Quadratic Program, Drittanbieter)

Unterstützt kontinuierliche Probleme mit linearen Einschränkungen und linearen oder konvexen quadratischen Zielen. Verwendet eine Methode der ersten Reihenfolge.
SOLVER_TYPE_ECOS

Der Integrierte Conic Solver (ECOS) (Drittanbieter).

Unterstützt LP- und SOCP-Probleme. Verwendet Innenpunktmethoden (Barriere).
SOLVER_TYPE_SCS

The Splitting Conic Solver (SCS) (Drittanbieter).

Unterstützt LP- und SOCP-Probleme. Verwendet eine Methode der ersten Reihenfolge.
SOLVER_TYPE_HIGHS

The HiGHS Solver (Drittanbieter).

Unterstützt LP- und MIP-Probleme (konvexe QPs sind nicht implementiert).
SOLVER_TYPE_SANTORINI

Referenzimplementierung eines MIP-Rechners in MathOpt

Langsam/für die Produktion nicht empfohlen. Kein LP-Resolver (keine doppelten Informationen zurückgegeben).

SosConstraintProto

Daten zur Darstellung einer einzelnen SOS1- oder SOS2-Einschränkung.

Wenn eine Variable, die an dieser Einschränkung beteiligt ist, gelöscht wird, wird sie so behandelt, als wäre sie auf null gesetzt.

Felder
expressions[]

LinearExpressionProto

Die Ausdrücke, auf die die SOS-Einschränkung angewendet werden soll: * SOS1: Höchstens ein Element verwendet einen Wert ungleich null. * SOS2: Maximal zwei Elemente nehmen Werte ungleich null an und müssen in der wiederholten Reihenfolge nebeneinander liegen.
weights[]

double

Entweder leer oder von gleicher Länge für Ausdrücke. Wenn leer, sind die Standardgewichtungen 1, 2, .... Falls vorhanden, müssen die Einträge eindeutig sein.
name

string

Für übergeordnete Nachrichten können Anforderungen an Eindeutigkeiten in diesem Feld gelten. Siehe z. B. „ModelProto.sos1_constraints“ und „SosConstraintUpdatesProto.new_constraints“.

SparseBasisStatusVector

Eine dünnbesetzte Darstellung eines Vektors von Basisstatuswerten.

Felder
ids[]

int64

Muss (in aufsteigender Reihenfolge) sortiert werden, wobei sich alle Elemente unterscheiden müssen.
values[]

BasisStatusProto

Muss dieselbe Länge wie IDs haben.

SparseDoubleMatrixProto

Eine dünnbesetzte Darstellung einer Matrix von Doubles.

Die Matrix wird als Dreifache von Zeilen-ID, Spalten-ID und Koeffizient gespeichert. Diese drei Vektoren müssen gleich lang sein. Für alle i sollte das Tupel (row_ids[i], column_ids[i]) unterschiedlich sein. Die Einträge müssen in der Hauptreihenfolge der Zeilen angegeben werden.

Felder
row_ids[]

int64
column_ids[]

int64
coefficients[]

double

Darf nicht NaN enthalten.

SparseDoubleVectorProto

Eine dünnbesetzte Darstellung eines Vektors von Doubles.

Felder
ids[]

int64

Muss (in aufsteigender Reihenfolge) sortiert werden, wobei sich alle Elemente unterscheiden müssen.
values[]

double

Muss dieselbe Länge wie IDs haben. Darf nicht NaN enthalten.

SparseInt32VectorProto

Eine dünnbesetzte Darstellung eines Inten-Vektors.

Felder
ids[]

int64

Sollte in aufsteigender Reihenfolge sortiert werden, wobei sich alle Elemente unterscheiden sollten.
values[]

int32

Muss dieselbe Länge wie IDs haben.

SparseVectorFilterProto

Mit dieser Meldung können bestimmte Teile eines SparseXxxxVector abfragen/festgelegt werden. Standardmäßig wird nichts herausgefiltert. Häufig werden nur Teile von Lösungen abgefragt, d. h. nur Werte ungleich null und/oder ein manuell ausgewählter Satz von Variablenwerten.

Felder
skip_zero_values

bool

Für SparseBoolVectorProto ist „zero“ false.
filter_by_ids

bool

Bei „true“ werden nur die Werte zurückgegeben, die den in „Filtered_ids“ aufgeführten IDs entsprechen.
filtered_ids[]

int64

Die Liste der IDs, die verwendet werden sollen, wenn filter_by_ids wahr ist. Muss leer sein, wenn filter_by_ids „false“ ist. HINWEIS: Wenn dieses Feld leer ist und filter_by_ids wahr ist, sagen Sie, dass das Ergebnis keine Informationen enthalten soll.

TerminationProto

Alle Informationen darüber, warum ein Aufruf von Solve() beendet wurde.

Felder
reason

TerminationReasonProto

Zusätzliche Informationen in limit, wenn der Wert TERMINATION_REASON_FEASIBLE oder TERMINATION_REASON_NO_SOLUTION_FOUND ist, finden Sie unter limit.
limit

LimitProto

Ist LIMIT_UNSPECIFIED, es sei denn, der Grund ist TERMINATION_REASON_FEASIBLE oder TERMINATION_REASON_NO_SOLUTION_FOUND. Nicht alle Solver können das Limit, das zur Kündigung geführt hat, immer ermitteln. Wenn sich die Ursache nicht ermitteln lässt, wird LIMIT_UNDETERMINED verwendet.
detail

string

Weitere, normalerweise löser spezifische Informationen zur Kündigung.
problem_status

ProblemStatusProto

Machbarkeitsstatus für grundlegende und doppelte Probleme. Seit dem 18. Juli 2023 fehlt diese Nachricht möglicherweise. Wenn nicht, finden Sie „problem_status“ in SolveResultProto.solve_stats.
objective_bounds

ObjectiveBoundsProto

Beschränkt auf den optimalen Zielwert. Seit dem 18. Juli 2023 fehlt diese Nachricht möglicherweise. Wenn „Objective_bounds.primal_bound“ fehlt, finden Sie sie in „SolveResultProto.solve.stats.best_primal_bound“ und „Objective_bounds.dual_bound“ in „SolveResultProto.solve.stats.best_dual_bound“

TerminationReasonProto

Der Grund, aus dem ein Aufruf von Solve() beendet wird.

Enums
TERMINATION_REASON_UNSPECIFIED
TERMINATION_REASON_OPTIMAL Es wurde eine nachweislich optimale Lösung (bis hin zu numerischen Toleranzen) gefunden.
TERMINATION_REASON_INFEASIBLE Für das ursprüngliche Problem gibt es keine durchführbaren Lösungen.
TERMINATION_REASON_UNBOUNDED Das Grundproblem ist machbar und willkürlich gute Lösungen finden sich entlang eines Nullstrahls.
TERMINATION_REASON_INFEASIBLE_OR_UNBOUNDED Das Grundproblem ist entweder nicht umsetzbar oder unbegrenzt. Weitere Informationen zum Problemstatus finden Sie möglicherweise unter „solve_stats.problem_status“. Beachten Sie, dass der unbegrenzte Status von Gurobi hier möglicherweise abgebildet wird.
TERMINATION_REASON_IMPRECISE

Das Problem wurde anhand eines der oben genannten Kriterien (Optimal, Nicht möglich, Unbegrenzt oder InfeasibleOrUnbounded) gelöst, aber mindestens eine Toleranz wurde nicht erfüllt. Einige grundlegende bzw. doppelte Lösungen/Strahlen sind vorhanden, die jedoch entweder etwas undurchführbar sind oder (wenn das Problem fast optimal war) möglicherweise eine Lücke zwischen dem besten Lösungsziel und der besten Zielbindung.

Benutzer können immer noch Prima-/Dual-Lösungen/Strahlen und Lösungsstatistiken abfragen, sind aber für den Umgang mit numerischer Ungenauigkeit verantwortlich.
TERMINATION_REASON_FEASIBLE Der Optimierer hat einen bestimmten Grenzwert erreicht und eine prinzipiell machbare Lösung wird zurückgegeben. Eine ausführliche Beschreibung der erreichten Art von Limit finden Sie unter SolveResultProto.limit_detail.
TERMINATION_REASON_NO_SOLUTION_FOUND Das Optimierer hat einen bestimmten Grenzwert erreicht und keine urpräventive Lösung gefunden. Eine ausführliche Beschreibung der erreichten Art von Limit finden Sie unter SolveResultProto.limit_detail.
TERMINATION_REASON_NUMERICAL_ERROR Der Algorithmus wurde aufgrund eines nicht behebbaren numerischen Fehlers angehalten. Es sind keine Lösungsinformationen verfügbar.
TERMINATION_REASON_OTHER_ERROR Der Algorithmus wurde aufgrund eines Fehlers angehalten, der nicht durch einen der oben definierten Status abgedeckt ist. Es sind keine Lösungsinformationen verfügbar.

VariablesProto

Wie unten verwendet, definieren wir „#variables“ = size(VariablesProto.ids).

Felder
ids[]

int64

Darf nicht negativ und nur ansteigend sein. Der Wert „max(int64)“ kann nicht verwendet werden.
lower_bounds[]

double

Die Länge sollte der Länge von #variables entsprechen, die Werte in [-inf, inf).
upper_bounds[]

double

Die Länge sollte #Variablen entsprechen, Werte in (-inf, inf].
integers[]

bool

Die Länge sollte dem Wert „#variables“ entsprechen. Der Wert ist „falsch“ für kontinuierliche Variablen und „wahr“ für ganzzahlige Variablen.
names[]

string

Wenn nichts festgelegt ist, werden alle leeren Strings angenommen. Andernfalls sollte die Länge gleich #variables sein.

Alle nicht leeren Namen müssen eindeutig sein.