Package google.research.optimization.v1.mathopt

Indeks

BasisProto

Karakterisasi kombinatorial untuk solusi program linear.

Metode simpleks untuk menyelesaikan program linear selalu menampilkan "solusi dasar yang layak" yang dapat dijelaskan secara kombinasi oleh Basis. Dasar menetapkan BasisStatusProto untuk setiap variabel dan batasan linear.

Misalnya, pertimbangkan bentuk standar LP: min c * x s.t. A * x = b x >= 0 yang memiliki lebih banyak variabel daripada batasan dan dengan peringkat baris penuh A.

Misalkan n adalah jumlah variabel dan m jumlah batasan linear. Dasar yang valid untuk masalah ini dapat dibuat sebagai berikut: * Semua batasan akan memiliki status dasar FIXED. * Pilih variabel m sehingga kolom A bersifat independen secara linear dan tetapkan status BASIC. * Tetapkan status AT_LOWER untuk variabel n - m yang tersisa.

Solusi dasar untuk dasar ini adalah solusi unik dari A * x = b yang memiliki semua variabel dengan status AT_LOWER tetap berada di batas bawahnya (semua nol). Solusi yang dihasilkan disebut solusi layak dasar jika juga memenuhi x >= 0.

Kolom
constraint_status

SparseBasisStatusVector

Status dasar batasan.

Persyaratan: * constraint_status.ids sama dengan LinearConstraints.ids.
variable_status

SparseBasisStatusVector

Status berbasis variabel.

Persyaratan: * constraint_status.ids sama dengan VariablesProto.ids.
basic_dual_feasibility

SolutionStatusProto

Ini adalah fitur lanjutan yang digunakan oleh MathOpt untuk mengkarakterisasi kelayakan solusi LP yang kurang optimal (solusi yang optimal akan selalu memiliki status SOLUTION_STATUS_FEASIBLE).

Untuk LP satu sisi, statusnya harus sama dengan status kelayakan solusi ganda yang terkait. Untuk LP dua sisi, hal ini mungkin berbeda dalam beberapa kasus ekstrem (misalnya penyelesaian yang tidak lengkap dengan simpleks primal).

Jika Anda memberikan dasar awal melalui ModelSolveParametersProto.initial_basis, nilai ini akan diabaikan. Data ini hanya relevan untuk dasar yang ditampilkan oleh SolutionProto.basis.

BasisStatusProto

Status variabel/batasan dalam basis LP.

Enum
BASIS_STATUS_UNSPECIFIED Nilai Guard yang tidak mewakili status.
BASIS_STATUS_FREE Variabel/batasan bebas (tidak memiliki batas yang terbatas).
BASIS_STATUS_AT_LOWER_BOUND Variabel/batasan berada pada batas bawahnya (yang harus terbatas).
BASIS_STATUS_AT_UPPER_BOUND Variabel/batasan berada di batas atasnya (yang harus terbatas).
BASIS_STATUS_FIXED_VALUE Variabel/batasan memiliki batas bawah dan atas terbatas yang identik.
BASIS_STATUS_BASIC Variabel/batasan bersifat dasar.

DualRayProto

Arah peningkatan tak terbatas pada dual dari pengoptimalan, masalah; setara dengan sertifikat ketidaklayakan utama.

Misalnya, pertimbangkan pasangan program linear pasangan ganda primal: (Primal) (Dual) min c * x maks b * y s.t. A * x >= b s.t. y * A + r = c x >= 0 y, r >= 0. Sinar ganda adalah pasangan (y, r) yang memuaskan: b * y > 0 y * A + r = 0 y, r >= 0 Amati bahwa menambahkan kelipatan positif (y, r) ke solusi layak ganda mempertahankan kelayakan ganda dan meningkatkan objektif (membuktikan ganda tidak dibatasi). Sinar ganda juga membuktikan masalah utama tidak mungkin terjadi.

Pada pesan DualRay di bawah ini, y adalah dual_values dan r adalah kurangi_costs.

Kolom
dual_values

SparseDoubleVectorProto

Persyaratan: * dual_values.ids adalah elemen LinearConstraints.ids. * dual_values.values harus berhingga.
reduced_costs

SparseDoubleVectorProto

Persyaratan: * less_costs.ids adalah elemen VariablesProto.ids. * less_costs.values harus terbatas.

DualSolutionProto

Solusi untuk masalah pengoptimalan ganda.

Misalnya, pertimbangkan pasangan program linear pasangan ganda primal: (Primal) (Dual) min c * x maks b * y s.t. A * x >= b s.t. y * A + r = c x >= 0 y, r >= 0. Solusi ganda adalah pasangan (y, r). Hal ini layak jika memenuhi batasan dari (Dual) di atas.

Pada pesan di bawah ini, y adalah dual_values, r adalah less_costs, dan b * y adalah nilai objektif.

Kolom
dual_values

SparseDoubleVectorProto

Persyaratan: * dual_values.ids adalah elemen LinearConstraints.ids. * dual_values.values harus berhingga.
reduced_costs

SparseDoubleVectorProto

Persyaratan: * less_costs.ids adalah elemen VariablesProto.ids. * less_costs.values harus terbatas.
feasibility_status

SolutionStatusProto

Status kelayakan solusi sesuai dengan pemecah masalah yang mendasarinya.
objective_value

double

EmphasisProto

Tingkat upaya yang diterapkan pada tugas opsional saat memecahkan (lihat SolveParametersProto untuk digunakan).

Penekanan digunakan untuk mengonfigurasi fitur pemecah sebagai berikut: * Jika pemecah masalah tidak mendukung fitur tersebut, hanya UNSPECIFIED yang akan selalu valid, setelan lainnya biasanya akan menjadi error argumen yang tidak valid (beberapa pemecah masalah juga dapat menerima NONAKTIF). * Jika resolver mendukung fitur: - Jika disetel ke UNSPECIFIED, default dasar akan digunakan. - Bila fitur tidak dapat dinonaktifkan, NONAKTIF akan menampilkan pesan error. - Jika fitur ini diaktifkan secara default, solusi default pemecah biasanya akan dipetakan ke MEDIUM. - Jika fitur tersebut didukung, LOW, MEDIUM, TINGGI, dan SANGAT TINGGI tidak akan pernah memberikan error, dan akan dipetakan ke hasil yang paling cocok.

Enum
EMPHASIS_UNSPECIFIED
EMPHASIS_OFF
EMPHASIS_LOW
EMPHASIS_MEDIUM
EMPHASIS_HIGH
EMPHASIS_VERY_HIGH

FeasibilityStatusProto

Status kelayakan masalah seperti yang diklaim oleh pemecah masalah (pemecah masalah tidak diwajibkan untuk mengembalikan sertifikat klaim).

Enum
FEASIBILITY_STATUS_UNSPECIFIED Nilai Guard yang tidak mewakili status.
FEASIBILITY_STATUS_UNDETERMINED Pemecah soal tidak mengklaim status.
FEASIBILITY_STATUS_FEASIBLE Pemecah soal mengklaim bahwa masalah tersebut layak.
FEASIBILITY_STATUS_INFEASIBLE Pemecah soal mengklaim bahwa masalah itu tidak mungkin dilakukan.

IndicatorConstraintProto

