Package google.research.optimization.v1.mathopt

Chỉ mục

BasisProto

Đặc tính tổ hợp để tìm lời giải cho chương trình tuyến tính.

Phương pháp đơn giản để giải các chương trình tuyến tính luôn trả về một "giải pháp khả thi cơ bản" có thể được mô tả kết hợp bằng cơ sở. Cơ sở sẽ chỉ định BasisStatusProto cho mọi quy tắc ràng buộc biến và tuyến tính.

Ví dụ: hãy xem xét một LP dạng chuẩn: min c * x s.t. A * x = b x >= 0 có nhiều biến hơn so với hạn chế và có thứ hạng hàng đầy đủ là A.

Gọi n là số biến và m số giới hạn tuyến tính. Cơ sở hợp lệ cho vấn đề này có thể được xây dựng như sau: * Tất cả ràng buộc sẽ có trạng thái cơ sở FIXED. * Chọn m biến sao cho các cột A là độc lập tuyến tính và gán trạng thái cơ bản. * Chỉ định trạng thái AT_LEFT cho các biến n – m còn lại.

Nghiệm cơ bản cho cơ sở này là nghiệm duy nhất của A * x = b có tất cả các biến có trạng thái AT_LEFT cố định vào giới hạn dưới của chúng (tất cả đều bằng 0). Giải pháp thu được được gọi là giải pháp khả thi cơ bản nếu nó cũng thoả mãn x >= 0.

Trường
constraint_status

SparseBasisStatusVector

Trạng thái cơ sở của quy tắc ràng buộc.

Yêu cầu: * binding_status.ids bằng LinearConstraints.ids.
variable_status

SparseBasisStatusVector

Trạng thái cơ sở của biến.

Yêu cầu: * scope_status.ids bằng VariablesProto.ids.
basic_dual_feasibility

SolutionStatusProto

Đây là một tính năng nâng cao mà MathOpt sử dụng để mô tả tính khả thi của các giải pháp LP dưới mức tối ưu (các giải pháp tối ưu sẽ luôn có trạng thái SOLUTION_STATUS_FEASIBLE).

Đối với LP một mặt, giá trị này phải bằng với trạng thái khả thi của giải pháp kép đã liên kết. Đối với LP hai mặt, giá trị này có thể khác trong một số trường hợp hiếm gặp (ví dụ: các nghiệm không hoàn toàn với đơn giản nguyên tố).

Nếu bạn đang cung cấp cơ sở bắt đầu thông qua ModelSolveParametersProto.Initial_basis, giá trị này sẽ bị bỏ qua. Dữ liệu này chỉ phù hợp với cơ sở mà SolutionProto.basis trả về.

BasisStatusProto

Trạng thái của một biến/quy tắc ràng buộc trong cơ sở LP.

Enum
BASIS_STATUS_UNSPECIFIED Giá trị bảo vệ không biểu thị trạng thái nào.
BASIS_STATUS_FREE Biến/giới hạn là tự do (không có giới hạn hữu hạn).
BASIS_STATUS_AT_LOWER_BOUND Biến/ràng buộc ở giới hạn dưới (phải có giới hạn).
BASIS_STATUS_AT_UPPER_BOUND Biến/giới hạn nằm ở giới hạn trên (phải có giới hạn).
BASIS_STATUS_FIXED_VALUE Biến/quy tắc ràng buộc có giới hạn dưới và giới hạn trên có giới hạn giống hệt nhau.
BASIS_STATUS_BASIC Biến/quy tắc ràng buộc ở đây là cơ bản.

DualRayProto

Hướng cải thiện không giới hạn đối với cả hai yếu tố tối ưu hoá hoặc vấn đề, tương đương với chứng chỉ tính không khả thi ban đầu.

Ví dụ: hãy xem xét cặp chương trình tuyến tính cặp nguyên tố: (Primal) (Kép) min c * x max b * y s.t. A * x >= b s.t. y * A + r = c x >= 0 y, r >= 0. Tia kép là cặp (y, r) thoả mãn: b * y > 0 y * A + r = 0 y, r >= 0 Quan sát thấy việc cộng bội dương của (y, r) vào nghiệm khả thi kép sẽ duy trì tính khả thi kép và cải thiện mục tiêu (chứng minh kép không giới hạn). Tia kép cũng chứng minh bài toán nguyên thuỷ là không khả thi.

Trong thông báo DualRay dưới đây, y là double_values và r là discount_costs.

Trường
dual_values

SparseDoubleVectorProto

Yêu cầu: * Dual_values.ids là các phần tử của LinearConstraints.ids. * kép_values.values đều phải hữu hạn.
reduced_costs

SparseDoubleVectorProto

Yêu cầu: * discount_costs.ids là các phần tử của VariablesProto.ids. * discount_costs.values phải là giá trị hữu hạn.

DualSolutionProto

Một giải pháp cho cả vấn đề tối ưu hoá.

Ví dụ: hãy xem xét cặp chương trình tuyến tính cặp nguyên tố: (Primal) (Kép) min c * x max b * y s.t. A * x >= b s.t. y * A + r = c x >= 0 y, r >= 0. Nghiệm kép là cặp (y, r). Điều này có thể xảy ra nếu đáp ứng các điều kiện ràng buộc từ (Kép) ở trên.

Trong thông báo dưới đây, y là giá trị kép, r là chi phí giảm và b * y là giá trị mục tiêu.

Trường
dual_values

SparseDoubleVectorProto

Yêu cầu: * Dual_values.ids là các phần tử của LinearConstraints.ids. * kép_values.values đều phải hữu hạn.
reduced_costs

SparseDoubleVectorProto

Yêu cầu: * discount_costs.ids là các phần tử của VariablesProto.ids. * discount_costs.values phải là giá trị hữu hạn.
feasibility_status

SolutionStatusProto

Trạng thái khả thi của giải pháp theo trình giải quyết cơ bản.
objective_value

double

EmphasisProto

Mức độ nỗ lực được áp dụng cho một tác vụ không bắt buộc trong khi giải (xem SolveParametersProto để sử dụng).

Điểm nhấn được dùng để định cấu hình tính năng trình giải như sau: * Nếu một trình giải toán không hỗ trợ tính năng này, thì chỉ UNSPECIFIED sẽ luôn hợp lệ, mọi chế độ cài đặt khác thường sẽ có lỗi đối số không hợp lệ (một số trình giải toán cũng có thể chấp nhận TẮT). * Nếu trình giải toán hỗ trợ tính năng: – Khi bạn đặt thành UNSPECIFIED, giá trị mặc định cơ bản sẽ được dùng. – Khi không thể tắt tính năng này, trạng thái TẮT sẽ trả về lỗi. – Nếu tính năng này được bật theo mặc định thì chế độ mặc định của trình giải thường được ánh xạ tới TRUNG BÌNH. – Nếu tính năng này được hỗ trợ, các hàm LOW, TRUNG BÌNH, HIGH và VERY HIGH sẽ không bao giờ hiển thị lỗi và sẽ được đánh dấu dựa trên kết quả phù hợp nhất.

Enum
EMPHASIS_UNSPECIFIED
EMPHASIS_OFF
EMPHASIS_LOW
EMPHASIS_MEDIUM
EMPHASIS_HIGH
EMPHASIS_VERY_HIGH

FeasibilityStatusProto

Trạng thái khả thi của vấn đề theo tuyên bố của trình giải quyết (không yêu cầu người giải quyết trả lại chứng chỉ cho yêu cầu xác nhận quyền sở hữu).

Enum
FEASIBILITY_STATUS_UNSPECIFIED Giá trị bảo vệ không biểu thị trạng thái nào.
FEASIBILITY_STATUS_UNDETERMINED Trình giải quyết không xác nhận trạng thái.
FEASIBILITY_STATUS_FEASIBLE Solver tuyên bố vấn đề này có thể thực hiện được.
FEASIBILITY_STATUS_INFEASIBLE Solver tuyên bố sự cố này không khả thi.

IndicatorConstraintProto

