Package google.research.optimization.v1.mathopt

Indeks

BasisProto

Charakterystyka kombinatoryczna rozwiązania programu liniowego.

Metoda jednokierunkowa do rozwiązywania programów liniowych zawsze zwraca „podstawowe wykonalne rozwiązanie”, które można opisać kombinacyjnie za pomocą podstawy. Podstawa przypisuje wartość BasisStatusProto do każdej zmiennej i ograniczenia liniowego.

Np. przyjmijmy, że mamy format standardowy LP: min c * x s.t. A * x = b x >= 0, który ma więcej zmiennych niż ograniczenia i ma pełny wiersz A.

Niech n będzie liczbą zmiennych, a m – liczbą ograniczeń liniowych. Prawidłową podstawę problemu można sformułować w następujący sposób: * Wszystkie ograniczenia mają stan podstawowy ZROBIONE. * Wybierz m zmiennych, aby kolumny A były liniowo niezależne od siebie i przypisano do nich stan PODSTAWOWY. * Dla pozostałych zmiennych n–m przypisz stan AT_LOWER.

Podstawowym rozwiązaniem na tej podstawie jest wyjątkowe rozwiązanie A * x = b, w którym wszystkie zmienne o stanie AT_LOWER są ustalone na stałe na dolnych granicach (całe 0). Otrzymane rozwiązanie jest nazywane podstawowym wykonalnym rozwiązaniem, jeśli spełnia również x >= 0.

Pola
constraint_status

SparseBasisStatusVector

Stan podstawy ograniczenia.

Wymagania: * constraint_status.ids ma wartość LinearConstraints.ids.
variable_status

SparseBasisStatusVector

Zmienny stan podstawy.

Wymagania: * constraint_status.ids ma wartość ZmiennasProto.ids.
basic_dual_feasibility

SolutionStatusProto

Jest to zaawansowana funkcja używana przez MathOpt do określania wykonalności nieoptymalnych rozwiązań LP (optymalne rozwiązania zawsze mają stan SOLUTION_STATUS_FEASIBLE).

W przypadku jednostronnych stron docelowych powinien on być równy stanowi wykonalności powiązanego rozwiązania podwójnego. W przypadku dwustronnych stron docelowych może się różnić w niektórych przypadkach skrajnych (np. niepełne rozwiązania z pierwotnym jednoksiążką).

Jeśli podasz wartość początkową za pomocą parametru ModelSolveParametersProto.initial_basis, ta wartość jest ignorowana. Ma zastosowanie tylko w przypadku podstawy zwracanej przez SolutionProto.basis.

BasisStatusProto

Stan zmiennej/ograniczenia na podstawie strony docelowej.

Wartości w polu enum
BASIS_STATUS_UNSPECIFIED Wartość zabezpieczenia reprezentująca brak stanu.
BASIS_STATUS_FREE Zmienna/ograniczenie jest dowolne (nie ma nieograniczonych granic).
BASIS_STATUS_AT_LOWER_BOUND Zmienna/ograniczenie znajduje się na dolnej granicy (która musi być skończona).
BASIS_STATUS_AT_UPPER_BOUND Zmienna/ograniczenie znajduje się na górnej granicy (która musi być skończona).
BASIS_STATUS_FIXED_VALUE Zmienna/ograniczenie ma identyczną, dolną i górną granicę.
BASIS_STATUS_BASIC Zmienna/ograniczenie jest podstawowe.

DualRayProto

Kierunek nieograniczonej poprawy dwójki problemu optymalizacji, czyli równoważnego certyfikatu pierwszorzędnej niewykonalności.

Np. przyjmijmy, że pierwotna para programu liniowego z podwójnymi parami: (Primal) (Dual) min c * x max b * y s.t. A * x >= b s.t. y * A + r = c x >= 0 y, r >= 0. Podwójne promienie spełniają para (y, r): b * y > 0 y * A + r = 0 y, r >= 0 Obserwuj, że dodanie dodatniej wielokrotności (y, r) do podwójnego wykonalnego rozwiązania pozwala uzyskać podwójną wykonalność i poprawia cel (udowadniając, że podwójny jest nieograniczony). Podwójne promienie dowodzą również, że pierwotny problem jest niemożliwy.

W poniższym komunikacie DualRay y oznacza wartość podwójną, a r – ograniczenie_kosztów.

Pola
dual_values

SparseDoubleVectorProto

Wymagania: * dual_values.ids to elementy elementu LinearConstraints.id. * Wszystkie wartości podwójne.wartości muszą być skończone.
reduced_costs

SparseDoubleVectorProto

Wymagania: * red_costs.ids to elementy ZmiennasProto.ids. * *red_costs.values muszą być ograniczone.

DualSolutionProto

Rozwiązanie dwuskładnikowego problemu optymalizacyjnego.

Np. przyjmijmy, że pierwotna para programu liniowego z podwójnymi parami: (Primal) (Dual) min c * x max b * y s.t. A * x >= b s.t. y * A + r = c x >= 0 y, r >= 0. Rozwiązanie podwójne to para (y, r). Jest możliwe, jeśli spełnia ograniczenia określone powyżej (Dual).

W poniższym komunikacie y to wartości podwójne, r – ograniczony_koszt, a b * y to wartość docelowa.

Pola
dual_values

SparseDoubleVectorProto

Wymagania: * dual_values.ids to elementy elementu LinearConstraints.id. * Wszystkie wartości podwójne.wartości muszą być skończone.
reduced_costs

SparseDoubleVectorProto

Wymagania: * red_costs.ids to elementy ZmiennasProto.ids. * *red_costs.values muszą być ograniczone.
feasibility_status

SolutionStatusProto

Stan wykonalności rozwiązania zgodnie z jego rozwiązaniem.
objective_value

double

EmphasisProto

Poziom wysiłku zastosowany do zadania opcjonalnego podczas rozwiązywania problemu (patrz: SolveParametersProto, aby go użyć).

Aktywujemy je, by skonfigurować funkcję rozwiązania w ten sposób: * Jeśli rozwiązanie nie obsługuje tej funkcji, zawsze poprawna jest tylko wartość UNSPECIFIED. W przypadku każdego innego ustawienia będzie zwykle zwracany błąd nieprawidłowego argumentu (niektóre rozwiązania mogą też akceptować opcję WYŁĄCZONE). * Jeśli rozwiązanie obsługuje tę funkcję: – Gdy ma wartość UNSPECIFIED, używana jest bazowa wartość domyślna. – Jeśli tej funkcji nie można wyłączyć, opcja OFF spowoduje wyświetlenie błędu. – Jeśli ta funkcja jest domyślnie włączona, rozwiązanie domyślne jest zwykle mapowane na ŚREDNIE. - Jeśli funkcja jest obsługiwana, wartości NISKIE, ŚREDNIE, WYSOKIE i BARDZO WYSOKIE nie zwracają nigdy błędu i są dopasowywane najlepiej.

Wartości w polu enum
EMPHASIS_UNSPECIFIED
EMPHASIS_OFF
EMPHASIS_LOW
EMPHASIS_MEDIUM
EMPHASIS_HIGH
EMPHASIS_VERY_HIGH

FeasibilityStatusProto

Stan wykonalności problemu określony przez osobę wnoszącą rozwiązanie (nie musi zwracać certyfikatu dla roszczenia).

Wartości w polu enum
FEASIBILITY_STATUS_UNSPECIFIED Wartość zabezpieczenia reprezentująca brak stanu.
FEASIBILITY_STATUS_UNDETERMINED Solver nie rości sobie statusu.
FEASIBILITY_STATUS_FEASIBLE Solver twierdzi, że problem jest możliwy do wykonania.
FEASIBILITY_STATUS_INFEASIBLE Solver twierdzi, że problem jest niemożliwy do wykonania.