Data untuk mewakili batasan indikator tunggal dalam bentuk: Variable(indicator_id) = (activate_on_zero ? 0 : 1) Mendorong batas_bawah <= ekspresi <= batas_atas.

Jika variabel yang terlibat dalam batasan ini (baik indikator maupun yang muncul di expression) dihapus, variabel tersebut akan diperlakukan seolah-olah disetel ke nol. Secara khusus, menghapus variabel indikator berarti bahwa batasan indikator akan hampa jika activate_on_zero bernilai salah (false), dan bahwa batasan tersebut setara dengan batasan linear jika activate_on_zero bernilai benar (true).

Kolom
activate_on_zero

bool

Jika benar, maka jika variabel indikator mengambil nilai 0, batasan tersirat harus menampungnya. Sebaliknya, jika variabel indikator mengambil nilai 1, maka batasan tersirat harus dipertahankan.
expression

SparseDoubleVectorProto

Harus berupa ekspresi linear yang valid terkait model yang memuatnya: * Semua kondisi yang dinyatakan di SparseDoubleVectorProto, * Semua elemen expression.values harus berhingga, * expression.ids adalah subset dari VariablesProto.ids.
lower_bound

double

Harus memiliki nilai di [-inf, inf); tidak boleh NaN.
upper_bound

double

Harus memiliki nilai di (-inf, inf]; tidak boleh NaN.
name

string

Pesan induk mungkin memiliki persyaratan keunikan di kolom ini; misalnya, lihat ModelProto.indicator_constraints dan IndicatorConstraintUpdatesProto.new_constraints.
indicator_id

int64

ID yang sesuai dengan variabel biner, atau tidak ditetapkan. Jika tidak disetel, batasan indikator akan diabaikan. Jika ditetapkan, kita mengharuskan: * VariablesProto.integers[indicator_id] = true, * VariablesProto.lower_bounds[indicator_id] >= 0, * VariablesProto.upper_bounds[indicator_id] <= 1. Kondisi ini tidak divalidasi oleh MathOpt, tetapi jika tidak terpenuhi, pemecah soal akan menampilkan error saat menyelesaikan soal.

LPAlgorithmProto

Memilih algoritma untuk menyelesaikan program linear.

Enum
LP_ALGORITHM_UNSPECIFIED
LP_ALGORITHM_PRIMAL_SIMPLEX Metode simplex (primal). Biasanya dapat memberikan solusi primal dan ganda, sinar primal/ganda pada soal primal/dual tak terbatas, dan suatu basis.
LP_ALGORITHM_DUAL_SIMPLEX Metode simpleks ganda. Biasanya dapat memberikan solusi primal dan ganda, sinar primal/ganda pada soal primal/dual tak terbatas, dan suatu basis.
LP_ALGORITHM_BARRIER Metode penghalang, juga biasa disebut metode titik interior (IPM). Biasanya dapat memberikan solusi primal dan ganda. Beberapa implementasi juga dapat menghasilkan sinar pada masalah yang tidak terbatas/tidak layak. Dasar tidak diberikan kecuali pemecah masalah yang mendasarinya melakukan "crossover" dan diselesaikan dengan simplex.
LP_ALGORITHM_FIRST_ORDER Algoritma yang didasarkan pada metode urutan pertama. Ini biasanya akan menghasilkan solusi primal dan ganda, serta berpotensi juga sertifikat ketidaklayakan primal dan/atau ganda. Metode urutan pertama biasanya akan memberikan solusi dengan akurasi yang lebih rendah, sehingga pengguna harus berhati-hati dalam menetapkan parameter kualitas solusi (misalnya, toleransi) dan memvalidasi solusi.

LimitProto

Saat Solve() berhenti lebih awal dengan termReasonProto FEASIBLE atau NO_SOLUTION_FOUND, batas spesifik yang tercapai.

Enum
LIMIT_UNSPECIFIED Digunakan sebagai nilai null ketika kami menghentikan bukan dari batas (mis. TERMINATION_REASON_OPTIMAL).
LIMIT_UNDETERMINED Pemecah masalah yang mendasari tidak mengekspos batas mana yang telah tercapai.
LIMIT_ITERATION Algoritma berulang berhenti setelah melakukan jumlah maksimum iterasi (misalnya, simpleks atau iterasi penghalang).
LIMIT_TIME Algoritma berhenti setelah waktu komputasi yang ditentukan pengguna.
LIMIT_NODE Algoritma {i>bran-and-bound<i} berhenti karena telah mengeksplorasi jumlah maksimum {i>node<i} pada pohon {i>bran-and-bound<i}.
LIMIT_SOLUTION Algoritma berhenti karena menemukan jumlah solusi yang diperlukan. Hal ini sering digunakan dalam MIP agar pemecah masalah mengembalikan solusi layak pertama yang ditemuinya.
LIMIT_MEMORY Algoritma berhenti karena kehabisan memori.
LIMIT_CUTOFF Pemecah masalah dijalankan dengan batas (misalnya SolveParameters.cutoff_limit sudah ditetapkan) pada objektif, yang menunjukkan bahwa pengguna tidak menginginkan solusi yang lebih buruk daripada batasnya, dan pemecah soal menyimpulkan tidak ada solusi yang setidaknya sebagus batasnya. Biasanya tidak ada informasi solusi lebih lanjut yang diberikan.
LIMIT_OBJECTIVE Algoritma berhenti karena menemukan solusi atau batas yang lebih baik dari batas yang ditetapkan oleh pengguna (lihat SolveParameters.objective_limit dan SolveParameters.best_bound_limit).
LIMIT_NORM Algoritma berhenti karena norma iterasi menjadi terlalu besar.
LIMIT_INTERRUPTED Algoritma berhenti karena ada sinyal interupsi atau permintaan interupsi pengguna.
LIMIT_SLOW_PROGRESS Algoritma berhenti karena tidak dapat terus membuat progres menuju solusi.
LIMIT_OTHER

Algoritma berhenti karena ada batas yang tidak dicakup oleh salah satu hal di atas. Perhatikan bahwa LIMIT_UNDETERMINED digunakan ketika alasan tidak dapat ditentukan, dan LIMIT_OTHER digunakan jika alasan tersebut diketahui tetapi tidak sesuai dengan salah satu alternatif di atas.

PenghentianProto.detail mungkin berisi informasi tambahan tentang batas tersebut.

LinearConstraintsProto

Seperti yang digunakan di bawah ini, kami mendefinisikan "#linear constraints" = size(LinearConstraintsProto.ids).

Kolom
ids[]

int64

Harus tidak negatif dan meningkat secara ketat. Nilai max(int64) tidak dapat digunakan.
lower_bounds[]

double

Harus memiliki panjang yang sama dengan #linear batasan, nilai dalam [-inf, inf).
upper_bounds[]

double

Harus memiliki panjang yang sama dengan #linear batasan, nilai dalam (-inf, inf].
names[]

string

Jika tidak disetel, semua string dianggap kosong. Jika tidak, harus memiliki panjang yang sama dengan batasan #linear.

Semua nama yang tidak kosong harus berbeda.

LinearExpressionProto

Representasi renggang dari ekspresi linear (jumlah variabel yang berbobot, ditambah offset konstan).