Dữ liệu biểu thị một điều kiện ràng buộc chỉ báo có dạng: Variable(indicator_id) = (activate_on_zero ? 0 : 1) ⇒ giới hạn dưới <= biểu thức <= giới hạn trên.

Nếu một biến liên quan đến quy tắc ràng buộc này (chỉ báo hoặc xuất hiện trong expression) bị xoá, thì biến đó sẽ được coi là được đặt thành 0. Cụ thể, việc xoá biến chỉ báo có nghĩa là giới hạn chỉ báo sẽ trống nếu activate_on_zero là false và tương đương với điều kiện ràng buộc tuyến tính nếu activate_on_zero là true.

Trường
activate_on_zero

bool

Nếu đúng, thì nếu biến chỉ báo nhận giá trị 0, thì ràng buộc ngụ ý phải giữ nguyên. Ngược lại, nếu biến chỉ báo nhận giá trị 1, thì ràng buộc ngụ ý phải giữ.
expression

SparseDoubleVectorProto

Phải là một biểu thức tuyến tính hợp lệ đối với mô hình chứa: * Tất cả các điều kiện đã nêu trên SparseDoubleVectorProto, * Tất cả các phần tử của expression.values phải hữu hạn, * expression.ids là một tập con của VariablesProto.ids.
lower_bound

double

Phải có giá trị bằng [-inf, inf); không được là NaN.
upper_bound

double

Phải có giá trị trong (-inf, inf]; không được là NaN.
name

string

Thông báo gốc có thể có yêu cầu về tính riêng biệt trong trường này. Ví dụ: xem ModelProto.indicator_constraints và IndicatorConstraintUpdatesProto.new_constraints.
indicator_id

int64

Mã nhận dạng tương ứng với một biến nhị phân hoặc chưa được đặt. Nếu bạn không đặt chính sách này, thì điều kiện ràng buộc đối với chỉ báo sẽ bị bỏ qua. Nếu đặt giá trị, chúng ta yêu cầu: * VariablesProto.integers[indicator_id] = true, * VariablesProto.lower_bounds[indicator_id] >= 0, * VariablesProto.upper_bounds[indicator_id] <= 1. MathOpt không xác thực các điều kiện này, nhưng nếu bạn không thoả mãn điều kiện này, trình giải toán sẽ trả về lỗi khi giải.

LPAlgorithmProto

Chọn một thuật toán để giải các chương trình tuyến tính.

Enum
LP_ALGORITHM_UNSPECIFIED
LP_ALGORITHM_PRIMAL_SIMPLEX Phương thức đơn giản (nguyên bản). Thường có thể đưa ra nghiệm nguyên thuỷ và nghiệm kép, tia nguyên tố/kép đối với các bài toán nguyên thuỷ/kép không giới hạn và cơ sở.
LP_ALGORITHM_DUAL_SIMPLEX Phương thức đơn giản kép. Thường có thể đưa ra nghiệm nguyên thuỷ và nghiệm kép, tia nguyên tố/kép đối với các bài toán nguyên thuỷ/kép không giới hạn và cơ sở.
LP_ALGORITHM_BARRIER Phương pháp chắn, còn thường được gọi là phương pháp điểm bên trong (IPM). Thường có thể đưa ra cả dung dịch nguyên tố và dung dịch kép. Một số phương pháp triển khai cũng có thể tạo ra tia trên các vấn đề không ràng buộc/không khả thi. Cơ sở không được đưa ra trừ phi trình giải quyết cơ bản thực hiện "chuyển đổi" và kết thúc bằng đơn giản.
LP_ALGORITHM_FIRST_ORDER Một thuật toán dựa trên phương thức bậc nhất. Những giải pháp này thường sẽ tạo ra cả giải pháp ban đầu và giải pháp kép, cũng như có thể cũng có cả chứng chỉ không khả thi nguyên gốc và/hoặc giải pháp kép. Phương thức bậc nhất thường sẽ cung cấp giải pháp với độ chính xác thấp hơn. Vì vậy, người dùng nên chú ý đặt thông số chất lượng của giải pháp (ví dụ: dung sai) và xác thực giải pháp.

LimitProto

Khi một Solve() ngừng sớm bằng TermReasonProto FEASIBLE hoặc NO_SOLUTION_FOUND, thì đây là giới hạn cụ thể đã đạt đến.

Enum
LIMIT_UNSPECIFIED Được sử dụng làm giá trị rỗng khi chúng tôi chấm dứt không phải trong một giới hạn (ví dụ: termINATION_REASON_OPTIMAL).
LIMIT_UNDETERMINED Trình giải toán cơ bản không cho biết giới hạn đã đạt đến.
LIMIT_ITERATION Một thuật toán lặp lại đã dừng sau khi tiến hành số lần lặp tối đa (ví dụ: vòng lặp đơn giản hoặc rào cản).
LIMIT_TIME Thuật toán đã dừng sau thời gian tính toán do người dùng chỉ định.
LIMIT_NODE Thuật toán nhánh và giới hạn đã dừng vì thuật toán này đã khám phá số lượng nút tối đa trong cây nhánh và giới hạn.
LIMIT_SOLUTION Thuật toán đã ngừng hoạt động vì tìm thấy số lượng giải pháp cần thiết. Tính năng này thường được dùng trong MIP để yêu cầu trình giải toán trả về giải pháp khả thi đầu tiên mà hệ thống gặp phải.
LIMIT_MEMORY Thuật toán đã ngừng hoạt động vì hết bộ nhớ.
LIMIT_CUTOFF Trình giải toán đã chạy với điểm hạn chế (ví dụ: đã đặt SolveParameters.cutoff_limit) trên mục tiêu, cho biết rằng người dùng không muốn có bất kỳ giải pháp nào tệ hơn điểm cắt và trình giải giải kết luận là không có giải pháp nào ít nhất bằng điểm cắt. Thường thì Google sẽ không cung cấp thêm thông tin về giải pháp.
LIMIT_OBJECTIVE Thuật toán đã ngừng hoạt động vì đã tìm thấy một giải pháp hoặc một giới hạn tốt hơn giới hạn do người dùng đặt (xem SolveParameters.objective_limit và SolveParameters.best_bound_limit).
LIMIT_NORM Thuật toán đã ngừng hoạt động vì tiêu chuẩn của một vòng lặp trở nên quá lớn.
LIMIT_INTERRUPTED Thuật toán đã dừng lại do tín hiệu gián đoạn hoặc yêu cầu làm gián đoạn của người dùng.
LIMIT_SLOW_PROGRESS Thuật toán đã ngừng hoạt động vì không thể tiếp tục cải tiến giải pháp.
LIMIT_OTHER

Thuật toán đã ngừng hoạt động do một giới hạn không được đề cập ở trên. Lưu ý rằng LIMIT_UNDEtermINED được sử dụng khi không thể xác định lý do và LIMIT_OTHER được sử dụng khi đã biết lý do nhưng không phù hợp với bất kỳ phương án thay thế nào ở trên.

Chấm dứt Proto.detail có thể chứa thông tin bổ sung về giới hạn.

LinearConstraintsProto

Như được sử dụng dưới đây, chúng tôi xác định "#linearConstraint" = kích thước(LinearConstraintsProto.ids).

Trường
ids[]

int64

Phải là số không âm và tăng dần. Không thể dùng giá trị max(int64).
lower_bounds[]

double

Phải có độ dài bằng #giới hạn tuyến tính, các giá trị tính bằng [-inf, inf).
upper_bounds[]

double

Phải có độ dài bằng #giới hạn tuyến tính, các giá trị trong (-inf, inf].
names[]

string

Nếu bạn không đặt chính sách này, giá trị được giả định là tất cả các chuỗi trống. Nếu không, đoạn mã phải có độ dài bằng #hàm ràng buộc tuyến tính.

Tất cả tên không trống phải khác biệt.

LinearExpressionProto

Biểu diễn thưa của một biểu thức tuyến tính (tổng các biến có trọng số cộng với độ lệch không đổi).