IndicatorConstraintProto

Dane reprezentujące ograniczenie pojedynczego wskaźnika w postaci: Zmienna(indicator_id) = (activate_on_zero ? 0 : 1) ⇒ dolna granica <= wyrażenie <= górna_granica.

Jeśli zmienna powiązana z tym ograniczeniem (wskaźnik lub występująca w polu expression) zostanie usunięta, jest traktowana tak, jakby miała wartość 0. W szczególności usunięcie zmiennej wskaźnika oznacza, że ograniczenie wskaźnika jest nieważne, jeśli funkcja activate_on_zero ma wartość fałsz, i że jest odpowiednikiem ograniczenia liniowego, jeśli zasada activate_on_zero ma wartość prawda.

Pola
activate_on_zero

bool

Jeśli ma wartość prawda, jeśli zmienna wskaźnika przyjmuje wartość 0, to domniemane ograniczenie musi obowiązywać. W przeciwnym razie, jeśli zmienna wskaźnika przyjmuje wartość 1, wtedy wymagane ograniczenie musi obowiązywać.
expression

SparseDoubleVectorProto

Musi być prawidłowym wyrażeniem liniowym w odniesieniu do modelu, który zawiera: * Wszystkie warunki określone w SparseDoubleVectorProto, * Wszystkie elementy expression.values muszą być skończone, * expression.ids są podzbiorem VariablesProto.ids.
lower_bound

double

Musi mieć wartość w [-inf, inf). Nie może to być NaN.
upper_bound

double

Musi mieć wartość w (-inf, inf]; nie może być NaN.
name

string

Wiadomości nadrzędne mogą mieć w tym polu wymagania dotyczące unikalności, np.: ModelProto.indicator_constraints i IndicatorConstraintUpdatesProto.new_constraints.
indicator_id

int64

Identyfikator odpowiadający zmiennej binarnej lub nieskonfigurowany. Jeśli zasada jest nieskonfigurowana, ograniczenie wskaźnika jest ignorowane. Jeśli zasada jest skonfigurowana, wymagane są: * ZmiennasProto.integers[indicator_id] = true, * ZmiennasProto.lower_bounds[indicator_id] >= 0, * ZmiennasProto.upper_bounds[indicator_id] <= 1. MathOpt nie weryfikuje tych warunków, ale jeśli nie zostaną spełnione, rozwiązanie zwróci błąd po rozwiązaniu problemu.

LPAlgorithmProto

Wybiera algorytm do rozwiązywania programów liniowych.

Wartości w polu enum
LP_ALGORITHM_UNSPECIFIED
LP_ALGORITHM_PRIMAL_SIMPLEX Metoda jednoskładnikowa (pierwotna). Zwykle można uzyskać roztwory pierwsze i podwójne, promienie pierwotne/podwójne dotyczące problemów podstawowych lub podwójnych, oraz podstawę.
LP_ALGORITHM_DUAL_SIMPLEX Metoda podwójnej jednostajnej. Zwykle można uzyskać roztwory pierwsze i podwójne, promienie pierwotne/podwójne dotyczące problemów podstawowych lub podwójnych, oraz podstawę.
LP_ALGORITHM_BARRIER Metoda barierowa, zwana też metodą punktu wewnętrznego (IPM). Zwykle można uzyskać zarówno rozwiązania pierwsze, jak i podwójne. Niektóre implementacje mogą również generować promienie na nieograniczone lub niewykonalne problemy. Podstawa nie jest podana, chyba że rozwiązanie wykonujące operację „crossover” i kończy się jednokrotnym.
LP_ALGORITHM_FIRST_ORDER Algorytm oparty na metodzie pierwszego rzędu. Zwykle tworzą one zarówno rozwiązania podstawowe, jak i podwójne, a potem również zaświadczenia o pierwotnej lub podwójnej niewykonalności. Metody pierwszego zamówienia zapewniają zwykle rozwiązania z mniejszą dokładnością, więc użytkownicy powinni zadbać o ustawianie parametrów jakości (np. tolerancji) i weryfikowanie rozwiązań.

LimitProto

Gdy funkcja Solve() zatrzymuje się wcześniej z zasadą FinishReasonProto FEASIBLE lub NO_SOLUTION_FOUND, określony limit został osiągnięty.