Kolom
ids[]

int64

ID variabel. Harus disortir (dalam urutan meningkat) dengan semua elemen berbeda.
coefficients[]

double

Harus memiliki panjang yang sama dengan ID. Nilai harus terbatas tidak boleh NaN.
offset

double

Harus terbatas dan tidak boleh NaN.

ModelProto

Masalah pengoptimalan. MathOpt mendukung: - Variabel keputusan kontinu dan bilangan bulat dengan batas terbatas opsional. - Tujuan linier dan kuadrat (tujuan tunggal atau beberapa), baik diminimalkan atau dimaksimalkan. - Sejumlah jenis batasan, termasuk: * Batasan linier * Batasan kuadrat * Batasan kerucut urutan kedua * Batasan logis > Batasan SOS1 dan SOS2 > Batasan indikator

Secara default, batasan ditampilkan dalam peta "id-to-data". Namun, kami mewakili batasan linear dalam format "struct-of-array" yang lebih efisien.

Kolom
name

string
variables

VariablesProto
objective

ObjectiveProto

Tujuan utama dalam model.
auxiliary_objectives

map<int64, ObjectiveProto>

Tujuan tambahan untuk digunakan dalam model multi-tujuan.

ID kunci peta harus dalam [0, max(int64)). Setiap prioritas, dan setiap nama yang tidak kosong, harus unik dan juga berbeda dari objective utama.
linear_constraints

LinearConstraintsProto
linear_constraint_matrix

SparseDoubleMatrixProto

Koefisien variabel untuk batasan linear.

Jika variabel yang terlibat dalam batasan ini dihapus, variabel tersebut akan diperlakukan seolah-olah telah disetel ke nol.

Persyaratan: * linear_constraint_matrix.row_ids adalah elemen linear_constraints.ids. * linear_constraint_matrix.column_ids adalah elemen variables.ids. * Entri matriks yang tidak ditentukan adalah nol. * linear_constraint_matrix.values harus berhingga.
quadratic_constraints

map<int64, QuadraticConstraintProto>

Batasan kuadrat dalam model.
second_order_cone_constraints

map<int64, SecondOrderConeConstraintProto>

Batasan kerucut urutan kedua dalam model.
sos1_constraints

map<int64, SosConstraintProto>

Batasan SOS1 dalam model, yang membatasi paling banyak satu expression boleh bukan nol. Entri weights opsional adalah detail implementasi yang digunakan oleh pemecah masalah untuk (semoga) menyatu dengan lebih cepat. Secara lebih mendetail, pemecah masalah dapat (atau tidak dapat) menggunakan bobot ini untuk memilih keputusan percabangan yang menghasilkan node turunan yang "seimbang".
sos2_constraints

map<int64, SosConstraintProto>

Batasan SOS2 dalam model, yang membatasi bahwa maksimal dua entri expression tidak boleh nol, dan harus berdekatan dalam urutannya. Jika weights tidak tersedia, pengurutan ini adalah pengurutan linearnya dalam daftar expressions; jika weights ditampilkan, pengurutan akan diambil sehubungan dengan nilai ini secara bertambah.
indicator_constraints

map<int64, IndicatorConstraintProto>

Batasan indikator dalam model, yang memberlakukannya, jika "variabel indikator" biner disetel ke satu, "batasan tersirat" harus disimpan.

ModelSolveParametersProto

Kolom
variable_values_filter

SparseVectorFilterProto

Filter yang diterapkan ke semua penampung renggang yang ditampilkan dengan kunci variabel dalam PrimalSolutionProto dan PrimalRayProto (PrimalSolutionProto.variable_values, PrimalRayProto.variable_values).

Persyaratan: * filters_ids adalah elemen VariablesProto.ids.
dual_values_filter

SparseVectorFilterProto

Filter yang diterapkan ke semua penampung renggang yang ditampilkan dengan kunci batasan linear di DualSolutionProto dan DualRay (DualSolutionProto.dual_values, DualRay.dual_values).

Persyaratan: * filters_ids adalah elemen LinearConstraints.ids.
reduced_costs_filter

SparseVectorFilterProto

Filter yang diterapkan ke semua container sparse yang ditampilkan dan dikunci oleh variabel dalam DualSolutionProto dan DualRay (DualSolutionProto.reduced_costs, DualRay.Reduced_costs).

Persyaratan: * filters_ids adalah elemen VariablesProto.ids.
initial_basis

BasisProto

Dasar awal opsional untuk pemecah masalah LP simpleks mulai warm. Jika disetel, nilai ini diharapkan valid menurut ValidateBasis di validators/solution_validator.h untuk ModelSummary saat ini.
solution_hints[]

SolutionHintProto

Petunjuk solusi opsional. Jika pemecah masalah yang mendasarinya hanya menerima satu petunjuk, petunjuk pertama akan digunakan.
branching_priorities

SparseInt32VectorProto

Prioritas percabangan opsional. Variabel dengan nilai yang lebih tinggi akan memiliki cabang terlebih dahulu. Variabel yang prioritasnya tidak ditetapkan mendapatkan prioritas default pemecah (biasanya nol).

Persyaratan: * branching_priorities.values harus terbatas. * branching_priorities.ids harus menjadi elemen VariablesProto.ids.

ObjectiveBoundsProto

Batas pada nilai tujuan optimal.

Kolom
primal_bound

double

Solver mengklaim bahwa nilai optimal sama atau lebih baik (lebih kecil untuk minimalisasi dan lebih besar untuk maksimalisasi) daripada primal_bound hingga toleransi kelayakan dasar pemecah (lihat peringatan di bawah): * primal_bound kecil (+inf untuk minimalisasi dan -inf maksimalisasi) saat pemecah tidak mengklaim memiliki batasan tersebut. * primal_bound dapat lebih dekat dengan nilai optimal daripada tujuan dari solusi terbaik yang layak. Secara khusus, primal_bound mungkin tidak praktis meskipun tidak ada solusi layak primal yang ditampilkan. Peringatan: Klaim yang sesungguhnya adalah bahwa ada solusi utama yang: * layak secara numerik (yaitu layak hingga toleransi pemecah masalah), dan * memiliki nilai objektif primal_bound. Solusi yang layak secara numerik ini mungkin sedikit tidak layak, dalam hal ini primal_bound bisa benar-benar lebih baik daripada nilai yang optimal. Menerjemahkan toleransi kelayakan dasar ke toleransi pada primal_bound tidaklah mudah, terutama ketika toleransi kelayakan relatif besar (misalnya ketika dipecahkan dengan PDLP).
dual_bound

double