Trường
ids[]

int64

Mã của biến. Phải được sắp xếp (theo thứ tự tăng dần) với tất cả các phần tử riêng biệt.
coefficients[]

double

Phải có độ dài bằng mã nhận dạng. Giá trị không được hữu hạn và không được là NaN.
offset

double

Phải hữu hạn và không thể là NaN.

ModelProto

Vấn đề về tối ưu hoá. MathOpt hỗ trợ: – Biến quyết định liên tục và số nguyên với các giới hạn hữu hạn không bắt buộc. – Mục tiêu tuyến tính và mục tiêu bậc hai (một hoặc nhiều mục tiêu), giảm thiểu hoặc tối đa. - Một số loại ràng buộc, bao gồm: * Các ràng buộc tuyến tính * Các ràng buộc bậc hai * Các ràng buộc về nón bậc hai * Các ràng buộc logic > Các ràng buộc SOS1 và SOS2 > Các ràng buộc của chỉ báo

Theo mặc định, các điều kiện ràng buộc được thể hiện trong bản đồ "mã nhận dạng với dữ liệu". Tuy nhiên, chúng ta biểu diễn các ràng buộc tuyến tính ở định dạng "cấu trúc mảng" hiệu quả hơn.

Trường
name

string
variables

VariablesProto
objective

ObjectiveProto

Mục tiêu chính của mô hình.
auxiliary_objectives

map<int64, ObjectiveProto>

Các mục tiêu phụ trợ để sử dụng trong mô hình đa mục tiêu.

Mã khoá ánh xạ phải nằm trong giá trị [0, max(int64)). Mỗi mức độ ưu tiên và mỗi tên không được để trống phải là duy nhất và cũng khác biệt với objective chính.
linear_constraints

LinearConstraintsProto
linear_constraint_matrix

SparseDoubleMatrixProto

Các hệ số biến cho các điều kiện ràng buộc tuyến tính.

Nếu một biến liên quan đến quy tắc ràng buộc này bị xoá, thì biến đó sẽ được coi như được đặt thành 0.

Yêu cầu: * Linear_boundt_trix.row_ids là các phần tử củaLinear_Constraintts.ids. * Linear_Constraintt_trix.column_ids là các phần tử của biến.ids. * Các mục nhập ma trận chưa được chỉ định bằng 0. * tất cả các giá trị tuyến tính__tr_ăng_ đều phải hữu hạn.
quadratic_constraints

map<int64, QuadraticConstraintProto>

Các ràng buộc bậc hai trong mô hình.
second_order_cone_constraints

map<int64, SecondOrderConeConstraintProto>

Các quy tắc ràng buộc của nón bậc hai trong mô hình.
sos1_constraints

map<int64, SosConstraintProto>

Các điều kiện ràng buộc của SOS1 trong mô hình, ràng buộc rằng tối đa một expression có thể khác 0. Các mục nhập weights không bắt buộc là thông tin chi tiết triển khai mà trình giải quyết sử dụng để (hy vọng) hội tụ nhanh hơn. Cụ thể hơn, trình giải quyết có thể (hoặc không) sử dụng các trọng số này để chọn các quyết định phân nhánh tạo ra các nút con "cân bằng".
sos2_constraints

map<int64, SosConstraintProto>

Các điều kiện ràng buộc của SOS2 trong mô hình này ràng buộc rằng tối đa hai mục nhập của expression có thể khác 0 và phải ở cạnh nhau theo thứ tự tương ứng. Nếu không có weights nào được cung cấp, thì thứ tự này sẽ là thứ tự tuyến tính của chúng trong danh sách expressions; nếu weights được hiển thị, thứ tự sẽ được thực hiện so với các giá trị này theo thứ tự tăng dần.
indicator_constraints

map<int64, IndicatorConstraintProto>

Các quy tắc ràng buộc về chỉ báo trong mô hình sẽ thực thi điều đó nếu đặt một "biến chỉ báo" nhị phân thành 1, thì "quy tắc ràng buộc ngụ ý" phải giữ nguyên.

ModelSolveParametersProto

Trường
variable_values_filter

SparseVectorFilterProto

Bộ lọc được áp dụng cho tất cả các vùng chứa thưa được trả về được khoá bởi các biến trong PrimalSolutionProto và PrimalRayProto (PrimalSolutionProto.variable_values, PrimalRayProto.variable_values).

Yêu cầu: * filter_ids là các phần tử của VariablesProto.ids.
dual_values_filter

SparseVectorFilterProto

Bộ lọc được áp dụng cho tất cả các vùng chứa thưa được trả về được khoá bởi các điều kiện ràng buộc tuyến tính trong DualSolutionProto và DualRay (DualSolutionProto.dual_values, DualRay.dual_values).

Yêu cầu: * filter_id là các phần tử của LinearConstraints.ids.
reduced_costs_filter

SparseVectorFilterProto

Bộ lọc được áp dụng cho tất cả các vùng chứa thưa được trả về được khoá theo các biến trong DualSolutionProto và DualRay (DualSolutionProto.reduced_costs, DualRay.reduced_costs).

Yêu cầu: * filter_ids là các phần tử của VariablesProto.ids.
initial_basis

BasisProto

Cơ sở ban đầu không bắt buộc cho trình phân giải LP đơn giản khởi động ấm. Nếu được đặt, giá trị này dự kiến sẽ hợp lệ theo ValidateBasis trong validators/solution_validator.h cho ModelSummary hiện tại.
solution_hints[]

SolutionHintProto

Gợi ý giải pháp không bắt buộc. Nếu trình giải cơ bản chỉ chấp nhận một gợi ý, thì gợi ý đầu tiên sẽ được sử dụng.
branching_priorities

SparseInt32VectorProto

Mức độ ưu tiên phân nhánh không bắt buộc. Các biến có giá trị cao hơn sẽ được phân nhánh trước. Các biến không đặt mức độ ưu tiên sẽ nhận được mức độ ưu tiên mặc định của trình giải (thường là 0).

Yêu cầu: * sourceing_preferred.values phải là giá trị hữu hạn. * Branching_Priority.ids phải là các phần tử của VariablesProto.ids.

ObjectiveBoundsProto

Giới hạn giá trị mục tiêu tối ưu.

Trường
primal_bound

double

Trình giải toán tuyên bố giá trị tối ưu bằng hoặc tốt hơn (nhỏ hơn để thu gọn và lớn hơn để tối đa hoá) so với giới hạn nguyên thuỷ tối đa với dung sai khả thi ban đầu của các bộ giải (xem cảnh báo dưới đây): * Prial_bound là không đáng kể (+inf để tối đa hoá và tối đa hoá -inf) khi trình giải toán không tuyên bố là có giới hạn như vậy. * Prial_bound có thể gần với giá trị tối ưu hơn mục tiêu của giải pháp khả thi gốc tốt nhất. Cụ thể, native_bound có thể không quan trọng ngay cả khi không có giải pháp khả thi nguyên gốc nào được trả về. Cảnh báo: Tuyên bố chính xác là có một nghiệm nguyên gốc: * khả thi về mặt số học (tức là khả thi theo khả năng chấp nhận của trình giải) và * có giá trị mục tiêu Prial_bound. Giải pháp khả thi về mặt số lượng này có thể hơi không khả thi, trong trường hợp đó Prial_bound có thể tốt hơn giá trị tối ưu. Việc chuyển đổi dung sai khả thi nguyên gốc thành dung sai trên Prial_bound là không nhỏ, đặc biệt khi dung sai khả thi tương đối lớn (ví dụ: khi giải quyết bằng PDLP).
dual_bound

double