Wartości w polu enum
LIMIT_UNSPECIFIED Używana jako wartość null w przypadku zakończenia działania spoza limitu (np. TERMINATION_REASON_OPTIMAL).
LIMIT_UNDETERMINED Rozwiązanie nie pokazuje, który limit został osiągnięty.
LIMIT_ITERATION Algorytm iteracyjny został zatrzymany po przeprowadzeniu maksymalnej liczby iteracji (np. jednorazowych lub iteracji bariery).
LIMIT_TIME Algorytm zatrzymał się po czasie obliczeniowym określonym przez użytkownika.
LIMIT_NODE Algorytm powiązany z gałęzią i powiązanymi z gałęzią został zatrzymany, ponieważ zbadał maksymalną liczbę węzłów w drzewie z gałęzią i powiązaną.
LIMIT_SOLUTION Algorytm został zatrzymany, ponieważ znalazł wymaganą liczbę rozwiązań. Jest on często używany w mechanizmach IP, aby umożliwić rozwiązanie zadania, które zwróciło pierwsze możliwe do znalezienia rozwiązanie.
LIMIT_MEMORY Algorytm został zatrzymany, ponieważ zabrakło pamięci.
LIMIT_CUTOFF Rozwiązanie zostało uruchomione z końcem wartości (np.SolveParameters. cutoff_limit) dla celu, co oznaczało, że użytkownik nie chce żadnego rozwiązania gorszego niż wartość graniczna.Rozwiązanie stwierdziło, że nie ma rozwiązań co najmniej tak dobrych jak wartość graniczna. Zwykle nie podano dodatkowych informacji o rozwiązaniu.
LIMIT_OBJECTIVE Algorytm został zatrzymany, ponieważ znalazł rozwiązanie lub granicę wyższą niż limit ustawiony przez użytkownika (patrz SolveParameters.objective_limit i SolveParameters.best_bound_limit.
LIMIT_NORM Algorytm został zatrzymany, ponieważ norma powtórzenia stała się za duża.
LIMIT_INTERRUPTED Algorytm został zatrzymany z powodu sygnału przerwy w działaniu lub żądania przerwania przez użytkownika.
LIMIT_SLOW_PROGRESS Algorytm się zatrzymał, ponieważ nie mógł kontynuować pracy nad rozwiązaniem.
LIMIT_OTHER

Algorytm został zatrzymany z powodu limitu nieobjętego żadnym z powyższych. Pamiętaj, że wartość LIMIT_UNDETERMINED jest używana, gdy nie można określić przyczyny. Wartość LIMIT_OTHER jest używana, gdy przyczyna jest znana, ale nie pasuje do żadnej z powyższych alternatyw.

ZakończenieProto.detail może zawierać dodatkowe informacje o limicie.

LinearConstraintsProto

Tak jak poniżej zdefiniujemy „#ograniczenia liniowe” = rozmiar(LinearConstraintsProto.ids).

Pola
ids[]

int64

Musi być nieujemna i ściśle rosnąca. Nie można użyć wartości max(int64).
lower_bounds[]

double

Długość powinna być równa #ograniczeniom liniowym, wartościom w [-inf, inf).
upper_bounds[]

double

Długość musi być równa #ograniczeniom liniowym, wartościom w (-inf, inf].
names[]

string

Jeśli nie jest skonfigurowana, przyjmuje się, że są to wszystkie puste ciągi. W przeciwnym razie długość powinna być równa #linear limits.

Wszystkie nazwy niepuste muszą być różne.

LinearExpressionProto

Rzadka reprezentacja wyrażenia liniowego (ważona suma zmiennych oraz stałe przesunięcie).

Pola
ids[]

int64

Identyfikatory zmiennych. Musi być sortowana (w kolejności rosnącej), w której wszystkie elementy są różne.
coefficients[]

double

Musi mieć taką samą długość jak identyfikatory. Wartości muszą być skończone, a nie mogą być wartością NaN.
offset

double

Musi być skończona i nie może być NaN.

ModelProto

Problem z optymalizacją. MathOpt obsługuje: – zmienne decyzji ciągłej i liczby całkowitej z opcjonalnymi granicami skończonymi. – cele liniowe i kwadratowe (pojedynczy lub wiele celów), zminimalizowane lub zmaksymalizowane; – Kilka typów ograniczeń, w tym: * Ograniczenia liniowe * Ograniczenia kwadratowe * Ograniczenia stożkowe drugiego rzędu * Ograniczenia logiczne > Ograniczenia SOS1 i SOS2 > Ograniczenia wskaźnika

Domyślnie ograniczenia są reprezentowane w mapach „id-to-data”. Ograniczenia liniowe prezentujemy w efektywniejszym formacie „struktury tablic”.

Pola
name

string
variables

VariablesProto
objective

ObjectiveProto

Główny cel modelu.
auxiliary_objectives

map<int64, ObjectiveProto>

Cele pomocnicze do wykorzystania w modelach wielozadaniowych.

Identyfikatory kluczy mapy muszą mieć wartość [0, max(int64)). Każdy priorytet i każda nazwa niepusta muszą być unikalne i różnić się od głównego atrybutu objective.
linear_constraints

LinearConstraintsProto
linear_constraint_matrix

SparseDoubleMatrixProto

Współczynniki zmienne ograniczeń liniowych.

Jeśli zmienna powiązana z tym ograniczeniem zostanie usunięta, jest traktowana tak, jakby była ustawiona na wartość 0.

Wymagania: * linear_constraint_matrix.row_ids to elementy atrybutu linear_constraints.ids. * linear_constraint_matrix.column_ids to elementy zmiennych.id. * Wpisy macierzy nie mają wartości zero. * Wszystkie wartości parametru linear_constraint_matrix.values muszą być skończone.
quadratic_constraints

map<int64, QuadraticConstraintProto>

Ograniczenia kwadratowe w modelu.
second_order_cone_constraints

map<int64, SecondOrderConeConstraintProto>

Ograniczenia stożka drugiego rzędu w modelu.
sos1_constraints

map<int64, SosConstraintProto>

Ograniczenia SOS1 w modelu, zgodnie z którymi maksymalnie 1 expression może być różna od zera. Opcjonalne wpisy weights to szczegół wdrożenia używany przez rozwiązanie do szybszego uzyskiwania dostępu. Rozwiązania mogą przy użyciu tych wag (ale nie muszą) wybierać decyzje rozgałęziające, które generują „zrównoważone” węzły podrzędne.
sos2_constraints

map<int64, SosConstraintProto>

Ograniczenia SOS2 w modelu, zgodnie z którymi maksymalnie 2 wpisy zmiennej expression mogą być różne od zera i muszą przylegać do siebie w swojej kolejności. Jeśli nie podano żadnego parametru weights, będzie to porządek liniowy na liście expressions. Jeśli zostaną podane wartości weights, będzie ona obowiązywać w kolejności rosnącej.
indicator_constraints

map<int64, IndicatorConstraintProto>

Ograniczenia wskaźnika w modelu, które egzekwują, że jeśli binarna „zmienna wskaźnika” ma wartość 1, musi obowiązywać „domniemane ograniczenie”.

ModelSolveParametersProto

Pola
variable_values_filter

SparseVectorFilterProto

Filtr stosowany do wszystkich zwróconych rozproszonych kontenerów objętych kluczem przez zmienne w PrimalSolutionProto i PrimalRayProto (PrimalSolutionProto.variable_values oraz PrimalRayProto.variable_values).

Wymagania: * filter_ids to elementy elementu ZmiennasProto.ids.
dual_values_filter

SparseVectorFilterProto

Filtr stosowany do wszystkich zwróconych rozproszonych kontenerów objętych ograniczeniami liniowymi w usługach DualSolutionProto i DualRay (DualSolutionProto.dual_values, DualRay.dual_values).

Wymagania: * filter_ids to elementy elementu LinearConstraints.ids.
reduced_costs_filter

SparseVectorFilterProto

Filtr, który jest stosowany do wszystkich zwróconych rozproszonych kontenerów objętych kluczem przez zmienne w DualSolutionProto i DualRay (DualSolutionProto.reduced_costs, DualRay.reduced_costs).

Wymagania: * filter_ids to elementy elementu ZmiennasProto.ids.
initial_basis

BasisProto

Opcjonalna podstawa początkowa układów jednokrotnych uruchamianych częściowo z pamięci. Jeśli jest ustawiony, powinien być prawidłowy zgodnie z ValidateBasis w validators/solution_validator.h przy bieżącym ModelSummary.
solution_hints[]

SolutionHintProto

Opcjonalne wskazówki dotyczące rozwiązań. Jeśli rozwiązanie podstawowe akceptuje tylko 1 podpowiedź, używana jest pierwsza.
branching_priorities

SparseInt32VectorProto

Opcjonalne priorytety rozgałęzienia. Zmienne z wyższymi wartościami zostaną najpierw rozgałęzione. Zmienne, dla których priorytety nie są ustawione, otrzymują domyślny priorytet rozwiązania (zwykle jest to zero).

Wymagania: * Braning_priorities.values musi być skończony. * Branch_priorities.ids muszą być elementami ZmiennasProto.ids.

ObjectiveBoundsProto

Ogranicza się do optymalnej wartości celu.

Pola
primal_bound

double

Funkcja Solver twierdzi, że wartość optymalna jest równa lub wyższa (mniejsza przy minimalizacji i wyższa przy maksymalizacji) niż primal_bound a pierwotna tolerancja wykonalności rozwiązania (patrz ostrzeżenie poniżej): * element primal_bound to prosty (+inf dla minimalizacji i -inf dla maksymalizacji), gdy rozwiązanie nie twierdzi, że ma taką granicę. * Argument granica_pierwotna może być bliższy wartości optymalnej niż cel najlepszego pierwszego możliwego rozwiązania. W szczególności argument granica_pierwotna może być nie trywialny, nawet jeśli nie zostały zwrócone żadne podstawowe rozwiązania wykonalne. Uwaga: precyzyjne twierdzenie mówi, że istnieje rozwiązanie podstawowe, które: * jest wykonalne liczbowo (tj. do osiągnięcia tolerancji rozwiązania), a * ma wartość obiektywną granica_pierwotna. To numeryczne rozwiązanie może być nieco niewykonalne. W takim przypadku wartość pierwotna_granica może być znacznie lepsza od wartości optymalnej. Przeniesienie pierwotnej tolerancji wykonalności na tolerancję dla granic_pierwotnej nie jest trywialne, zwłaszcza gdy tolerancja wykonalności jest stosunkowo duża (np. w przypadku rozwiązywania problemów z PDLP).
dual_bound

double

Funkcja Solver twierdzi, że wartość optymalna jest równa lub mniejsza (większa przy minimalizacji i mniejsza dla maksymalizacji) niż dual_bound do wartości podwójnej wykonalności rozwiązań (patrz ostrzeżenie poniżej): * dual_bound to minimalna wartość (-inf dla minimalizacji i +inf dla maksymalizacji), gdy rozwiązanie nie twierdzi, że ma taką granicę. Podobnie jak w przypadku argumentu granica_pierwotna, może się to zdarzyć w przypadku niektórych rozwiązań, nawet po zwróceniu wartości optymalnej. Rozwiązania MIP zwykle zgłaszają granicę, nawet jeśli jest ona nieprecyzyjna. * w przypadku problemów ciągłych argument podwójna_granica może być bliższy wartości optymalnej niż cel najlepszego podwójnego wykonalnego rozwiązania. W przypadku MIP jedna z pierwszych nieprostych wartości podwójnej wartości jest często optymalną wartością złagodzenia LP podczas MIP. * Wartość dual_bound powinna być lepsza (mniejsza w przypadku minimalizacji, a większa w przypadku maksymalizacji) niż wartość primal_bound względem tolerancji rozwiązań (zobacz ostrzeżenie poniżej). Ostrzeżenie: * w przypadku ciągłych problemów precyzyjne twierdzenie mówi, że istnieje podwójne rozwiązanie, które: * jest wykonalne liczbowo (czyli wykonalne do maksymalnej tolerancji rozwiązań), a * ma wartość obiektywną dual_bound. To numeryczne rozwiązanie może być nieco niewykonalne. W takim przypadku podwójna_granica może być znacznie gorsza niż wartość optymalna i granica_pierwotna. Podobnie jak w przypadku pierwszego przypadku przekształcenie podwójnej tolerancji wykonalności na tolerancję dla zakresu podwójnej nie jest trywialne, zwłaszcza gdy tolerancja wykonalności jest stosunkowo duża. Niektóre rozwiązania zapewniają jednak poprawioną wersję parametru podwójna_granica, która może być bezpieczniejsza liczbowo. Dostęp do tej poprawionej wersji można uzyskać przez określone dane wyjściowe rozwiązania (np. w przypadku PDLP, pdlp_output.Convergence_information.improveed_dual_objective). * W przypadku rozwiązań MIP parametr podwójny może być powiązany z rozwiązaniem podwójnym w celu pewnej ciągłej relaksacji (np.relaksacja LP). Często jest to złożona konsekwencja wykonania rozwiązania i zwykle jest bardziej nieprecyzyjna niż wartości progowe zgłaszane przez rozwiązania LP.

ObjectiveProto

Pola
maximize

bool

Wartość fałsz oznacza minimalizację, prawda oznacza maksymalizację
offset

double

Musi być skończone, a nie NaN.
linear_coefficients

SparseDoubleVectorProto

Terminy ObjectiveProto, które są liniowe w zmiennych decyzji.

Wymagania: * linear_coeffectives.ids są elementami ZmiennasProto.ids. * Nieokreślona wartość ZmiennasProto odpowiada zero. * Wszystkie wartości współczynników_liniowych muszą być skończone. * Wartości współczynników_liniowych.mogą wynosić zero, ale powoduje to marnowanie przestrzeni.
quadratic_coefficients

SparseDoubleMatrixProto

Terminy obiektywne, które w zmiennych decyzji są kwadratowe.

Wymagania oprócz wymagań dotyczących komunikatów SparseDoubleMatrixProto: * Każdy element elementu quadratic_coeffectives.row_ids i każdy element quadratic_coeffectives.column_ids musi być elementem zmiennysProto.ids. * Macierz musi być górnym trójkątem: dla każdego i – współczynniki_kwadratowe.identyfikatory.wierszy[i] <= współczynniki_kwadratowe.identyfikatory_kolumn[i].

Uwaga: * Hasła, które nie są wyraźnie zapisane, mają współczynnik zerowy. * Elementy we właściwości „współczynniki_kwadratowe.współczynniki” mogą wynosić 0, ale to tylko marnuje przestrzeń.
name

string

Wiadomości nadrzędne mogą mieć w tym polu wymagania dotyczące unikalności, np. ModelProto.objectives i AuxiliaryObjectivesUpdatesProto.new_objectives.
priority

int64

W przypadku problemów o wielu celach: priorytet tego celu w porównaniu z innymi celami (niższy jest ważniejszy). Ta wartość nie może być liczbą ujemną. Dodatkowo każdy priorytet celu w modelu musi być inny w momencie rozwiązania. Ten warunek nie jest weryfikowany na poziomie protokołu, więc modele mogą tymczasowo mieć cele o tym samym priorytecie.

PrimalRayProto

Kierunek nieograniczonej poprawy problemu optymalizacji; równoważnie certyfikat niewykonalności dla podwójnych problemów optymalizacyjnych.

Np. spójrz na prosty program liniowy: min c * x s.t. A * x >= b x >= 0 Promień początkowy to x, który spełnia: c * x < 0 A * x >= 0 x >= 0. Obserwuj, że w przypadku każdego dodatniego rozwiązania Promień początkowy jest także dowodem na niewykonalny problem z podwójną optymalizacją.

W poniższym komunikacie PrimalRay wartości_zmienne mają wartość x.

Pola
variable_values

SparseDoubleVectorProto

Wymagania: * zmienna_values.ids to elementy zmiennej variablesProto.ids. * Wszystkie wartości_zmienne.wartości muszą być skończone.

PrimalSolutionProto

Rozwiązanie problemu z optymalizacją.

Na przykład spróbuj zastosować prosty program liniowy: min c * x s.t. A * x >= b x >= 0. Rozwiązanie pierwsze to przypisanie wartości do x. Jest możliwe, jeśli spełnia warunki A * x >= b oraz x >= 0 z powyższych pól. W poniższym komunikacie PrimalSolutionProto wartości zmiennych to x, a cel_value to c * x.

Pola
variable_values

SparseDoubleVectorProto

Wymagania: * zmienna_values.ids to elementy zmiennej variablesProto.ids. * Wszystkie wartości_zmienne.wartości muszą być skończone.
objective_value

double

Wartość celu obliczona przez używane rozwiązanie. Nie może być nieskończona ani naN.
auxiliary_objective_values

map<int64, double>

Wartości celu pomocniczego obliczone przez używane rozwiązanie. Klucze muszą być prawidłowymi identyfikatorami celów pomocniczych. Wartości nie mogą być nieskończone ani NaN.
feasibility_status

SolutionStatusProto

Stan wykonalności rozwiązania zgodnie z jego rozwiązaniem.

ProblemStatusProto

Stan wykonalności zadania początkowego i jego podwójny (lub dwójka ciągłej relaksacji) zgodnie z deklaracją rozwiązania. Rozwiązanie nie musi zwracać certyfikatu w związku z roszczeniem (np. może deklarować podstawową wykonalność bez zwrócenia podstawowego wykonalnego rozwiązania). Ten połączony stan zapewnia wyczerpujący opis twierdzeń rozwiązania na temat wykonalności i nieograniczonego zakresu rozwiązania. Przykład:

  • Stan wykonalny w przypadku problemów podstawowych i podwójnych wskazuje, że wersja podstawowa jest wykonalna i ograniczona oraz prawdopodobnie ma rozwiązanie optymalne (gwarantowane w przypadku problemów bez ograniczeń nieliniowych).
  • Stan początkowy jest możliwy do wykonania, a podwójny niemożliwy do wykonania.

Zauważ, że podwójny stan niemożliwy do wykonania (tj. któremu towarzyszy nieokreślony stan początkowy) nie oznacza, że podstawowy problem jest nieuzasadniony, ponieważ oba problemy mogą być niewykonalne. Co więcej, choć początkowy i podwójny stan wykonalności może sugerować istnienie optymalnego rozwiązania, nie gwarantuje to, że udało się znaleźć takie optymalne rozwiązanie.

Pola
primal_status

FeasibilityStatusProto

Stan problemu pierwotnego.
dual_status

FeasibilityStatusProto

Stan podwójnych problemów (lub dla ciągłej relaksacji).
primal_or_dual_infeasible

bool

Jeśli ma wartość prawda, rozwiązanie twierdzi, że problem podstawowy lub podwójny jest niemożliwy, ale nie wie, który z nich (lub czy oba są niewykonalne). Może mieć wartość tylko wtedy, gdy stan podstawowy_problemu = podwójny_problem_status = kNieokreślony. Te dodatkowe informacje są często potrzebne, gdy wstępne przetwarzanie wskazuje, że nie ma optymalnego rozwiązania problemu (ale nie da się określić, czy jest ono spowodowane niewykonaniem, nieograniczeniem czy jedno i drugim).

QuadraticConstraintProto

Pojedyncze ograniczenie kwadratowe o postaci: lb <= suma{linear_terms} + suma{quadratic_terms} <= ub.

Jeśli zmienna powiązana z tym ograniczeniem zostanie usunięta, jest traktowana tak, jakby była ustawiona na wartość 0.

Pola
linear_terms

SparseDoubleVectorProto

Warunki liniowe w zmiennych decyzji.

Oprócz wymagań dotyczących wiadomości SparseDoubleVectorProto wymagamy, aby: * linear_terms.ids były elementami variablesProto.ids. * Wszystkie wartości linear_terms.value muszą być skończone i nie-NaN.

Uwaga: * pominięte identyfikatory zmiennych mają współczynnik równy 0. * Wartości parametrów linear_terms.mogą mieć wartość zero, ale powoduje to marnowanie miejsca.
quadratic_terms

SparseDoubleMatrixProto

hasła, które w zmiennych decyzji są kwadratowe.

Oprócz wymagań dotyczących wiadomości SparseDoubleMatrixProto wymagamy, aby: * Każdy element obiektu quadratic_terms.row_ids i każdy element quadratic_terms.column_ids musi być elementem zmiennysProto.ids. * Macierz musi być górnym trójkątem: dla każdego i – quadratic_terms.row_ids[i] <= quadratic_terms.column_ids[i].

Uwaga: * Hasła, które nie są wyraźnie zapisane, mają współczynnik zerowy. * Elementy quadratic_terms.coeffectives mogą wynosić 0, ale to tylko marnuje miejsce.
lower_bound

double

Musi mieć wartość w formacie [-inf, inf) i nie może być większa niż upper_bound.
upper_bound

double

Wartość musi mieć wartość w (-inf, inf] i być większa lub równa lower_bound.
name

string

Wiadomości nadrzędne mogą mieć w tym polu wymagania dotyczące unikatowości, np. zobacz ModelProto.quadratic_constraints i QuadraticConstraintUpdatesProto.new_constraints.

SecondOrderConeConstraintProto

Pojedyncze ograniczenie stożka drugiego rzędu w postaci:

||arguments_to_norm||_2 <= upper_bound,

gdzie upper_bound i każdy element arguments_to_norm są wyrażeniami liniowymi.

Jeśli zmienna powiązana z tym ograniczeniem zostanie usunięta, jest traktowana tak, jakby była ustawiona na wartość 0.

Pola
upper_bound

LinearExpressionProto
arguments_to_norm[]

LinearExpressionProto
name

string

Wiadomości nadrzędne mogą mieć w tym polu wymagania dotyczące unikalności, np.: ModelProto.second_order_cone_constraints i SecondOrderConeConstraintUpdatesProto.new_constraints.

SolutionHintProto

Sugerowane rozwiązanie początkowe.

Rozwiązania do zarządzania urządzeniami mobilnymi wymagają zwykle tylko informacji podstawowych (variable_values), podczas gdy rozwiązania tego typu wymagają zarówno informacji podstawowych, jak i podwójnych (dual_values).

Wiele rozwiązań do zarządzania MIP działa z: (1) rozwiązaniami częściowymi, które nie określają wszystkich zmiennych, lub (2) rozwiązaniami niemożliwymi do wykonania. W takich przypadkach rozwiązania zwykle realizują lub poprawiają wskazówkę w ramach podrzędnej witryny MIP.

Sposób, w jaki wskazówka jest używana przez rozwiązanie, w dużej mierze zależy od jego rozwiązania, typu zadania i używanego algorytmu. Najbardziej niezawodnym sposobem na zapewnienie właściwego zastosowania podpowiedzi jest czytanie powiązanych z nią dzienników rozwiązań z uwzględnieniem podpowiedzi i bez niej.

Rozwiązania liniowe oparte na zwykłym działaniu (LP) zwykle preferują początkową podstawę do uzyskania podpowiedzi (w przeciwnym razie muszą przejść na drugą stronę, aby przekonwertować wskazówkę na podstawowe wykonalne rozwiązanie).

Pola
variable_values

SparseDoubleVectorProto

Prawdopodobnie częściowe przypisanie wartości do podstawowych zmiennych zadania. W przypadku tego komunikatu podrzędnego niezależne od rozwiązania są te wymagania: * zmienne_wartości.id są elementami elementu ZmiennasProto.ids. * Wszystkie wartości_zmienne.wartości muszą być skończone.
dual_values

SparseDoubleVectorProto

(potencjalnie częściowe) przypisanie wartości do ograniczeń liniowych problemu.

Wymagania: * dual_values.ids to elementy elementu LinearConstraintsProto.ids. * Wszystkie wartości podwójne.wartości muszą być skończone.

SolutionProto

Zawartość rozwiązania zależy od rodzaju problemu i jego rozwiązania. Obecnie często używane wzorce to 1. Rozwiązania MIP zwracają tylko rozwiązanie pierwsze. 2. Rozwiązania funkcji Simplex LP często zwracają podstawę oraz rozwiązania podstawowe i podwójne powiązane z tą podstawą. 3. Inne rozwiązania ciągłe zwracają rozwiązanie pierwsze i podwójne, które są połączone w postaci zależnej od rozwiązania.

Wymagania: * należy ustawić co najmniej jedno pole; rozwiązanie nie może być puste.

Pola
primal_solution

PrimalSolutionProto
dual_solution

DualSolutionProto
basis

BasisProto

SolutionStatusProto

Wykonalność rozwiązania pierwotnego lub podwójnego zgodnie z opisem rozwiązania.

Wartości w polu enum
SOLUTION_STATUS_UNSPECIFIED Wartość zabezpieczenia reprezentująca brak stanu.
SOLUTION_STATUS_UNDETERMINED Solver nie zgłasza roszczenia do stanu wykonalności.
SOLUTION_STATUS_FEASIBLE Solver twierdzi, że rozwiązanie jest możliwe.
SOLUTION_STATUS_INFEASIBLE Solver twierdzi, że rozwiązanie jest niemożliwe.

SolveParametersProto

Parametry do sterowania pojedynczym rozwiązaniem.

Zawiera oba parametry wspólne dla wszystkich rozwiązań, np. time_limit, i parametry konkretnego rozwiązania, np. gscip. Jeśli wartość jest ustawiona zarówno w polu wspólnym, jak i pola konkretnego rozwiązania, używane jest ustawienie właściwe dla rozwiązania.

Typowe parametry, które są opcjonalne i nieskonfigurowane, lub wyliczenie z nieokreśloną wartością wskazują, że używane jest domyślne rozwiązanie rozwiązania.

W przypadku rozwiązań innych niż używane są ignorowane ich parametry.

Parametry zależne od modelu (np. priorytet rozgałęziania jest ustawiany dla każdej zmiennej) są przekazywane w funkcji ModelSolveParametersProto.

Pola
time_limit

Duration

Maksymalny czas, jaki rozwiązanie powinno poświęcić na rozwiązanie problemu (lub nieskończony, jeśli nie jest ustawiony).

To nie jest sztywny limit, więc czas rozwiązania może ją nieznacznie przekroczyć. Ten parametr jest zawsze przekazywany do rozwiązania bazowego. Rozwiązanie domyślne nie jest używane.
enable_output

bool

Włącza drukowanie logów czasu implementacji rozwiązania. Lokalizacja tych logów czasu zależy od rozwiązania. W przypadku SCIP i Gurobi będą to standardowe strumienie danych wyjściowych. W przypadku Glop i CP-SAT spowoduje to LOG(INFO).

Pamiętaj, że jeśli rozwiązanie obsługuje wywołanie zwrotne wiadomości, a użytkownik zarejestruje wywołanie zwrotne, ta wartość parametru jest ignorowana i żadne ślady nie są drukowane.
lp_algorithm

LPAlgorithmProto

Algorytm do rozwiązania programu liniowego. Jeśli ma wartość LP_ALGORITHM_UNSPECIFIED, użyj domyślnego algorytmu rozwiązania.

W przypadku zadań, które nie są programami liniowymi, ale są programami liniowymi, rozwiązania mogą używać tej wartości. Na przykład rozwiązania MIP będą zwykle używać tej funkcji tylko do rozwiązania głównego strony głównej (i w przeciwnym razie do korzystania z funkcji podwójnych jednorazowych).
presolve

EmphasisProto

Staraj się uprościć zadanie przed uruchomieniem głównego algorytmu lub domyślnego poziomu nakładu pracy rozwiązania, jeśli EMPHASIS_UNSPECIFIED.
cuts

EmphasisProto

Staraj się uzyskać silniejszą zrelaksowanie strony docelowej (tylko MIP) lub domyślny poziom nakładu pracy rozwiązania, jeśli EMPHASIS_UNSPECIFIED.

UWAGA: wyłączenie cięć może uniemożliwić wywołanie cięć w MIP_NODE. To zachowanie jest związane z rozwiązaniem.
heuristics

EmphasisProto

Wysiłek w poszukiwaniu możliwych rozwiązań wykraczających poza te występujące w pełnej procedurze wyszukiwania (tylko MIP) lub domyślny poziom nakładu pracy rozwiązania, jeśli ma wartość SOURCE_UNSPECIFIED.
scaling

EmphasisProto

Spróbuj przeskalować problem, aby poprawić stabilność liczbową, lub domyślny poziom nakładu pracy rozwiązania, jeśli SOURCE_UNSPECIFIED.
iteration_limit

int64

Ograniczenie liczby iteracji bazowego algorytmu (np. przestawienia w formacie jednokrotnym). Konkretne zachowanie zależy od użytego rozwiązania i algorytmu, ale często może mieć deterministyczny limit rozwiązania (może być wymagana dalsza konfiguracja, np. 1 wątek).

Zwykle obsługiwane przez rozwiązania LP, QP i MIP, ale w przypadku MIP obowiązują też rozwiązania node_limit.
node_limit

int64

Ogranicz liczbę podproblemów rozwiązanych w wyszukiwaniu wyliczeniowym (np. rozgałęzienie i granica). W przypadku wielu rozwiązań można to wykorzystać do deterministycznego ograniczenia obliczeń (może być potrzebna dalsza konfiguracja, np. 1 wątek).

Zwykle w przypadku rozwiązań MIP sprawdź też limit iteration_limit.
cutoff_limit

double

Rozwiązanie zatrzymuje się wcześniej, jeśli okazuje się, że nie ma rozwiązań podstawowych, które są przynajmniej tak dobre jak wynik odcięcia.

W przypadku wcześniejszego zatrzymania rozwiązanie zwraca powód zakończenia: NO_SOLUTION_FOUND z limitem CUTOFF. Nie musi podawać żadnych dodatkowych informacji. Nie ma wpływu na wartość zwracaną, jeśli nie ma wcześniejszego zatrzymania.

Stosowanie tolerancji jest zalecane, jeśli chcesz zwracać rozwiązania, w przypadku których cel jest dokładnie taki sam jak wartość odcięcia.

Więcej informacji i porównanie z atrybutem best_bound_limit znajdziesz w przewodniku użytkownika.
objective_limit

double

Rozwiązanie zatrzymuje się wcześniej, gdy znajduje rozwiązanie co najmniej tak dobre, z powodem zakończenia działania FEASIBLE i ograniczeniem OBJECTIVE.
best_bound_limit

double

Rozwiązanie zatrzymuje się wcześniej, gdy tylko okazuje się, że najlepsza granica jest przynajmniej taka dobra, z powodu zakończenia działania FEASIBLE lub NO_SOLUTION_FOUND i limitem OBJECTIVE.

Więcej informacji i porównanie z atrybutem cutoff_limit znajdziesz w przewodniku użytkownika.
solution_limit

int32

Rozwiązanie zatrzymuje się wcześniej po znalezieniu tylu możliwych rozwiązań, przy czym powód zamknięcia jest FEASIBLE i ogranicza ROZWIĄZANIE. Wartość musi być większa niż 0, jeśli jest ustawiona. Często używa się go, aby zatrzymywał rozwiązanie na pierwszym znalezionym możliwym rozwiązaniu. Pamiętaj, że nie ma gwarancji co do wartości docelowej żadnego ze zwróconych rozwiązań.

Rozwiązania te zwykle nie zwracają więcej rozwiązań niż wynosi limit, ale nie jest to wymuszane przez MathOpt (patrz również b/214041169).

Obecnie obsługiwany w przypadku Gurobi i SCIP oraz tylko CP-SAT z wartością 1.
threads

int32

Jeśli jest ustawiony, musi być >= 1.
random_seed

int32

Pole wyjściowe generatora liczb pseudolosowych w bazowym rozwiązaniu. Pamiętaj, że wszystkie rozwiązania korzystają z liczb pseudolosowych, aby wybierać takie rzeczy jak perturbacja w algorytmie LP, reguły rozłączania i korekty heurystyczne. Ich zmiana może mieć zauważalny wpływ na zachowanie rozwiązania.

Chociaż wszystkie rozwiązania mają pojęcie ziarna, pamiętaj, że prawidłowe wartości zależą od rzeczywistego rozwiązania. - Gurobi: [0:GRB_MAXINT] (na dzień Gurobi 9.0 to 2x10^9). – GSCIP: [0:2147483647] (czyli MAX_INT, kint32max albo 2^31-1). - GLOP: [0:2147483647] (tak samo jak wyżej) We wszystkich przypadkach funkcja solowa otrzyma wartość równą: MAX(0; MIN(MAX_VALID_VALUE_FOR_SOLVER; random_seed)).
absolute_gap_tolerance

double

Bezwzględna tolerancja optymalizacji (głównie) w przypadku rozwiązań MIP.

Bezwzględna wartość GAP to wartość bezwzględna różnicy między: * wartością obiektywną najlepszego znalezionego rozwiązania, * podwójną granicą wypracowaną przez wyszukiwanie. Rozwiązanie może się zatrzymać, gdy bezwzględny GAP osiągnie maksimum absolute_gap_tolerance (po ustawieniu) i zwrócić TERMINATION_REASON_OPTIMAL.

Jeśli jest ustawione, musi mieć wartość >= 0.

Zobacz też względne_gap_tolerance.
relative_gap_tolerance

double

Względna tolerancja optymalizacji (głównie) rozwiązań MIP.

Względny GAP to znormalizowana wersja bezwzględnego GAP (zdefiniowana za pomocą argumentu absolute_gap_tolerance), gdzie normalizacja zależy od rozwiązania, np. bezwzględny GAP podzielony przez docelową wartość najlepszego możliwego rozwiązania.

Rozwiązanie może się zatrzymać, gdy względny GAP osiągnie najwyższy poziom wartości względem odstępu (w przypadku ustawienia tolerancji) i zwróci wartość TERMINATION_REASON_OPTIMAL.

Jeśli jest ustawione, musi mieć wartość >= 0.

Zobacz też atrybut absolute_gap_tolerance.
solution_pool_size

int32

Podczas wyszukiwania możesz przechowywać do solution_pool_size rozwiązań. Pula rozwiązań ma zwykle 2 funkcje: (1) W przypadku rozwiązań, które mogą zwrócić więcej niż 1 rozwiązanie, ta opcja ogranicza liczbę zwróconych rozwiązań. (2) Niektóre rozwiązania mogą wykorzystywać rozwiązania heurystyczne z wykorzystaniem rozwiązań z puli rozwiązań, więc zmiana tej wartości może wpłynąć na ścieżkę algorytmu. Aby wymusić wypełnienie puli rozwiązań, np. przy użyciu n najlepszych rozwiązań, wymagana jest dodatkowa konfiguracja dotycząca rozwiązań.

SolveResultProto

Umowa dotycząca roztworów podstawowych/podwójnych/promieni jest złożona: Pełny opis znajdziesz na stronie prompt_reasons.md.

Do czasu zawarcia dokładnej umowy najbezpieczniej jest po prostu sprawdzić, czy jest dostępne rozwiązanie lub promień, zamiast polegać na przyczynie rozwiązania umowy.

Pola
termination

TerminationProto

Przyczyna zatrzymania rozwiązania.
solutions[]

SolutionProto

Ogólna umowa dotycząca kolejności rozwiązań, które powinny być wdrożone w przyszłości, to: 1. Rozwiązania z podstawowym rozwiązaniem wykonalnym, uporządkowane w kolejności od najlepszego pierwotnego celu. 2. Rozwiązania z podwójnym wykonalnym rozwiązaniem uporządkowane według najlepszego podwójnego celu (nieznany podwójny cel jest najgorszy) 3. Pozostałe rozwiązania można zwrócić w dowolnej kolejności.
primal_rays[]

PrimalRayProto

Kierunki niepowiązanej pierwotnej poprawy lub równoważnie certyfikaty podwójnej niewykonalności. Zwykle podawane w polach FinishReasonProtos UNBOUNDED i DUAL_INFEASIBLE
dual_rays[]

DualRayProto

Kierunki nieograniczonego podwójnej poprawy lub równoważne certyfikaty niewykonalności. Zwykle jest podawany w polu FinishReasonProto INFEASIBLE.
solve_stats

SolveStatsProto

Statystyki procesu rozwiązywania, np. czas trwania, iteracje.

SolveStatsProto

Pola
solve_time

Duration

Upływ czasu zegara mierzonego za pomocą parametru math_opt, czyli przybliżonego czasu działania funkcji Solver::Solve(). Uwaga: nie obejmuje to pracy związanej z zbudowaniem modelu.
problem_status

ProblemStatusProto

Stany wykonalności w przypadku problemów podstawowych i podwójnych.
simplex_iterations

int64
barrier_iterations

int64
first_order_iterations

int64
node_count

int64

SolverTypeProto

Rozwiązania obsługiwane przez MathOpt.

Wartości w polu enum
SOLVER_TYPE_UNSPECIFIED
SOLVER_TYPE_GSCIP

Solving Constraint Integer Programs (SCIP) – rozwiązanie innej firmy.

Obsługuje zadania kwadratowe z wykorzystaniem LP, MIP i niewypukłych liczb całkowitych. W przypadku stron docelowych nie są jednak zwracane podwójne dane. Preferuj GLOP dla stron docelowych.
SOLVER_TYPE_GUROBI

Rozwiązanie Gurobi (inna firma).

Obsługuje zadania kwadratowe z wykorzystaniem LP, MIP i niewypukłych liczb całkowitych. Jest to zwykle najszybsza opcja, ale wymaga specjalnych licencji.
SOLVER_TYPE_GLOP

Rozwiązanie Google Glop.

Obsługuje LP z użyciem metod podstawowych i podwójnych jednorazowych.
SOLVER_TYPE_CP_SAT

Rozwiązanie Google do obsługi CP-SAT.

Obsługuje problemy, w których wszystkie zmienne są liczbami całkowitymi i ograniczeniami (lub są domniemane po rozwiązaniu). Eksperymentalne wsparcie mające na celu przeskalowanie i dyskretowanie problemów z wykorzystaniem zmiennych ciągłych.
SOLVER_TYPE_PDLP

Rozwiązanie Google PDLP.

Obsługuje cele kwadratowe w przypadku LP i wypukłych po przekątnych. Używa metod pierwszej kolejności, a nie jednostajnych. Rozwiązuje bardzo duże problemy.
SOLVER_TYPE_GLPK

Pakiet GNU Linear Programming Kit (GLPK) (firmy zewnętrznej).

Obsługuje MIP i LP.

Bezpieczeństwo wątków: GLPK używa lokalnej pamięci wątków do przydzielania pamięci. W efekcie instancje rozwiązania do rozwiązywania problemów muszą zostać zniszczone w tym samym wątku, w którym są tworzone. W przeciwnym razie GLPK ulegnie awarii. Można użyć wywołania funkcji Solver::Solve() w innym wątku niż ten użyty do jego utworzenia, ale nie jest on dokumentowany w GLPK i nie należy tego robić.

W przypadku rozwiązania LPG za pomocą presolveratora rozwiązanie (i niepowiązane promienie) jest zwracane tylko wtedy, gdy zostanie znalezione rozwiązanie optymalne. W przeciwnym razie nic nie zostanie zwrócone. Szczegółowe informacje można znaleźć na stronie glpk-5.0/doc/glpk.pdf nr 40 dostępnej w katalogu glpk-5.0.tar.gz.
SOLVER_TYPE_OSQP

Rozwiązanie, które należy do firmy zewnętrznej w ramach rozwiązania Operator Splitting Quadratic Program (OSQP).

Obsługuje ciągłe problemy z ograniczeniami liniowymi i liniowymi lub wypukłymi celami kwadratowymi. Używa metody pierwszego rzędu.
SOLVER_TYPE_ECOS

The Embedded Conic Solver (ECOS) (inna firma).

Obsługuje problemy LP i SOCP. Używa metod punktów wewnętrznych (bariery).
SOLVER_TYPE_SCS

The Splitting Conic Solver (SCS) (firma zewnętrzna).

Obsługuje problemy LP i SOCP. Używa metody pierwszego rzędu.
SOLVER_TYPE_HIGHS

HiGHS Solver (zewnętrzna).

Obsługuje problemy z LP i MIP (wypukłe QP nie są zaimplementowane).
SOLVER_TYPE_SANTORINI

Referencyjna implementacja rozwiązania MIP przez MathOpt.

Wolne/niezalecane do produkcji. To nie jest Rozwiązanie LP (brak podwójnych informacji).

SosConstraintProto

Dane do reprezentowania jednego ograniczenia SOS1 lub SOS2.

Jeśli zmienna powiązana z tym ograniczeniem zostanie usunięta, jest traktowana tak, jakby była ustawiona na wartość 0.

Pola
expressions[]

LinearExpressionProto

Wyrażenia, do których należy zastosować ograniczenie SOS: * SOS1: maksymalnie 1 element ma wartość inną niż zero. * SOS2: maksymalnie 2 elementy przyjmują wartości różne od zera i muszą przylegać do siebie w powtarzającej się kolejności.
weights[]

double

Pole może być puste lub mieć taką samą długość jak wyrażenia. Jeśli wartość jest pusta, domyślne wagi to 1, 2, ... jeśli występują, wpisy muszą być unikalne.
name

string

Wiadomości nadrzędne mogą mieć w tym polu wymagania dotyczące unikatowości, np. zobacz ModelProto.sos1_constraints i SosConstraintUpdatesProto.new_constraints.

SparseBasisStatusVector

Rzadka reprezentacja wektorów stanów podstaw.

Pola
ids[]

int64

Musi być sortowana (w kolejności rosnącej), w której wszystkie elementy są różne.
values[]

BasisStatusProto

Musi mieć taką samą długość jak identyfikatory.

SparseDoubleMatrixProto

Rzadka reprezentacja macierzy podwójnych.

Macierz jest przechowywana jako potrójna wartość identyfikatora wiersza, identyfikatora kolumny i współczynnika. Te 3 wektory muszą mieć taką samą długość. We wszystkich elementach i, krotka (wiersze_identyfikatory[i] oraz identyfikatory_kolumn[i]) powinny być różne. Wpisy muszą być ułożone w kolejności głównej.

Pola
row_ids[]

int64
column_ids[]

int64
coefficients[]

double

Może nie zawierać NaN.

SparseDoubleVectorProto

Rzadka reprezentacja wektora podwójnej precyzji.

Pola
ids[]

int64

Musi być sortowana (w kolejności rosnącej), w której wszystkie elementy są różne.
values[]

double

Musi mieć taką samą długość jak identyfikatory. Może nie zawierać NaN.

SparseInt32VectorProto

Rzadka reprezentacja wektora liczby całkowitej.

Pola
ids[]

int64

Powinno być sortowane (w kolejności rosnącej), by wszystkie elementy były różne.
values[]

int32

Musi mieć taką samą długość jak identyfikatory.

SparseVectorFilterProto

Ten komunikat umożliwia wysyłanie zapytań o określone części SparseXxxxVector lub ich ustawianie. Domyślne działanie to niczego nie odfiltrowywać. Typowym zastosowaniem jest tworzenie zapytań dotyczących tylko części rozwiązań (tylko wartości niezerowe lub wybranych ręcznie zbiorów wartości zmiennych).

Pola
skip_zero_values

bool

W przypadku SparseBoolVectorProto wartość „zero” wynosi false.
filter_by_ids

bool

Jeśli ma wartość true (prawda), zwracane są tylko wartości odpowiadające identyfikatorom podanym w atrybucie filtrowane_identyfikatory.
filtered_ids[]

int64

Lista identyfikatorów do użycia, gdy filtr filter_by_ids ma wartość prawda. To pole musi być puste, jeśli filtr filter_by_ids ma wartość false (fałsz). UWAGA: jeśli to pole jest puste, a wartość filtra filter_by_ids ma wartość prawda, twierdzisz, że wynik nie powinien zawierać żadnych informacji.

TerminationProto

Wszystkie informacje o tym, dlaczego wywołanie funkcji Solve() zostało zakończone.

Pola
reason

TerminationReasonProto

Dodatkowe informacje w polu limit, gdy wartość to TERMINATION_REASON_FEASIBLE lub TERMINATION_REASON_NO_SOLUTION_FOUND. Szczegółowe informacje znajdziesz na stronie limit.
limit

LimitProto

Ma wartość LIMIT_UNSPECIFIED, chyba że przyczyna to TERMINATION_REASON_FEASIBLE lub TERMINATION_REASON_NO_SOLUTION_FOUND. Nie wszystkie rozwiązania są w stanie określić limit, który spowodował zakończenie działania. Gdy nie można ustalić przyczyny, używana jest wartość LIMIT_UNDETERMINED.
detail

string

Dodatkowe informacje dotyczące zwykle rozwiązania problemu.
problem_status

ProblemStatusProto

Stany wykonalności w przypadku problemów podstawowych i podwójnych. Od 18 lipca 2023 r. ta wiadomość może być niedostępna. Jeśli nie można go znaleźć, argument problem_status można znaleźć w pliku SolveResultProto.solve_stats.
objective_bounds

ObjectiveBoundsProto

Ogranicza się do optymalnej wartości celu. Od 18 lipca 2023 r. ta wiadomość może być niedostępna. Jeśli go nie ma, można go znaleźć w SolveResultProto.solve.stats.best_primal_bound i Goal_bounds.dual_bound, które można znaleźć w SolveResultProto.solve.stats.best_dual_bound.

TerminationReasonProto

Przyczyna zakończenia wywołania funkcji Solve().

Wartości w polu enum
TERMINATION_REASON_UNSPECIFIED
TERMINATION_REASON_OPTIMAL Znaleziono prawdopodobnie optymalne rozwiązanie (do tolerancji liczbowych).
TERMINATION_REASON_INFEASIBLE Problem początkowy nie ma możliwych rozwiązań.
TERMINATION_REASON_UNBOUNDED Problem początkowy jest możliwy i arbitrowo dobre rozwiązania można znaleźć wzdłuż promienia początkowego.
TERMINATION_REASON_INFEASIBLE_OR_UNBOUNDED Problem podstawowy jest niemożliwy do wykonania lub niepowiązany. Więcej informacji o stanie problemu znajdziesz w rozwiązaniu problemu_stats.problem_status. Zwróć uwagę, że w tym miejscu można zmapować stan Gurobi bez ograniczeń.
TERMINATION_REASON_IMPRECISE

Problem został rozwiązany zgodnie z jednym z powyższych kryteriów (Optymalny, Niemożliwy, Bez ograniczeń, Nieograniczony lub Nieograniczony), ale nie spełniono co najmniej 1 tolerancji. Niektóre roztwory lub promienie pierwsze/podwójne są obecne, ale będą one raczej niewykonalne lub (jeśli problem był niemal optymalny) może to być luka między najlepszym celem rozwiązania a najlepszą granicą celu.

Użytkownicy nadal mogą wyszukiwać informacje o rozwiązaniach podstawowych/podwójnych i statystykach roztworów, ale odpowiadają za radzenie sobie z niedokładnością liczbową.
TERMINATION_REASON_FEASIBLE Optymalizator osiągnął jakiś limit i zwracane jest pierwsze wykonalne rozwiązanie. Szczegółowy opis rodzaju limitu, który został osiągnięty, znajdziesz w sekcji SolveResultProto.limit_detail.
TERMINATION_REASON_NO_SOLUTION_FOUND Optymalizator osiągnął jakiś limit i nie znalazł żadnego wykonalnego rozwiązania. Szczegółowy opis rodzaju limitu, który został osiągnięty, znajdziesz w sekcji SolveResultProto.limit_detail.
TERMINATION_REASON_NUMERICAL_ERROR Algorytm został zatrzymany, ponieważ wystąpił nieodwracalny błąd numeryczny. Brak dostępnych informacji o rozwiązaniu.
TERMINATION_REASON_OTHER_ERROR Algorytm został zatrzymany z powodu błędu, który nie jest uwzględniony w jednym ze stanów zdefiniowanych powyżej. Brak dostępnych informacji o rozwiązaniu.

VariablesProto

W przykładzie poniżej definicja „#variables” = size(zmiennasProto.ids).

Pola
ids[]

int64

Musi być nieujemna i ściśle rosnąca. Nie można użyć wartości max(int64).
lower_bounds[]

double

Długość musi być równa #zmienne, wartości w [-inf, inf).
upper_bounds[]

double

Długość musi być równa #zmienne, wartości w (-inf, inf].
integers[]

bool

Długość musi być równa #zmienna. W przypadku zmiennych ciągłych wartość to false, a w przypadku zmiennych całkowitych to prawda.
names[]

string

Jeśli nie jest skonfigurowana, przyjmuje się, że są to wszystkie puste ciągi. W przeciwnym razie długość powinna być równa #variables.

Wszystkie nazwy niepuste muszą być różne.