Solver mengklaim bahwa nilai optimal sama atau lebih buruk (lebih besar untuk minimalisasi dan lebih kecil untuk maksimalisasi) daripada dual_bound hingga toleransi kelayakan ganda (lihat peringatan di bawah): * dual_bound biasa saja (-inf untuk minimalisasi dan +inf maksimalisasi) saat pemecah masalah tidak mengklaim memiliki batasan tersebut. Demikian pula dengan primal_bound, hal ini dapat terjadi untuk beberapa pemecah masalah bahkan saat menampilkan hasil optimal. Pemecah MIP biasanya akan melaporkan batas meskipun tidak akurat. * untuk masalah berkelanjutan dual_bound bisa lebih dekat dengan nilai optimal daripada tujuan dari solusi ganda terbaik yang layak. Untuk MIP, salah satu nilai non-trivial pertama untuk dual_bound sering kali merupakan nilai relaksasi LP MIP yang optimal. * dual_bound harus lebih baik (lebih kecil untuk minimalisasi dan lebih besar untuk maksimal) daripada primal_bound hingga toleransi pemecah (lihat peringatan di bawah). Peringatan: * Untuk masalah berkelanjutan, klaim yang tepat adalah bahwa ada solusi ganda yang: * layak secara numerik (yaitu layak hingga toleransi pemecah masalah), dan * memiliki nilai objektif dual_bound. Solusi yang layak secara numerik ini mungkin sedikit tidak layak, dalam hal ini dual_bound bisa benar-benar lebih buruk daripada nilai optimal dan primal_bound. Serupa dengan kasus dasar, menerjemahkan toleransi kelayakan ganda ke toleransi pada dual_bound tidaklah mudah, khususnya ketika toleransi kelayakan relatif besar. Namun, beberapa pemecah masalah memberikan versi dual_bound yang telah dikoreksi yang secara numerik lebih aman. Versi yang dikoreksi ini dapat diakses melalui output khusus pemecah masalah (misalnya untuk PDLP, pdlp_output.convergence_information.corrected_dual_objective). * Untuk pemecah MIP, dual_bound mungkin dikaitkan dengan solusi ganda untuk beberapa relaksasi berkelanjutan (misalnya, relaksasi LP), tetapi sering kali merupakan konsekuensi kompleks dari eksekusi pemecah masalah dan biasanya lebih tidak akurat daripada batas yang dilaporkan oleh pemecah masalah LP.

ObjectiveProto

Kolom
maximize

bool

false adalah meminimalkan, true adalah memaksimalkan
offset

double

Harus terbatas dan bukan NaN.
linear_coefficients

SparseDoubleVectorProto

Istilah ObjectiveProto yang linear dalam variabel keputusan.

Persyaratan: * linear_coefficients.ids adalah elemen VariablesProto.ids. * VariablesProto yang tidak ditentukan berkaitan dengan nol. * linear_coefficients.values harus terbatas. * linear_coefficients.values bisa nol, tetapi ini hanya membuang-buang ruang.
quadratic_coefficients

SparseDoubleMatrixProto

Istilah objektif yang kuadrat dalam variabel keputusan.

Persyaratan selain yang ada pada pesan SparseDoubleMatrixProto: * Setiap elemen quadratic_coefficients.row_ids dan setiap elemen quadratic_coefficients.column_ids harus menjadi elemen VariablesProto.ids. * Matriks harus berbentuk segitiga atas: untuk setiap i, quadratic_coefficients.row_ids[i] <= quadratic_coefficients.column_ids[i].

Catatan: * Istilah yang tidak disimpan secara eksplisit memiliki koefisien nol. * Elemen quadratic_coefficients.coefficients boleh nol, tetapi ini hanya akan membuang-buang ruang.
name

string

Pesan induk mungkin memiliki persyaratan keunikan pada kolom ini; misalnya, lihat ModelProto.objectives dan AuxiliaryObjectivesUpdatesProto.new_objectives.
priority

int64

Untuk masalah multi-tujuan, prioritas tujuan ini relatif terhadap masalah lainnya (lebih rendah lebih penting). Nilai ini tidak boleh negatif. Selain itu, setiap prioritas objektif dalam model harus berbeda pada waktu penyelesaian. Kondisi ini tidak divalidasi di level proto, sehingga model mungkin untuk sementara memiliki tujuan dengan prioritas yang sama.

PrimalRayProto

Arah peningkatan tak terbatas pada masalah pengoptimalan; setara dengan sertifikat ketidaklayakan untuk masalah pengoptimalan ganda.

Contoh: amati program linier sederhana: min c * x s.t. A * x >= b x >= 0 Sinar primal adalah x yang memenuhi: c * x < 0 A * x >= 0 x >= 0 Amati bahwa jika diberikan penyelesaian yang layak, hasil kelipatan positif dari sinar primal tersebut bernilai obyektif dan bernilai lebih baik. Sinar primal juga membuktikan masalah pengoptimalan ganda tidak mungkin terjadi.

Pada pesan PrimalRay di bawah ini, variabel_values adalah x.

Kolom
variable_values

SparseDoubleVectorProto

Persyaratan: * variabel_values.ids adalah elemen VariablesProto.ids. * variabel_values.values harus berhingga.

PrimalSolutionProto

Solusi untuk masalah pengoptimalan.

Misalnya, pertimbangkan program linear sederhana: min c * x s.t. A * x >= b x >= 0. Solusi utamanya adalah nilai penetapan ke x. Sangat memungkinkan jika memenuhi A * x >= b dan x >= 0 dari contoh di atas. Pada pesan PrimalSolutionProto di bawah ini, variabel_nilai adalah x dan objektif_value adalah c * x.

Kolom
variable_values

SparseDoubleVectorProto

Persyaratan: * variabel_values.ids adalah elemen VariablesProto.ids. * variabel_values.values harus berhingga.
objective_value

double

Nilai objektif seperti yang dihitung oleh pemecah masalah yang mendasarinya. Tidak boleh tak terbatas atau NaN.
auxiliary_objective_values

map<int64, double>

Nilai objektif tambahan seperti yang dihitung oleh pemecah masalah yang mendasarinya. Kunci harus berupa ID tujuan tambahan yang valid. Nilai tidak boleh tak terbatas atau NaN.
feasibility_status

SolutionStatusProto

Status kelayakan solusi sesuai dengan pemecah masalah yang mendasarinya.

ProblemStatusProto

Status kelayakan masalah utama dan masalah ganda (atau ganda dari relaksasi berkelanjutan) seperti yang diklaim oleh pemecah masalah. Pemecah masalah tidak perlu mengembalikan sertifikat untuk klaim (misalnya, pemecah masalah dapat mengklaim kelayakan dasar tanpa mengembalikan penyelesaian layak utama). Status gabungan ini memberikan deskripsi komprehensif mengenai klaim pemecah masalah tentang kelayakan dan tidak adanya batasan dari masalah yang dipecahkan. Misalnya,

  • status layak untuk masalah primal dan ganda menunjukkan bahwa primal layak dan dibatasi dan kemungkinan memiliki solusi optimal (dijamin untuk masalah tanpa kendala non-linear).
  • status primal layak dan status ganda tidak layak menunjukkan masalah primal tidak terbatas (yaitu memiliki solusi yang baik secara arbitrer).

Perhatikan bahwa status dua ketidaklayakan itu sendiri (yaitu disertai dengan status dasar yang tidak dapat ditentukan) tidak berarti masalah primal tidak terbatas karena kedua masalah tersebut bisa jadi tidak mungkin terjadi. Selain itu, meskipun status kelayakan primal dan ganda mungkin menyiratkan adanya solusi yang optimal, hal ini tidak menjamin bahwa pemecah masalah telah benar-benar menemukan solusi optimal tersebut.

Kolom
primal_status

FeasibilityStatusProto

Status untuk masalah utama.
dual_status

FeasibilityStatusProto