Trình giải toán tuyên bố giá trị tối ưu bằng hoặc kém hơn (lớn hơn để giảm tối đa và nhỏ hơn để tối đa hoá) so với giới hạn kép lên đến dung sai khả thi kép của trình giải (xem cảnh báo bên dưới): * giới hạn kép là không đáng kể (-inf để thu nhỏ và tối đa hoá +inf) khi trình giải toán không tuyên bố giới hạn như vậy. Tương tự như Prial_bound, điều này có thể xảy ra với một số trình giải toán ngay cả khi trả về giá trị tối ưu. Trình giải quyết MIP thường sẽ báo cáo ràng buộc ngay cả khi thông tin đó không chính xác. * đối với các bài toán liên tục giới hạn kép có thể gần với giá trị tối ưu hơn so với mục tiêu của giải pháp khả thi kép tốt nhất. Đối với MIP, một trong những giá trị không quan trọng đầu tiên của giới hạn kép thường là giá trị tối ưu của việc nới lỏng LP của MIP. * giới hạn_kép nên tốt hơn (nhỏ hơn để giảm thiểu tối đa và lớn hơn để tối đa hoá) so với giới hạn_nguyên thuỷ cho đến dung sai của trình giải (xem cảnh báo dưới đây). Cảnh báo: * Đối với các bài toán liên tục, tuyên bố chính xác là có một giải pháp kép: * khả thi về mặt số học (tức là khả thi tuỳ thuộc vào khả năng giải quyết của bài toán) và * có giá trị mục tiêu kép. Giải pháp khả thi về mặt số lượng này có thể không khả thi một chút, trong trường hợp double_bound có thể sẽ tệ hơn so với giá trị tối ưu và Prial_bound. Tương tự như trường hợp ban đầu, việc chuyển đổi dung sai khả thi kép thành dung sai trên ràng buộc kép là không hề nhỏ, đặc biệt khi dung sai khả thi tương đối lớn. Tuy nhiên, một số trình giải toán cung cấp một phiên bản chính xác của double_bound an toàn hơn về mặt số học. Bạn có thể truy cập vào phiên bản đã sửa lỗi này thông qua kết quả cụ thể của trình giải toán (ví dụ: PDlp_output.convergence_information.corrected_dual_objective) * Đối với các trình giải MIP, giới hạn kép có thể được liên kết với một giải pháp kép để giải quyết một số trường hợp thư giãn liên tục (ví dụ: thư giãn LP). Tuy nhiên, đây thường là hệ quả phức tạp của quá trình thực thi các trình giải quyết và thường không chính xác hơn các giới hạn mà các trình giải LP báo cáo.

ObjectiveProto

Trường
maximize

bool

false là giảm thiểu, true là tối đa hóa
offset

double

Phải hữu hạn và không phải NaN.
linear_coefficients

SparseDoubleVectorProto

Thuật ngữ ObjectiveProto tuyến tính trong các biến quyết định.

Yêu cầu: * Linear_coperformances.ids là các phần tử của VariablesProto.ids. * VariablesProto không được chỉ định tương ứng với 0. * hệ số tuyến tính.giá trị tuyến tính phải là hữu hạn. * hệ số tuyến tính.values có thể bằng 0, nhưng việc này chỉ lãng phí không gian.
quadratic_coefficients

SparseDoubleMatrixProto

Cụm từ khách quan mang tính bậc hai trong các biến quyết định.

Các yêu cầu ngoài những yêu cầu đối với thông báo SparseDoubleMatrixProto: * Mỗi phần tử của quadratic_co {7/}s.row_ids và mỗi phần tử của quadratic_co {7/}s.column_ids phải là một thành phần của VariablesProto.ids. * Ma trận phải là hình tam giác trên: với mỗi i, hệ số bậc hai.row_ids[i] <= quadratic_co {7/}s.column_ids[i].

Lưu ý: * Các thuật ngữ không được lưu trữ rõ ràng có hệ số bằng 0. * Các phần tử của hệ số bậc hai.Hệ số có thể bằng 0, nhưng việc này chỉ lãng phí không gian.
name

string

Các thông báo gốc có thể có yêu cầu về tính riêng biệt trong trường này; ví dụ: xem ModelProto.objectives và AuxiliaryObjectivesUpdatesProto.new_objectives.
priority

int64

Đối với các bài toán đa mục tiêu, mức độ ưu tiên của mục tiêu này so với các mục tiêu khác (càng thấp thì càng quan trọng). Giá trị này không được là số âm. Hơn nữa, mỗi mức độ ưu tiên của mục tiêu trong mô hình phải khác biệt tại thời điểm giải quyết. Điều kiện này không được xác thực ở cấp proto, vì vậy, các mô hình có thể tạm thời có các mục tiêu có cùng mức độ ưu tiên.

PrimalRayProto

Hướng cải thiện không giới hạn của bài toán tối ưu hoá; tương đương với chứng chỉ không khả thi cho bài toán kép của bài toán tối ưu hoá.

Ví dụ: xem xét một chương trình tuyến tính đơn giản: min c * x s.t. A * x >= b x >= 0 Tia nguyên thuỷ là một x thoả mãn: c * x < 0 A * x >= 0 x >= 0 Tia nguyên tố cũng chứng minh vấn đề tối ưu hoá kép là không khả thi.

Trong thông báo PrimalRay dưới đây, biến_values là x.

Trường
variable_values

SparseDoubleVectorProto

Yêu cầu: * Variable_values.ids là các phần tử của VariablesProto.ids. * tất cả biến_values.values phải là giá trị hữu hạn.

PrimalSolutionProto

Giải pháp cho một vấn đề tối ưu hoá.

Ví dụ: hãy xem xét một chương trình tuyến tính đơn giản: min c * x s.t. A * x >= b x >= 0. Nghiệm nguyên sơ là gán các giá trị cho x. Điều này có thể xảy ra nếu nó thỏa mãn A * x >= b và x >= 0 từ trên xuống. Trong thông báo PrimalSolutionProto dưới đây, các giá trị biến là x và giá trị mục tiêu là c * x.

Trường
variable_values

SparseDoubleVectorProto

Yêu cầu: * Variable_values.ids là các phần tử của VariablesProto.ids. * tất cả biến_values.values phải là giá trị hữu hạn.
objective_value

double

Giá trị mục tiêu do trình giải toán cơ bản tính toán. Không được là vô hạn hoặc NaN.
auxiliary_objective_values

map<int64, double>

Các giá trị mục tiêu phụ do trình giải toán cơ bản tính toán. Khoá phải là mã mục tiêu phụ hợp lệ. Giá trị không được là vô hạn hoặc NaN.
feasibility_status

SolutionStatusProto

Trạng thái khả thi của giải pháp theo trình giải quyết cơ bản.

ProblemStatusProto

Trạng thái khả thi của vấn đề nguyên gốc và vấn đề kép của vấn đề này (hoặc kép của một quá trình thư giãn liên tục) theo tuyên bố của người giải quyết. Trình giải quyết không bắt buộc phải trả lại chứng chỉ cho tuyên bố (ví dụ: trình giải quyết có thể tuyên bố về tính khả thi ban đầu mà không trả về một giải pháp khả thi ban đầu). Trạng thái kết hợp này cung cấp thông tin mô tả toàn diện về tuyên bố của người giải về tính khả thi và tính không ràng buộc của bài toán đã giải. Ví dụ:

  • trạng thái khả thi cho bài toán nguyên hàm và bài toán kép chỉ ra điều kiện sơ cấp khả thi và bị giới hạn và có thể có giải pháp tối ưu (đảm bảo cho bài toán không có ràng buộc phi tuyến tính).
  • một khả năng khả thi nguyên gốc và trạng thái không khả thi kép cho thấy vấn đề nguyên thuỷ là không có giới hạn (tức là có các giải pháp tốt tuỳ ý).

Lưu ý rằng trạng thái không khả thi kép (tức là đi kèm với trạng thái nguyên gốc chưa được xác định) không ngụ ý vấn đề nguyên gốc không bị ràng buộc vì chúng ta có thể khiến cả hai vấn đề đều không khả thi. Ngoài ra, mặc dù trạng thái khả thi ban đầu và trạng thái khả thi kép có thể ngụ ý sự tồn tại của một giải pháp tối ưu nhưng điều này không đảm bảo rằng trình giải toán thực sự tìm thấy giải pháp tối ưu đó.

Trường
primal_status

FeasibilityStatusProto

Trạng thái của sự cố ban đầu.
dual_status

FeasibilityStatusProto

Trạng thái của bài toán kép (hoặc bài toán kép khi thư giãn liên tục).
primal_or_dual_infeasible

bool

Nếu đúng, trình giải toán tuyên bố bài toán nguyên gốc hoặc bài toán kép là không khả thi, nhưng không biết bài toán nào (hoặc cả hai có khả thi hay không). Chỉ có thể đúng khi Prial_problem_status = Dual_problem_status = kUndefined. Thông tin bổ sung này thường cần thiết khi quá trình xử lý trước xác định không có giải pháp tối ưu cho vấn đề (nhưng không thể xác định liệu vấn đề là do tính không khả thi, không bị ràng buộc hay cả hai).

QuadraticConstraintProto

Một ràng buộc bậc hai có dạng: lb <= sum{linear_terms} + sum{quadratic_terms} <= ub.

Nếu một biến liên quan đến quy tắc ràng buộc này bị xoá, thì biến đó sẽ được coi như được đặt thành 0.

Trường
linear_terms

SparseDoubleVectorProto

Những thuật ngữ tuyến tính trong các biến quyết định.

Ngoài các yêu cầu về thông báo SparseDoubleVectorProto, chúng tôi yêu cầu: * Linear_terms.ids là các phần tử của VariablesProto.ids. * tất cả giá trị tuyến tính điều kiện tuyến tính phải là hữu hạn và không phải giá trị NaN.

Lưu ý: * Các mã biến bị bỏ qua có hệ số tương ứng bằng 0. * Linear_terms.values có thể bằng 0, nhưng việc này chỉ lãng phí không gian.
quadratic_terms

SparseDoubleMatrixProto

Những thuật ngữ bậc hai trong các biến quyết định.

Ngoài các yêu cầu đối với thông báo SparseDoubleMatrixProto, chúng tôi yêu cầu: * Mỗi phần tử của quadratic_terms.row_ids và mỗi phần tử của quadratic_terms.column_ids phải là một phần tử của VariablesProto.ids. * Ma trận phải là hình tam giác trên: đối với mỗi i, điều kiện bậc hai.row_ids[i] <= quadratic_terms.column_ids[i].

Lưu ý: * Các thuật ngữ không được lưu trữ rõ ràng có hệ số bằng 0. * Các phần tử của quadratic_terms.cohệ số có thể bằng 0, nhưng việc này chỉ gây lãng phí không gian.
lower_bound

double

Phải có giá trị tính bằng [-inf, inf) và nhỏ hơn hoặc bằng upper_bound.
upper_bound

double

Phải có giá trị bằng (-inf, inf] và lớn hơn hoặc bằng lower_bound.
name

string

Thông báo mẹ có thể có các yêu cầu về tính riêng biệt trên trường này; ví dụ: xem ModelProto.quadratic_Constraintts và QuadraticConstraintUpdatesProto.new_constraints.

SecondOrderConeConstraintProto

Một ràng buộc về hình nón bậc hai của dạng:

|arguments_to_norm||_2 <= upper_bound,

trong đó upper_bound và mỗi phần tử của arguments_to_norm là biểu thức tuyến tính.

Nếu một biến liên quan đến quy tắc ràng buộc này bị xoá, thì biến đó sẽ được coi như được đặt thành 0.

Trường
upper_bound

LinearExpressionProto
arguments_to_norm[]

LinearExpressionProto
name

string

Thông báo gốc có thể có yêu cầu về tính riêng biệt trong trường này. Ví dụ: xem ModelProto.second_order_cone_constraints và SecondOrderConeConstraintUpdatesProto.new_constraints.

SolutionHintProto

Một giải pháp bắt đầu được đề xuất cho trình giải toán.

Các trình phân giải MIP thường chỉ cần thông tin nguyên gốc (variable_values), trong khi trình giải LP cần cả thông tin nguyên gốc và thông tin kép (dual_values).

Nhiều trình phân giải MIP có thể xử lý được: (1) giải pháp từng phần không nêu rõ tất cả các biến hoặc (2) giải pháp không khả thi. Trong những trường hợp này, trình giải quyết thường giải quyết một MIP phụ để hoàn tất/sửa gợi ý.

Cách người giải quyết sử dụng gợi ý (nếu có) phụ thuộc nhiều vào cách giải, dạng bài toán và thuật toán được sử dụng. Cách đáng tin cậy nhất để đảm bảo gợi ý có hiệu quả là đọc nhật ký của trình giải cơ bản có và không có gợi ý.

Các trình giải LP dạng đơn giản thường ưu tiên cơ sở ban đầu là gợi ý giải pháp (nếu không thì họ cần chuyển đổi gợi ý để chuyển đổi gợi ý thành một giải pháp cơ bản khả thi).

Trường
variable_values

SparseDoubleVectorProto

Có thể chỉ định một phần các giá trị cho biến nguyên gốc của bài toán. Các yêu cầu độc lập với trình giải quyết cho thông báo phụ này là: * variable_values.ids là các phần tử của VariablesProto.ids. * tất cả biến_values.values phải là giá trị hữu hạn.
dual_values

SparseDoubleVectorProto

Chỉ định (có thể là một phần) giá trị cho giới hạn tuyến tính của bài toán.

Yêu cầu: * double_values.ids là các phần tử của LinearConstraintsProto.ids. * kép_values.values đều phải hữu hạn.

SolutionProto

Những nội dung trong giải pháp sẽ tuỳ thuộc vào loại vấn đề và cách giải quyết. Một mẫu hình phổ biến hiện nay là 1. Trình phân giải MIP chỉ trả về giải pháp nguyên thuỷ. 2. Các trình giải LP đơn giản thường trả về cơ sở và nghiệm nguyên tố và nghiệm kép liên quan đến cơ sở này. 3. Các phép giải liên tục khác thường trả về một nghiệm nguyên thuỷ và nghiệm kép. Các nghiệm này kết nối với nhau dưới dạng phụ thuộc vào trình giải.

Yêu cầu: * phải đặt ít nhất một trường; không được để trống một giải pháp.

Trường
primal_solution

PrimalSolutionProto
dual_solution

DualSolutionProto
basis

BasisProto

SolutionStatusProto

Tính khả thi của một nghiệm nguyên thuỷ hoặc giải pháp kép theo tuyên bố của người giải toán.

Enum
SOLUTION_STATUS_UNSPECIFIED Giá trị bảo vệ không biểu thị trạng thái nào.
SOLUTION_STATUS_UNDETERMINED Trình giải quyết không xác nhận trạng thái khả thi.
SOLUTION_STATUS_FEASIBLE Solver tuyên bố giải pháp này khả thi.
SOLUTION_STATUS_INFEASIBLE Solver tuyên bố giải pháp này không khả thi.

SolveParametersProto

Các tham số để kiểm soát một giải pháp duy nhất.

Chứa cả hai tham số chung cho tất cả các trình giải toán (ví dụ: giới hạn thời gian) và tham số cho một trình giải toán cụ thể, ví dụ: gscip. Nếu một giá trị được đặt trong cả trường phổ biến và trường cụ thể của trình giải, thì chế độ cài đặt cụ thể của trình giải sẽ được sử dụng.

Các tham số phổ biến không bắt buộc và không được đặt hoặc một giá trị enum không chỉ định giá trị sẽ cho biết trình giải toán đang được sử dụng theo giá trị mặc định.

Các tham số cụ thể của Solver cho các trình giải toán không phải là tham số đang được sử dụng sẽ bị bỏ qua.

Các tham số phụ thuộc vào mô hình (ví dụ: mức độ ưu tiên phân nhánh được đặt cho mỗi biến) được chuyển vào ModelSolveParametersProto.

Trường
time_limit

Duration

Thời gian tối đa mà người giải toán cần dành cho bài toán (hoặc vô hạn nếu chưa đặt).