Status untuk masalah ganda (atau masalah ganda dari relaksasi berkelanjutan).
primal_or_dual_infeasible

bool

Jika benar, pemecah masalah mengklaim bahwa masalah utama atau masalah ganda tidak mungkin terjadi, tetapi tidak tahu masalah yang mana (atau apakah keduanya tidak mungkin). Dapat menjadi true (benar) hanya jika primal_problem_status = dual_problem_status = kUnspecified. Informasi tambahan ini sering kali diperlukan saat pra-pemrosesan menentukan tidak ada solusi optimal untuk masalah (tetapi tidak dapat menentukan apakah masalah disebabkan oleh ketidaklayakan, ketidakterbatasan, atau keduanya).

QuadraticConstraintProto

Batasan kuadrat tunggal dalam bentuk: lb <= sum{linear_terms} + sum{quadratic_terms} <= ub.

Jika variabel yang terlibat dalam batasan ini dihapus, variabel tersebut akan diperlakukan seolah-olah telah disetel ke nol.

Kolom
linear_terms

SparseDoubleVectorProto

Istilah yang linier dalam variabel keputusan.

Selain persyaratan pada pesan SparseDoubleVectorProto, kami mengharuskan bahwa: * linear_terms.ids adalah elemen VariablesProto.ids. * linear_terms.values harus terbatas dan bukan-NaN.

Catatan: * ID variabel yang dihilangkan memiliki koefisien nol yang sesuai. * linear_terms.values bisa nol, tapi ini hanya membuang-buang ruang.
quadratic_terms

SparseDoubleMatrixProto

Istilah yang kuadrat dalam variabel keputusan.

Selain persyaratan pada pesan SparseDoubleMatrixProto, kami mengharuskan bahwa: * Setiap elemen quadratic_terms.row_ids dan setiap elemen quadratic_terms.column_ids harus menjadi elemen VariablesProto.ids. * Matriks harus berbentuk segitiga atas: untuk setiap i, quadratic_terms.row_ids[i] <= quadratic_terms.column_ids[i].

Catatan: * Istilah yang tidak disimpan secara eksplisit memiliki koefisien nol. * Elemen quadratic_terms.coefficients bisa berupa nol, tetapi ini hanya akan membuang-buang ruang.
lower_bound

double

Harus memiliki nilai dalam [-inf, inf), dan lebih kecil dari atau sama dengan upper_bound.
upper_bound

double

Harus memiliki nilai dalam (-inf, inf], dan lebih besar dari atau sama dengan lower_bound.
name

string

Pesan induk mungkin memiliki persyaratan keunikan di kolom ini; misalnya, lihat ModelProto.quadratic_constraints dan QuadraticConstraintUpdatesProto.new_constraints.

SecondOrderConeConstraintProto

Batasan kerucut urutan kedua tunggal dari bentuk:

||arguments_to_norm||_2 <= upper_bound,

dengan upper_bound dan setiap elemen arguments_to_norm adalah ekspresi linear.

Jika variabel yang terlibat dalam batasan ini dihapus, variabel tersebut akan diperlakukan seolah-olah telah disetel ke nol.

Kolom
upper_bound

LinearExpressionProto
arguments_to_norm[]

LinearExpressionProto
name

string

Pesan induk mungkin memiliki persyaratan keunikan di kolom ini; misalnya, lihat ModelProto.second_order_cone_constraints dan SecondOrderConeConstraintUpdatesProto.new_constraints.

SolutionHintProto

Solusi awal yang disarankan untuk pemecah masalah.

Pemecah MIP umumnya hanya menginginkan informasi primal (variable_values), sementara pemecah masalah LP menginginkan informasi primal dan ganda (dual_values).

Banyak pemecah MIP dapat bekerja dengan: (1) solusi parsial yang tidak menentukan semua variabel atau (2) solusi yang tidak layak. Dalam kasus ini, pemecah masalah biasanya memecahkan sub-MIP untuk melengkapi/memperbaiki petunjuk.

Cara penggunaan petunjuk oleh pemecah masalah, jika ada, sangat bergantung pada pemecah, jenis permasalahan, dan algoritma yang digunakan. Cara yang paling dapat diandalkan untuk memastikan petunjuk Anda memiliki efek adalah dengan membaca log pemecah masalah yang mendasarinya dengan dan tanpa petunjuk.

Pemecah LP berbasis {i>simplex <i}biasanya lebih memilih basis awal untuk petunjuk solusi (mereka perlu melakukan crossover untuk mengubah petunjuk menjadi solusi dasar yang layak).

Kolom
variable_values

SparseDoubleVectorProto

Kemungkinan penetapan nilai sebagian ke variabel primal masalah. Persyaratan bebas pemecah masalah untuk sub-pesan ini adalah: * variable_values.ids adalah elemen VariablesProto.ids. * variabel_values.values harus berhingga.
dual_values

SparseDoubleVectorProto

Penetapan nilai (yang kemungkinan sebagian) ke batasan linear masalah.

Persyaratan: * dual_values.ids adalah elemen LinearConstraintsProto.ids. * dual_values.values harus berhingga.

SolutionProto

Apa yang dimasukkan dalam solusi tergantung pada jenis masalah dan pemecahnya. Pola umum saat ini adalah 1. Pemecah masalah MIP hanya menampilkan solusi utama. 2. Pemecah LP {i>simplex <i}sering menampilkan suatu basis serta solusi primal dan ganda yang terkait dengan basis ini. 3. Pemecah masalah berkelanjutan lainnya sering kali memberikan solusi primal dan ganda yang terhubung dalam bentuk yang bergantung pada pemecah masalah.

Persyaratan: * minimal satu kolom harus ditetapkan; solusi tidak boleh kosong.

Kolom
primal_solution

PrimalSolutionProto
dual_solution

DualSolutionProto
basis

BasisProto

SolutionStatusProto

Kelayakan solusi primal atau ganda seperti yang diklaim oleh pemecah masalah.

Enum
SOLUTION_STATUS_UNSPECIFIED Nilai Guard yang tidak mewakili status.
SOLUTION_STATUS_UNDETERMINED Pemecah soal tidak mengklaim status kelayakan.
SOLUTION_STATUS_FEASIBLE Pemecah soal mengklaim bahwa solusi tersebut layak.
SOLUTION_STATUS_INFEASIBLE Pemecah soal mengklaim bahwa solusinya tidak mungkin.

SolveParametersProto

Parameter untuk mengontrol satu penyelesaian.

Berisi kedua parameter yang umum untuk semua pemecah masalah, misalnya time_limit, dan parameter untuk solver tertentu, misalnya gscip. Jika nilai ditetapkan di kolom umum dan khusus pemecah masalah, setelan khusus pemecah akan digunakan.

Parameter umum yang bersifat opsional dan tidak disetel atau enum dengan nilai yang tidak ditentukan menunjukkan bahwa default pemecah digunakan.

Parameter khusus pemecah untuk pemecah selain yang digunakan akan diabaikan.

Parameter yang bergantung pada model (misalnya, prioritas percabangan ditetapkan untuk setiap variabel) diteruskan di ModelSolveParametersProto.

Kolom
time_limit

Duration

Waktu maksimum yang harus dihabiskan pemecah masalah untuk soal (atau tak terbatas jika tidak ditetapkan).