Giá trị này không phải là giới hạn cố định, thời gian giải quyết có thể vượt quá giá trị này một chút. Tham số này luôn được truyền đến trình giải toán cơ bản, chứ không sử dụng trình giải toán mặc định.
enable_output

bool

Cho phép in dấu vết triển khai trình giải quyết. Vị trí của những dấu vết đó phụ thuộc vào trình giải quyết. Đối với SCIP và Gurobi, đây sẽ là các luồng đầu ra tiêu chuẩn. Đối với Glop và CP-SAT, thao tác này sẽ LOG(INFO).

Xin lưu ý rằng nếu trình giải quyết hỗ trợ lệnh gọi lại tin nhắn và người dùng đăng ký lệnh gọi lại cho hàm đó, thì giá trị tham số này sẽ bị bỏ qua và không có dấu vết nào được in.
lp_algorithm

LPAlgorithmProto

Thuật toán để giải chương trình tuyến tính. Nếu là LP_ALGORITHM_UNSPECIFIED, hãy sử dụng thuật toán mặc định của trình giải toán.

Đối với những bài toán không phải là chương trình tuyến tính nhưng trong đó việc lập trình tuyến tính là một chương trình con, thì trình giải toán có thể sử dụng giá trị này. Ví dụ: Trình giải quyết MIP thường chỉ dùng cách này cho quá trình giải LP gốc (và nếu không thì sử dụng đơn giản kép).
presolve

EmphasisProto

Cố gắng đơn giản hoá bài toán trước khi bắt đầu thuật toán chính hoặc mức nỗ lực mặc định của trình giải toán nếu {/7}_UNSPECIFIED.
cuts

EmphasisProto

Nỗ lực để tăng mức nới lỏng LP mạnh hơn (chỉ dành cho MIP) hoặc mức nỗ lực mặc định của trình giải nếu {7}_UNSPECIFIED.

LƯU Ý: việc tắt tính năng cắt giảm có thể ngăn lệnh gọi lại có cơ hội thêm đoạn cắt tại MIP_node. Đây là hành vi riêng của một trình giải quyết.
heuristics

EmphasisProto

Nỗ lực tìm ra các giải pháp khả thi ngoài những giải pháp gặp phải trong quy trình tìm kiếm hoàn chỉnh (chỉ dành cho MIP) hoặc mức nỗ lực mặc định của trình giải nếu kênh_UNSPECIFIED.
scaling

EmphasisProto

Nỗ lực thay đổi kích thước bài toán để cải thiện độ ổn định số hoặc mức nỗ lực mặc định của trình giải nếu {7}_UNSPECIFIED.
iteration_limit

int64

Giới hạn số lần lặp lại của thuật toán cơ bản (ví dụ: các trục đơn giản). Hành vi cụ thể phụ thuộc vào trình giải toán và thuật toán được sử dụng, nhưng thường có thể đưa ra giới hạn giải quyết theo thuật toán (có thể cần cấu hình thêm, ví dụ như một luồng).

Thường được trình giải quyết LP, QP và MIP hỗ trợ, nhưng đối với các trình phân giải MIP, hãy xem thêm nút_limit.
node_limit

int64

Giới hạn số lượng bài toán phụ được giải trong phương thức tìm kiếm liệt kê (ví dụ: nhánh và ràng buộc). Đối với nhiều trình giải toán, bạn có thể dùng tính năng này để giới hạn việc tính toán một cách quyết định (có thể cần cấu hình hơn nữa, ví dụ như một luồng).

Thông thường, đối với các trình phân giải MIP, hãy xem thêm bộ lặp_limit.
cutoff_limit

double

Trình giải toán sẽ dừng sớm nếu có thể chứng minh được không có nghiệm nguyên tố nào ít nhất là tốt bằng điểm cắt.

Khi ngừng hoạt động sớm, trình giải quyết sẽ trả về lý do chấm dứt NO_SOLUTION_FOUND và có giới hạn CUTOFF, đồng thời không cần phải cung cấp thêm thông tin về giải pháp. Không ảnh hưởng đến giá trị trả về nếu không có điểm dừng sớm.

Bạn nên sử dụng dung sai nếu muốn trả về các giải pháp có mục tiêu chính xác bằng ngưỡng cắt.

Hãy xem hướng dẫn sử dụng để biết thêm thông tin chi tiết và so sánh với Best_bound_limit.
objective_limit

double

Trình giải quyết sẽ dừng sớm ngay khi tìm thấy giải pháp tối thiểu là phù hợp, với lý do kết thúc CÓ THỂ và giới hạn MỤC TIÊU.
best_bound_limit

double

Trình giải toán sẽ dừng sớm ngay khi chứng minh được ràng buộc tốt nhất ít nhất là phù hợp, với lý do chấm dứt là FEASIBLE hoặc NO_SOLUTION_FOUND và giới hạn Objective.

Xem hướng dẫn sử dụng để biết thêm thông tin chi tiết và so sánh với giới hạn mức cắt.
solution_limit

int32

Trình giải quyết sẽ ngừng sớm sau khi tìm thấy nhiều giải pháp khả thi này, với lý do chấm dứt là CÓ THỂ và giới hạn GIẢI PHÁP. Phải lớn hơn 0 nếu được đặt. Phương pháp này thường được dùng để yêu cầu trình giải quyết dừng lại ở giải pháp khả thi đầu tiên tìm được. Lưu ý rằng không có đảm bảo về giá trị mục tiêu cho bất kỳ nghiệm nào được trả về.

Trình giải toán thường sẽ không trả về nhiều giải pháp hơn giới hạn giải pháp, nhưng điều này không được MathOpt thực thi, hãy xem thêm b/214041169.

Hiện được hỗ trợ cho Gurobi và SCIP, đồng thời chỉ hỗ trợ CP-SAT với giá trị 1.
threads

int32

Nếu được đặt, giá trị này phải lớn hơn 1.
random_seed

int32

Nội dung gốc cho trình tạo số giả ngẫu nhiên trong trình giải toán cơ bản. Lưu ý rằng tất cả trình giải đều sử dụng số giả ngẫu nhiên để chọn những yếu tố như nhiễu loạn trong thuật toán LP, cho các quy tắc phân tách và để sửa lỗi suy nghiệm. Việc thay đổi cách này có thể tác động đáng kể đến hành vi của trình giải toán.

Mặc dù tất cả trình giải toán đều có khái niệm hạt giống, nhưng hãy lưu ý rằng các giá trị hợp lệ phụ thuộc vào cách giải thực tế. - Gurobi: [0:GRB_MAXINT] (kể từ Gurobi 9.0 là 2x10^9). - GSCIP: [0:2147483647] (là MAX_INT hoặc kint32max hoặc 2^31-1). - GLOP: [0:2147483647] (tương tự như trên) Trong mọi trường hợp, trình giải quyết sẽ nhận được một giá trị bằng: MAX(0, MIN(MAX_VALID_VALUE_FOR_SOLVER, random_seed)).
absolute_gap_tolerance

double

Dung sai tối ưu tuyệt đối (chủ yếu) cho trình giải MIP.

GAP tuyệt đối là giá trị tuyệt đối của hiệu số giữa: * giá trị mục tiêu của giải pháp khả thi nhất tìm được, * giới hạn kép do cụm từ tìm kiếm tạo ra. Trình giải quyết có thể dừng lại khi GAP tuyệt đối có dung sai_khoảng cách tuyệt đối tối đa (khi đặt) và trả về giá trị termINATION_REASON_OPTIMAL.

Phải lớn hơn 0 nếu đặt.

Ngoài ra, hãy xem thêm parameter_gap_Vay.
relative_gap_tolerance

double

Dung sai tối ưu tương đối (chủ yếu) cho trình phân giải MIP.

GAP tương đối là phiên bản chuẩn hoá của GAP tuyệt đối (được xác định theo tỷ lệ_khoảng_không_ tuyệt đối), trong đó việc chuẩn hoá phụ thuộc vào trình giải, ví dụ: GAP tuyệt đối chia cho giá trị mục tiêu của giải pháp khả thi tốt nhất đã tìm thấy.