Nilai ini bukan batas yang pasti, waktu penyelesaian mungkin sedikit melebihi nilai ini. Parameter ini selalu diteruskan ke pemecah yang mendasarinya, pemecah default tidak digunakan.
enable_output

bool

Memungkinkan pencetakan rekaman aktivitas implementasi pemecah. Lokasi trace tersebut bergantung pada pemecahnya. Untuk SCIP dan Gurobi, ini akan menjadi streaming output standar. Untuk Glop dan CP-SAT, ini akan LOG(INFO).

Perhatikan bahwa jika pemecah masalah mendukung callback pesan dan pengguna mendaftarkan callback untuknya, nilai parameter ini akan diabaikan dan tidak ada pelacakan yang dicetak.
lp_algorithm

LPAlgorithmProto

Algoritma untuk menyelesaikan program linear. Jika LP_ALGORITHM_UNSPECIFIED, gunakan algoritma default pemecah masalah.

Untuk soal yang bukan program linear, tetapi pemrograman linear adalah subrutin, pemecah masalah dapat menggunakan nilai ini. Misalnya, pemecah MIP biasanya akan menggunakan ini hanya untuk pemecahan LP root (dan sebaliknya menggunakan dual simplex).
presolve

EmphasisProto

Upaya menyederhanakan masalah sebelum memulai algoritma utama, atau tingkat upaya default pemecah jika solarmora_UNSPECIFIED.
cuts

EmphasisProto

Upaya untuk mendapatkan pelonggaran LP yang lebih kuat (khusus MIP), atau tingkat upaya default pemecah jika solarmora_UNSPECIFIED.

CATATAN: menonaktifkan pemotongan dapat mencegah callback memiliki kesempatan untuk menambahkan potongan di MIP_ potongan, perilaku ini adalah khusus pemecah.
heuristics

EmphasisProto

Upaya dalam menemukan solusi yang layak di luar yang ditemukan dalam prosedur penelusuran lengkap (khusus MIP), atau tingkat upaya default pemecah jika SELECTED_UNSPECIFIED.
scaling

EmphasisProto

Upaya dalam mengubah skala masalah untuk meningkatkan stabilitas numerik, atau tingkat upaya default pemecah jika solarmora_UNSPECIFIED.
iteration_limit

int64

Membatasi iterasi dari algoritma yang mendasari (misalnya pivot simplex). Perilaku spesifik bergantung pada pemecah dan algoritme yang digunakan, tetapi sering kali dapat memberikan batas penyelesaian deterministik (konfigurasi lebih lanjut mungkin diperlukan, misalnya satu thread).

Biasanya didukung oleh pemecah masalah LP, QP, dan MIP, tetapi untuk pemecah masalah MIP, lihat juga node_limit.
node_limit

int64

Membatasi jumlah subsoal yang diselesaikan dalam penelusuran enumeratif (misalnya cabang dan terikat). Bagi banyak pemecah masalah, ini dapat digunakan untuk membatasi komputasi secara deterministik (konfigurasi lebih lanjut mungkin diperlukan, misalnya satu thread).

Biasanya untuk pemecah MIP, lihat juga Iterasi_limit.
cutoff_limit

double

Pemecah masalah berhenti lebih awal jika dapat membuktikan bahwa tidak ada solusi utama yang setidaknya sebaik alternatif.

Pada perhentian awal, pemecah masalah menampilkan alasan penghentian NO_SOLUTION_FOUND dan dengan batas CUTOFF sehingga tidak diperlukan untuk memberikan informasi solusi tambahan. Tidak memengaruhi nilai yang ditampilkan jika tidak ada perhentian awal.

Sebaiknya gunakan toleransi jika Anda menginginkan solusi dengan tujuan yang sama persis dengan batas ditampilkan.

Lihat panduan pengguna untuk detail selengkapnya dan perbandingan dengan best_bound_limit.
objective_limit

double

Pemecah masalah berhenti lebih awal segera setelah menemukan solusi yang setidaknya sebagus ini, dengan alasan penghentian MUDAH dan membatasi TUJUAN.
best_bound_limit

double

Pemecah soal berhenti lebih awal segera setelah membuktikan ikatan terbaik setidaknya sebagus ini, dengan alasan penghentian FEASIBLE atau NO_SOLUTION_FOUND dan membatasi TUJUAN.

Lihat panduan pengguna untuk detail lebih lanjut dan perbandingan dengan cutoff_limit.
solution_limit

int32

Pemecah masalah berhenti lebih awal setelah menemukan sekian banyak solusi yang layak ini, dengan alasan penghentian MUDAH dan membatasi SOLUSI. Harus lebih besar dari nol jika ditetapkan. Parameter ini sering digunakan untuk menghentikan pemecah masalah pada solusi pertama yang layak ditemukan. Perhatikan bahwa tidak ada jaminan terhadap nilai objektif untuk solusi yang ditampilkan.

Solvers biasanya tidak akan mengembalikan lebih banyak solusi daripada batas solusi, tetapi ini tidak diberlakukan oleh MathOpt, lihat juga b/214041169.

Saat ini didukung untuk Gurobi dan SCIP, serta hanya untuk CP-SAT dengan nilai 1.
threads

int32

Jika ditetapkan, nilainya harus >= 1.
random_seed

int32

Seed untuk generator angka pseudo-random dalam pemecah masalah yang mendasarinya. Perhatikan bahwa semua pemecah masalah menggunakan angka pseudo-random untuk memilih hal-hal seperti gangguan dalam algoritma LP, untuk aturan tie-break-up, dan untuk perbaikan heuristik. Memvariasikan ini dapat memberikan dampak yang signifikan terhadap perilaku pemecah masalah.

Meskipun semua pemecah masalah memiliki konsep benih, perhatikan bahwa nilai yang valid bergantung pada pemecah yang sebenarnya. - Gurobi: [0:GRB_MAXINT] (yang pada Gurobi 9.0 adalah 2x10^9). - GSCIP: [0:2147483647] (yang adalah MAX_INT atau kint32max atau 2^31-1). - GLOP: [0:2147483647] (sama seperti di atas) Dalam semua kasus, pemecah akan menerima nilai yang sama dengan: MAX(0, MIN(MAX_VALID_VALUE_FOR_SOLVER, random_seed)).
absolute_gap_tolerance

double

Toleransi pengoptimalan absolut (terutama) untuk pemecah MIP.

GAP absolut adalah nilai absolut dari perbedaan antara: * nilai objektif dari solusi terbaik yang memungkinkan, * ikatan ganda yang dihasilkan oleh penelusuran. Pemecah masalah dapat berhenti setelah GAP absolut mencapai batas absolut_gap_tolerance (saat ditetapkan), dan menampilkan TERMINATION_REASON_OPTIMAL.

Harus >= 0 jika ditetapkan.

Lihat juga relative_gap_tolerance.
relative_gap_tolerance

double

Toleransi pengoptimalan relatif (terutama) untuk pemecah MIP.

GAP relatif adalah versi normalisasi dari GAP absolut (ditetapkan pada absolut_gap_tolerance), dengan normalisasi yang bergantung pada pemecah masalah, mis. GAP absolut dibagi dengan nilai objektif dari solusi terbaik yang mungkin ditemukan.

Pemecah masalah dapat berhenti setelah GAP relatif mencapai tingkat relatif_gap_tolerance (saat ditetapkan), dan mengembalikan TERMINATION_REASON_OPTIMAL.

Harus >= 0 jika ditetapkan.

Lihat juga absolut_gap_tolerance.
solution_pool_size

int32

Pertahankan hingga solution_pool_size solusi saat melakukan penelusuran. Kumpulan solusi umumnya memiliki dua fungsi: (1) Untuk pemecah masalah yang dapat mengembalikan lebih dari satu solusi, ini membatasi jumlah solusi yang akan ditampilkan. (2) Beberapa pemecah masalah dapat menjalankan heuristik menggunakan solusi dari kumpulan solusi, sehingga mengubah nilai ini dapat memengaruhi jalur algoritme. Untuk memaksa pemecah masalah mengisi kumpulan solusi, mis. dengan n solusi terbaik, memerlukan konfigurasi khusus pemecah masalah lebih lanjut.

SolveResultProto

Kontrak ketika solusi/sinar primal/ganda bersifat kompleks, lihat penghentian_reasons.md untuk deskripsi lengkap.

Hingga kontrak yang tepat diselesaikan, lebih aman untuk memeriksa apakah ada solusi/cara yang tersedia daripada mengandalkan alasan penghentian.

Kolom
termination

TerminationProto

Alasan pemecah masalah berhenti.
solutions[]

SolutionProto

Kontrak umum untuk urutan solusi yang harus diterapkan oleh pemecah masalah di masa depan adalah mengurutkan berdasarkan: 1. Solusi dengan solusi primal yang layak, diurutkan berdasarkan objektif primal terbaik terlebih dahulu. 2. Solusi dengan solusi ganda yang layak, diurutkan berdasarkan objektif ganda terbaik (tujuan ganda yang tidak diketahui adalah yang terburuk) 3. Semua solusi yang tersisa dapat ditampilkan dalam urutan apa pun.
primal_rays[]

PrimalRayProto

Petunjuk untuk peningkatan awal tanpa batas, atau yang setara dengan sertifikat ketidaklayakan ganda. Biasanya diberikan untuk PenghentianAlasanProtos UNBOUNDED dan DUAL_INFEASIBLE
dual_rays[]

DualRayProto

Petunjuk peningkatan ganda tanpa batas, atau yang setara, sertifikat ketidaklayakan dasar. Biasanya diberikan untuk PenghentianAlasanProto TIDAK DAPAT DIERUSKAN.
solve_stats

SolveStatsProto

Statistik tentang proses penyelesaian, misalnya waktu berjalan, iterasi.

SolveStatsProto

Kolom
solve_time

Duration

Waktu jam dinding berlalu seperti yang diukur oleh learn_opt, kira-kira dari waktu dalam Solver::Solve(). Catatan: ini tidak termasuk pekerjaan yang dilakukan saat membangun model.
problem_status

ProblemStatusProto

Status kelayakan untuk masalah primal dan ganda.
simplex_iterations

int64
barrier_iterations

int64
first_order_iterations

int64
node_count

int64

SolverTypeProto

Pemecah masalah yang didukung oleh MathOpt.

Enum
SOLVER_TYPE_UNSPECIFIED
SOLVER_TYPE_GSCIP

Memecahkan masalah Constraint Integer Programs (SCIP) (pihak ketiga).

Mendukung soal kuadrat bilangan bulat LP, MIP, dan non-cembung. Tidak ada data ganda untuk LP yang ditampilkan. Pilih GLOP untuk LP.
SOLVER_TYPE_GUROBI

Pemecah masalah Gurobi (pihak ketiga).

Mendukung soal kuadrat bilangan bulat LP, MIP, dan non-cembung. Umumnya merupakan opsi tercepat, tetapi memiliki lisensi khusus.
SOLVER_TYPE_GLOP

Pemecah masalah Glop Google.

Mendukung LP dengan metode simpleks primal dan ganda.
SOLVER_TYPE_CP_SAT

Solusi CP-SAT dari Google.

Mendukung masalah di mana semua variabel berupa bilangan bulat dan dibatasi (atau tersirat setelah presolve). Dukungan eksperimental untuk menskalakan ulang dan membedakan masalah dengan variabel berkelanjutan.
SOLVER_TYPE_PDLP

Pemecah PDLP Google.

Mendukung objektif kuadrat diagonal LP dan konveks. Menggunakan metode urutan pertama, bukan simpleks. Dapat memecahkan masalah yang sangat besar.
SOLVER_TYPE_GLPK

GNU Linear Programming Kit (GLPK) (pihak ketiga).

Mendukung MIP dan LP.

Thread-safety: GLPK menggunakan penyimpanan lokal thread untuk alokasi memori. Akibatnya, instance Solver harus dihancurkan di thread yang sama dengan yang dibuat. Jika tidak, GLPK akan error. Tampaknya dapat memanggil Solver::Solve() dari thread lain selain yang digunakan untuk membuat Solver, tetapi tidak didokumentasikan oleh GLPK dan harus dihindari.

Ketika memecahkan LP dengan presolver, larutan (dan sinar tidak terikat) hanya dikembalikan jika solusi optimal telah ditemukan. Selain itu, tidak ada yang ditampilkan. Lihat halaman glpk-5.0/doc/glpk.pdf #40 yang tersedia dari glpk-5.0.tar.gz untuk detailnya.
SOLVER_TYPE_OSQP

Pemecah masalah Program Kuadrat Pemisahan Operator (OSQP) (pihak ketiga).

Mendukung masalah berkelanjutan dengan batasan linear dan objektif linear atau kuadrat cembung. Menggunakan metode urutan pertama.
SOLVER_TYPE_ECOS

Embedded Conic Solver (ECOS) (pihak ketiga).

Mendukung masalah LP dan SOCP. Menggunakan metode titik interior (barrier).
SOLVER_TYPE_SCS

Splitting Conic Solver (SCS) (pihak ketiga).

Mendukung masalah LP dan SOCP. Menggunakan metode urutan pertama.
SOLVER_TYPE_HIGHS

HiGHS Solver (pihak ketiga).

Mendukung masalah LP dan MIP (QP konveks tidak diimplementasikan).
SOLVER_TYPE_SANTORINI

Implementasi referensi MathOpt untuk pemecah MIP.

Lambat/tidak direkomendasikan untuk produksi. Bukan pemecah masalah LP (tidak ada informasi ganda yang ditampilkan).

SosConstraintProto

Data untuk merepresentasikan satu batasan SOS1 atau SOS2.

Jika variabel yang terlibat dalam batasan ini dihapus, variabel tersebut akan diperlakukan seolah-olah telah disetel ke nol.

Kolom
expressions[]

LinearExpressionProto

Ekspresi yang digunakan untuk menerapkan batasan SOS: * SOS1: Maksimal satu elemen berisi nilai selain nol. * SOS2: Paling banyak dua elemen mengambil nilai bukan nol, dan elemen tersebut harus berdekatan dalam pengurutan berulang.
weights[]

double

Kosong atau sama panjangnya dengan ekspresi. Jika kosong, bobot default adalah 1, 2, ... Jika ada, entri harus unik.
name