Trình giải quyết có thể dừng lại sau khi GAP tương đối đạt tối đa tương đối_khoảng_Dung_dốc_(khi đã đặt) và trả về giá trị termINATION_REASON_OPTIMAL.

Phải lớn hơn 0 nếu đặt.

Ngoài ra, hãy xem thêm thuộc tính ngăn_giãn_ô_lực_tuyệt_đối.
solution_pool_size

int32

Duy trì tối đa solution_pool_size giải pháp trong khi tìm kiếm. Nhóm giải pháp thường có hai chức năng: (1) Đối với những trình giải toán có thể trả về nhiều đáp án, nhóm giải pháp này giới hạn số lượng đáp án sẽ được trả về. (2) Một số trình giải có thể chạy phương pháp phỏng đoán bằng cách sử dụng các giải pháp trong nhóm giải pháp. Vì vậy, việc thay đổi giá trị này có thể ảnh hưởng đến đường dẫn của thuật toán. Để buộc trình giải toán lấp đầy nhóm giải pháp, chẳng hạn như để tìm ra n cách giải phù hợp nhất, bạn phải có thêm cấu hình cụ thể cho trình giải toán.

SolveResultProto

Hợp đồng về thời điểm dung dịch nguyên thuỷ/giải pháp kép/tia sáng phức tạp, hãy truy cập vào join_reasons.md để biết nội dung mô tả đầy đủ.

Cho đến khi ký kết một hợp đồng chính xác, cách an toàn nhất là chỉ cần kiểm tra xem có giải pháp/tia UV hay không thay vì dựa vào lý do chấm dứt.

Trường
termination

TerminationProto

Nguyên nhân khiến trình giải toán dừng hoạt động.
solutions[]

SolutionProto

Hợp đồng chung về thứ tự các giải pháp mà những người giải quyết trong tương lai nên triển khai là sắp xếp theo: 1. Các giải pháp có giải pháp khả thi sơ cấp, được sắp xếp theo mục tiêu sơ cấp tốt nhất trước tiên. 2. Các giải pháp có giải pháp khả thi kép, được sắp xếp theo mục tiêu kép tốt nhất (mục tiêu kép chưa xác định là mục tiêu kém nhất) 3. Bạn có thể trả về tất cả dung dịch còn lại theo thứ tự bất kỳ.
primal_rays[]

PrimalRayProto

Hướng dẫn cải thiện nguyên gốc không giới hạn hoặc tương đương với chứng chỉ không khả thi kép. Thường được cung cấp cho ExpirationReasonProtos UNBOUNDED và DUAL_INFEASIBLE
dual_rays[]

DualRayProto

Hướng dẫn về cải tiến kép không ràng buộc hoặc chứng chỉ không khả thi nguyên gốc tương đương. Thường được cung cấp cho termReasonProto INFEASIBLE.
solve_stats

SolveStatsProto

Số liệu thống kê về quy trình giải quyết, ví dụ: thời gian chạy, số lần lặp lại.

SolveStatsProto

Trường
solve_time

Duration

Thời gian của đồng hồ treo tường đã trôi qua được tính bằngMath_opt, xấp xỉ thời gian trong Solver::Solve(). Lưu ý: điều này không bao gồm công việc hoàn tất xây dựng mô hình.
problem_status

ProblemStatusProto

Trạng thái khả thi cho bài toán nguyên gốc và bài toán kép.
simplex_iterations

int64
barrier_iterations

int64
first_order_iterations

int64
node_count

int64

SolverTypeProto

Các trình giải toán mà MathOpt hỗ trợ.

Enum
SOLVER_TYPE_UNSPECIFIED
SOLVER_TYPE_GSCIP

Trình giải quyết chương trình số nguyên ràng buộc (SCIP) (bên thứ ba).

Hỗ trợ các bài toán LP, MIP và số nguyên không lồi. Tuy nhiên, hệ thống không trả về dữ liệu kép cho LP. Ưu tiên GLOP cho LP.
SOLVER_TYPE_GUROBI

Trình giải Gurobi (bên thứ ba).

Hỗ trợ các bài toán LP, MIP và số nguyên không lồi. Nhìn chung là lựa chọn nhanh nhất nhưng có giấy phép đặc biệt.
SOLVER_TYPE_GLOP

Trình phân giải Gốm màn hình của Google.

Hỗ trợ LP với phương thức đơn giản và nguyên gốc.
SOLVER_TYPE_CP_SAT

Trình giải CP-SAT của Google.

Hỗ trợ các sự cố trong đó tất cả các biến đều là số nguyên và bị giới hạn (hoặc được ngụ ý sau khi giải quyết). Hỗ trợ thử nghiệm để thay đổi kích thước và làm rõ vấn đề bằng các biến liên tục.
SOLVER_TYPE_PDLP

Trình giải quyết vấn đề Ngăn chặn mất dữ liệu (PDLP) của Google.

Hỗ trợ mục tiêu bậc hai LP và đường chéo lồi. Sử dụng phương thức bậc nhất thay vì đơn giản. Có thể giải quyết những vấn đề rất lớn.
SOLVER_TYPE_GLPK

Bộ công cụ lập trình tuyến tính GNU (GLPK) (bên thứ ba).

Hỗ trợ MIP và LP.

An toàn cho luồng: GLPK sử dụng bộ nhớ cục bộ cho luồng để phân bổ bộ nhớ. Do đó, phải huỷ các thực thể Solver trên cùng một luồng khi chúng được tạo, nếu không GLPK sẽ gặp sự cố. Có vẻ như bạn có thể gọi Solver::Solve() từ một luồng khác ngoài luồng được sử dụng để tạo Solver nhưng GLPK không ghi lại được và bạn nên tránh.

Khi giải một LP bằng bộ tiền giải, một giải pháp (và các tia không liên kết) chỉ được trả lại nếu đã tìm được giải pháp tối ưu. Nếu không, sẽ không có kết quả nào được trả về. Xem glpk-5.0/doc/glpk.pdf trang #40 có sẵn từ glpk-5.0.tar.gz để biết chi tiết.
SOLVER_TYPE_OSQP

Trình giải toán Chương trình phân chia toán tử (OSQP) (bên thứ ba).

Hỗ trợ các bài toán liên tục có điều kiện ràng buộc tuyến tính và mục tiêu bậc hai lồi hoặc tuyến tính. Sử dụng phương thức bậc nhất.
SOLVER_TYPE_ECOS

Embedded Conic Solver (ECOS) (bên thứ ba).

Hỗ trợ các vấn đề LP và SOCP. Sử dụng các phương pháp điểm bên trong (hàng rào).
SOLVER_TYPE_SCS

The Splitting Conic Solver (SCS) (bên thứ ba).

Hỗ trợ các vấn đề LP và SOCP. Sử dụng phương thức bậc nhất.
SOLVER_TYPE_HIGHS

HiGHS Solver (bên thứ ba).

Hỗ trợ các vấn đề về LP và MIP (chưa triển khai các QP lồi).
SOLVER_TYPE_SANTORINI

Cách triển khai tham chiếu trình giải MIP của MathOpt.

Chậm/không nên dùng cho quá trình sản xuất. Không phải là trình giải LP (không trả về thông tin kép).

SosConstraintProto

Dữ liệu để biểu thị một quy tắc ràng buộc SOS1 hoặc SOS2.

Nếu một biến liên quan đến quy tắc ràng buộc này bị xoá, thì biến đó sẽ được coi như được đặt thành 0.

Trường
expressions[]

LinearExpressionProto

Các biểu thức để áp dụng quy tắc ràng buộc SOS: * SOS1: Tối đa một phần tử nhận giá trị khác 0. * SOS2: Tối đa là hai phần tử nhận các giá trị khác 0 và các phần tử đó phải nằm liền kề theo thứ tự lặp lại.
weights[]

double

Để trống hoặc có độ dài bằng biểu thức. Nếu trống, trọng số mặc định là 1, 2, ... Nếu có, các mục phải là duy nhất.
name

string

Thông báo mẹ có thể có các yêu cầu về tính riêng biệt trên trường này; ví dụ: xem ModelProto.sos1_constraints và SosConstraintUpdatesProto.new_constraints.

SparseBasisStatusVector

Biểu diễn thưa một vectơ của các trạng thái cơ sở.

Trường
ids[]

int64

Phải được sắp xếp (theo thứ tự tăng dần) với tất cả các phần tử riêng biệt.
values[]

BasisStatusProto

Phải có độ dài bằng mã nhận dạng.

SparseDoubleMatrixProto

Biểu diễn thưa của một ma trận nhân đôi.

Ma trận được lưu trữ dưới dạng bộ ba mã nhận dạng hàng, mã cột và hệ số. Ba vectơ này phải có độ dài bằng nhau. Đối với tất cả giá trị i, bộ dữ liệu (row_ids[i], column_ids[i]) phải khác biệt. Các mục phải theo thứ tự hàng chính.

Trường
row_ids[]

int64
column_ids[]

int64
coefficients[]

double

Có thể không chứa NaN.

SparseDoubleVectorProto

Biểu diễn thưa của một vectơ nhân đôi.

Trường
ids[]

int64

Phải được sắp xếp (theo thứ tự tăng dần) với tất cả các phần tử riêng biệt.
values[]

double

Phải có độ dài bằng mã nhận dạng. Có thể không chứa NaN.

SparseInt32VectorProto

Biểu diễn thưa của một vectơ int.

Trường
ids[]

int64

Phải được sắp xếp (theo thứ tự tăng dần) với tất cả các phần tử riêng biệt.
values[]

int32

Phải có độ dài bằng mã nhận dạng.

SparseVectorFilterProto

Thông báo này cho phép truy vấn/đặt các phần cụ thể của SparseXxxxVector. Hành vi mặc định là không lọc bỏ bất cứ thứ gì. Một cách sử dụng phổ biến là chỉ truy vấn các phần của nghiệm (chỉ các giá trị khác 0 và/hoặc chỉ truy vấn một tập hợp các giá trị biến được chọn thủ công).

Trường
skip_zero_values

bool

Đối với SparseBoolVectorProto, "zero" là false.
filter_by_ids

bool

Khi đúng, chỉ trả về các giá trị tương ứng với các mã được liệt kê trong filter_ids.
filtered_ids[]

int64

Danh sách mã nhận dạng cần sử dụng khi filter_by_ids là true. Phải để trống khi filter_by_ids là false. LƯU Ý: nếu giá trị này trống và filter_by_ids là true, tức là bạn đang nói rằng bạn không muốn có bất kỳ thông tin nào trong kết quả.

TerminationProto

Tất cả thông tin về lý do tại sao lệnh gọi đến Solve() bị chấm dứt.

Trường
reason

TerminationReasonProto

Thông tin bổ sung trong limit khi giá trị là TERMSINATION_REASON_FEASIBLE hoặc TERMSINATION_REASON_NO_SOLUTION_FOUND, hãy xem limit để biết thông tin chi tiết.
limit

LimitProto

là LIMIT_UNSPECIFIED, trừ phi lý do là TERMSINATION_REASON_FEASIBLE hoặc TERMSINATION_REASON_NO_SOLUTION_FOUND. Không phải tất cả trình giải quyết đều có thể xác định giới hạn dẫn đến việc chấm dứt tài khoản, LIMIT_UNDEtermINED được sử dụng khi không xác định được nguyên nhân.
detail

string

Thông tin bổ sung thường giải quyết thông tin cụ thể về việc chấm dứt.
problem_status

ProblemStatusProto

Trạng thái khả thi cho bài toán nguyên gốc và bài toán kép. Kể từ ngày 18 tháng 7 năm 2023, thư này có thể bị thiếu. Nếu thiếu, bạn có thể tìm thấy issue_status trong SolveResultProto.solve_stats.
objective_bounds

ObjectiveBoundsProto

Giới hạn giá trị mục tiêu tối ưu. Kể từ ngày 18 tháng 7 năm 2023, thư này có thể bị thiếu. Nếu bị thiếu, bạn có thể tìm thấy items_bounds.primal_bound trong SolveResultProto.solve.stats.best_primal_bounds và goal_bounds.dual_bound trong SolveResultProto.solve.stats.best_dual_bound

TerminationReasonProto

Lý do lệnh gọi đến Solve() chấm dứt.

Enum
TERMINATION_REASON_UNSPECIFIED
TERMINATION_REASON_OPTIMAL Đã tìm ra nghiệm tối ưu có thể chứng minh được (lên đến dung sai bằng số).
TERMINATION_REASON_INFEASIBLE Vấn đề sơ cấp không có giải pháp khả thi.
TERMINATION_REASON_UNBOUNDED Vấn đề nguyên gốc là khả thi và có thể tìm thấy các giải pháp tối ưu tuỳ ý dọc theo tia nguyên gốc.
TERMINATION_REASON_INFEASIBLE_OR_UNBOUNDED Vấn đề ban đầu là không khả thi hoặc không bị ràng buộc. Bạn có thể xem thêm chi tiết về trạng thái sự cố trong resolve_stats.problem_status. Lưu ý rằng trạng thái không bị ràng buộc của Gurobi có thể được ánh xạ ở đây.
TERMINATION_REASON_IMPRECISE

Sự cố đã được giải quyết theo một trong các tiêu chí ở trên (Tối ưu, Không khả thi, Không bị ràng buộc hoặc Không thể giới hạn hoặc Không thể giới hạn), nhưng ít nhất một dung sai chưa được đáp ứng. Một số giải pháp/tia ban đầu/kép đã có mặt, nhưng những giải pháp này ít khả thi hoặc (nếu vấn đề gần như đã được tối ưu) nhưng chúng có thể là khoảng cách giữa mục tiêu giải pháp tốt nhất và giới hạn mục tiêu tốt nhất.

Người dùng vẫn có thể truy vấn nghiệm nguyên thuỷ/giải pháp kép/tia và số liệu thống kê về nghiệm, nhưng họ phải chịu trách nhiệm xử lý hiện tượng sai số.
TERMINATION_REASON_FEASIBLE Trình tối ưu hoá đã đạt đến loại giới hạn nào đó và giải pháp khả thi gốc được trả về. Xem SolveResultProto.limit_detail để biết mô tả chi tiết về loại giới hạn đã đạt đến.
TERMINATION_REASON_NO_SOLUTION_FOUND Trình tối ưu hoá đã đạt đến một loại giới hạn nào đó và không tìm thấy giải pháp khả thi gốc. Xem SolveResultProto.limit_detail để biết mô tả chi tiết về loại giới hạn đã đạt đến.
TERMINATION_REASON_NUMERICAL_ERROR Thuật toán đã dừng lại vì gặp phải lỗi số không thể khôi phục. Không có thông tin về giải pháp.
TERMINATION_REASON_OTHER_ERROR Thuật toán đã ngừng hoạt động vì một lỗi không thuộc một trong các trạng thái đã xác định ở trên. Không có thông tin về giải pháp.

VariablesProto

Như được sử dụng dưới đây, chúng tôi xác định "#variables" = size(VariablesProto.ids).

Trường
ids[]

int64

Phải là số không âm và tăng dần. Không thể dùng giá trị max(int64).
lower_bounds[]

double

Phải có độ dài bằng #variables, các giá trị trong [-inf, inf).
upper_bounds[]

double

Phải có độ dài bằng #variables, các giá trị trong (-inf, inf].
integers[]

bool

Phải có độ dài bằng #variables. Giá trị là false đối với biến liên tục và true đối với biến số nguyên.
names[]

string

Nếu bạn không đặt chính sách này, giá trị được giả định là tất cả các chuỗi trống. Nếu không, phải có độ dài bằng #variables.

Tất cả tên không trống phải khác biệt.