string

Pesan induk mungkin memiliki persyaratan keunikan pada kolom ini; misalnya, lihat ModelProto.sos1_constraints dan SosConstraintUpdatesProto.new_constraints.

SparseBasisStatusVector

Representasi renggang dari vektor status dasar.

Kolom
ids[]

int64

Harus disortir (dalam urutan meningkat) dengan semua elemen berbeda.
values[]

BasisStatusProto

Harus memiliki panjang yang sama dengan ID.

SparseDoubleMatrixProto

Representasi renggang dari matriks ganda.

Matriks disimpan sebagai tiga kali lipat ID baris, ID kolom, dan koefisien. Ketiga vektor ini harus memiliki panjang yang sama. Untuk semua i, tuple (row_ids[i], column_ids[i]) harus berbeda. Entri harus dalam urutan utama baris.

Kolom
row_ids[]

int64
column_ids[]

int64
coefficients[]

double

Mungkin tidak mengandung NaN.

SparseDoubleVectorProto

Representasi renggang dari vektor ganda.

Kolom
ids[]

int64

Harus disortir (dalam urutan meningkat) dengan semua elemen berbeda.
values[]

double

Harus memiliki panjang yang sama dengan ID. Mungkin tidak mengandung NaN.

SparseInt32VectorProto

Representasi renggang dari vektor int.

Kolom
ids[]

int64

Harus diurutkan (dalam urutan meningkat) dengan semua elemen berbeda.
values[]

int32

Harus memiliki panjang yang sama dengan ID.

SparseVectorFilterProto

Pesan ini memungkinkan untuk membuat kueri/menetapkan bagian tertentu dari SparseXxxxVector. Perilaku default-nya adalah tidak memfilter apa pun. Penggunaan yang umum adalah mengkueri sebagian solusi saja (hanya nilai bukan nol, dan/atau hanya satu set nilai variabel yang dipilih sendiri).

Kolom
skip_zero_values

bool

Untuk SparseBoolVectorProto "nol" adalah false.
filter_by_ids

bool

Jika true (benar), hanya tampilkan nilai yang sesuai dengan ID yang tercantum dalam filtering_ids.
filtered_ids[]

int64

Daftar ID yang akan digunakan saat filter_by_ids bernilai benar (true). Harus kosong jika filter_by_ids bernilai salah (false). CATATAN: jika ini kosong, dan filter_by_ids benar, Anda mengatakan bahwa Anda tidak ingin informasi apa pun dalam hasil.

TerminationProto

Semua informasi mengenai alasan panggilan ke Solve() dihentikan.

Kolom
reason

TerminationReasonProto

Informasi tambahan dalam limit jika nilai TERMINATION_REASON_FEASIBLE atau TERMINATION_REASON_NO_SOLUTION_FOUND, lihat limit untuk mengetahui detailnya.
limit

LimitProto

LIMIT_UNSPECIFIED kecuali jika alasannya adalah TERMINATION_REASON_FEASIBLE atau TERMINATION_REASON_NO_SOLUTION_FOUND. Tidak semua pemecah masalah selalu dapat menentukan batas yang menyebabkan penghentian, LIMIT_UNDETERMINED digunakan ketika penyebabnya tidak dapat ditentukan.
detail

string

Informasi tambahan khusus pemecah masalah tentang penghentian.
problem_status

ProblemStatusProto

Status kelayakan untuk masalah primal dan ganda. Mulai 18 Juli 2023, pesan ini mungkin tidak akan ada. Jika tidak ada, problem_status dapat ditemukan di SolveResultProto.Solve_stats.
objective_bounds

ObjectiveBoundsProto

Batas pada nilai tujuan optimal. Mulai 18 Juli 2023, pesan ini mungkin tidak akan ada. Jika tidak ada, destination_bounds.primal_bound dapat ditemukan di SolveResultProto.Solve.stats.best_primal_bound dan goals_bounds.dual_bound dapat ditemukan di SolveResultProto.resolve.stats.best_dual_bound

TerminationReasonProto

Alasan panggilan ke Solve() dihentikan.

Enum
TERMINATION_REASON_UNSPECIFIED
TERMINATION_REASON_OPTIMAL Solusi yang optimal (hingga toleransi numerik) telah ditemukan.
TERMINATION_REASON_INFEASIBLE Masalah utama tidak memiliki solusi yang layak.
TERMINATION_REASON_UNBOUNDED Masalah primal layak dan solusi yang baik dapat ditemukan di sepanjang sinar primal.
TERMINATION_REASON_INFEASIBLE_OR_UNBOUNDED Masalah utamanya tidak layak atau tidak terbatas. Detail lebih lanjut tentang status masalah mungkin tersedia di solve_stats.problem_status. Perhatikan bahwa status tanpa batas Gurobi mungkin dipetakan di sini.
TERMINATION_REASON_IMPRECISE

Masalah ini diselesaikan pada salah satu kriteria di atas (Optimal, Ineligibility, Unbounded, atau IneligibilityOrUnbounded), tetapi satu atau beberapa toleransi tidak terpenuhi. Terdapat beberapa solusi/sinar utama/ganda, tetapi hasilnya mungkin sedikit tidak mungkin, atau (jika masalahnya hampir optimal) mungkin merupakan celah antara tujuan solusi terbaik dan batas objektif terbaik.

Pengguna masih dapat mengajukan kueri statistik solusi/sinar/solusi primal/ganda dan solusi, tetapi mereka bertanggung jawab untuk menangani ketidaktepatan numerik.
TERMINATION_REASON_FEASIBLE Pengoptimal mencapai semacam batas dan solusi primal yang layak ditampilkan. Lihat SolveResultProto.limit_detail untuk deskripsi mendetail tentang jenis batas yang telah dicapai.
TERMINATION_REASON_NO_SOLUTION_FOUND Pengoptimal mencapai semacam batas dan tidak menemukan solusi primal yang layak. Lihat SolveResultProto.limit_detail untuk deskripsi mendetail tentang jenis batas yang telah tercapai.
TERMINATION_REASON_NUMERICAL_ERROR Algoritma berhenti karena mengalami error numerik yang tidak dapat dipulihkan. Informasi solusi tidak tersedia.
TERMINATION_REASON_OTHER_ERROR Algoritma berhenti karena terjadi error yang tidak tercakup dalam salah satu status yang ditentukan di atas. Informasi solusi tidak tersedia.

VariablesProto

Seperti yang digunakan di bawah ini, kami mendefinisikan "#variables" = size(VariablesProto.ids).

Kolom
ids[]

int64

Harus tidak negatif dan meningkat secara ketat. Nilai max(int64) tidak dapat digunakan.
lower_bounds[]

double

Harus memiliki panjang yang sama dengan #variables, nilai dalam [-inf, inf).
upper_bounds[]

double

Harus memiliki panjang yang sama dengan #variables, nilai dalam (-inf, inf].
integers[]

bool

Harus memiliki panjang yang sama dengan #variable. Nilai salah untuk variabel kontinu dan benar untuk variabel bilangan bulat.
names[]

string

Jika tidak disetel, semua string dianggap kosong. Jika tidak, panjangnya harus sama dengan #variable.

Semua nama yang tidak kosong harus berbeda.