Catatan Rilis OR-Alat

Halaman ini mencantumkan perubahan pada OR-Tools, termasuk fitur baru, perbaikan bug, serta peningkatan kualitas kode dan prosedur penginstalan.

Jika Anda mengalami masalah saat menginstal OR-Tools, periksa bagian Troubleshooting di petunjuk penginstalan OR-Tools. Jika masalah Anda tidak tercantum di sana, periksa masalah di GitHub, atau jangan ragu untuk membuka masalah baru, dan kami akan dengan senang hati membantu Anda.

Berikut adalah catatan rilis untuk OR-Tools, dimulai dengan rilis terbaru.

Mei 2024

Mengumumkan rilis OR-Tools v9.10

Kami telah merilis OR-Tools v9.10. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Anda dapat menemukan catatan rilis di github

March 2024

Mengumumkan rilis OR-Tools v9.9

Kami telah merilis OR-Tools v9.9. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Anda dapat menemukan catatan rilis di github

November 2023

Mengumumkan rilis OR-Tools v9.8

Kami telah merilis OR-Tools v9.8. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Perubahan platform

  • Tambahkan Python 3.12.
  • Menambahkan dukungan untuk Ubuntu 23.10

Linear Solver

  • Port ModelBuilder ke .Net.
  • Ganti nama LogCallback menjadi MbLogCallback untuk menghindari tabrakan dengan SAT LogCallback.
  • Memperluas API ModelBuilder:
    • Menambahkan batasan indikator.
    • Menambahkan dukungan petunjuk.
    • Menambahkan cloning model.

Opt Matematika

  • Pengerjaan ulang mendalam.

Pemilihan rute

  • Menambahkan status ROUTING_OPTIMAL.
  • Jadikan RoutingModel tidak dapat disalin atau dipindahkan.
  • Memperbaiki beberapa loop tanpa henti di operator penelusuran lokal.
  • Tambahkan struct internal PickupDeliveryPosition.
  • Menambahkan metode IsPickup() dan IsDelivery().

SAT

  • Mengurangi jejak memori untuk model besar.
  • Penelusuran penjadwalan yang lebih baik.
  • tambahkan packing_precedences_lns.
  • mengoptimalkan dan memperbaiki lompatan kelayakan.
  • mengoptimalkan {i>presolve<i} linier dan pencatatan {i>presolve<i} yang lebih baik.
  • Meningkatkan presolve untuk int_abs, int_mod, int_prod, dan lin_max.
  • Meningkatkan dukungan Panda
  • Sedikit perbaikan bug.

Log Perubahan GitHub

Agustus 2023

Mengumumkan rilis OR-Tools v9.7

Kami telah merilis OR-Tools v9.7. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Perubahan platform

  • Hentikan Centos-8 (EOL).
  • Hentikan Debian 10.
  • Lepaskan Fedora [33, 36] (EOL).
  • Drop Ubuntu 18.04 LTS (EOL).
  • Drop Python 3.7 (EOL).
  • Menonaktifkan dukungan netcore3.1 di CMake (EOL).

Python Pembuat Model

  • Izinkan penggunaan deret dan kerangka data Pandas untuk membuat variabel.
  • Lengkapi informasi pengetikan

PDLP

  • berbagai pembaruan.

CP-SAT

  • Peningkatan performa. (feasibility_jump, lin_max)
  • Meningkatkan pengelolaan pemotongan
  • Pekerja destination_shave_search baru yang didedikasikan untuk meningkatkan batas bawah tujuan (saat meminimalkan)
  • Anotasi pengetikan untuk python cp_model.py
  • Dukungan parsial eksperimental untuk panda di cp_model.py
  • Pekerja berbasis pelanggaran penelusuran lokal eksperimental:
    • diaktifkan dengan parameter: num_violation_ls:xxx
    • dioptimalkan untuk model linear (linear, bool_or, bool_and, at_most_one, exactly_one)
    • berfungsi dengan benar pada lin_max, product, division
    • mendukung no_overlap, kumulatif, sirkuit, rute
    • dinonaktifkan dengan no_overlap_2d
    • jumlah pekerja ls yang direkomendasikan: num_workers -> num_violation_ls: (8, 1), (16, 2) (24, 3), (32, 4)

Log Perubahan GitHub

Maret 2023

Mengumumkan rilis OR-Tools v9.6

Kami telah merilis OR-Tools v9.6. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Perubahan platform

  • Tambahkan dukungan Fedora 37, 38.
  • Lepaskan Python 3.6 (tidak didukung oleh protobuf).
  • Jatuhkan Python 3.7 di macOS (tidak didukung oleh scipy).
  • Menambahkan dukungan net7.0 di CMake (menggunakan -DUSE_DOTNET_7=ON)
  • Lepaskan netcore3.1 di paket nuget .org

Dependensi

  • SCIP v801 -> v803 (catatan: sekarang SCIP menggunakan lisensi yang kompatibel dengan OSI)
  • abseil 20220623.1 -> 20230105.0
  • Protobuf v21.5 -> v21.12
  • ALIH 4.1.1
  • JNA Java 5.11.0 -> 5.12.1

Bazel

  • Menambahkan dukungan pybind11.
  • Menambahkan dukungan wrapper java.

Pemecah Masalah

  • PDLP: wrapper dd python.
  • CP-SAT: Peningkatan performa.
  • GLOP: Tweak presolve.
  • ModelBuilder: Python: Meningkatkan dukungan numpy.
  • Pemilihan rute: Peningkatan performa (penelusuran lokal)

Masalah Umum:

  • CP-SAT: Mengabaikan subresolver pseudo_costs akan menampilkan Parameter tidak valid (lihat #3706).

November 2022

Mengumumkan rilis OR-Tools v9.5

Kami telah merilis OR-Tools v9.5. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Perubahan platform

  • Tambahkan dukungan Debian Sid.
  • Tambahkan dukungan Fedora 35, 36.
  • Menambahkan dukungan Ubuntu 22.10.
  • Letakkan Python 3.6 di macOS.
  • Menambahkan dukungan Python 3.11.

Update Dependensi

  • Protobuf v19.4 -> v21.5.
  • Pemecah Soal SCIP v800 -> v801.

CP-SAT

  • Peningkatan presolve: max(array), batasan Boolean, batasan linear.
  • Penelusuran sisipan harus bersifat deterministik secara paralel.
  • Potongan linier: pembersihan persegi dan potongan int_prod; tulis ulang pipeline yang dipotong.
  • Model input dan solusi sidik jari (terlihat di log).
  • Peningkatan penjadwalan.
  • Sekumpulan perbaikan bug yang biasa (error selama penyelesaian, error dalam pemotongan, solusi yang tidak memungkinkan, model tidak layak di LNS).

GLOP

  • Percepat dengan menulis ulang aljabar linear, serta aturan pemilihan pivot.

Linear Solver

  • Menambahkan knapsack_interface.cc.
  • Pindahkan API model_builder ke dalam direktori linear_Solver (header dan sampel).
  • Menambahkan dukungan untuk Gurobi 10.

Pemilihan rute

  • Membebaskan beberapa parser untuk berbagai tantangan pemilihan rute.

Agustus 2022

Mengumumkan rilis OR-Tools v9.4

Kami telah merilis OR-Tools v9.4. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Platform

  • Menambahkan dukungan Debian-10 (lihat #3029).
  • Menambahkan dukungan Ubuntu 22.04 LTS (lihat #3276). catatan: tidak akan memiliki dukungan .Net 3.1 (lihat dotnet/core#7038).
  • Menghapus dukungan Ubuntu 21.10.

Lain-lain

  • Pisahkan arsip berdasarkan bahasa dan tambahkan konfigurasi CMake ke C++ (#3200).

Grafik

Bagi ortools.graph.pywrapgraph menjadi:

  • ortools.graph.python.linear_sum_assignment.
  • ortools.graph.python.max_flow.
  • ortools.graph.python.min_cost_flow.

Tindakan ini memungkinkan penggunaan numpy untuk mempercepat penyiapan masalah.

CP-SAT

Beberapa peningkatan pada:

  • penjadwalan (propagasi, potongan, batas bawah).
  • MaxSAT (heuristik berbasis inti, presolve).
  • Performa MIP (presolve, pemotongan).

Maret 2022

Mengumumkan rilis OR-Tools v9.3

Kami telah merilis OR-Tools v9.3. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Perubahan platform

  • Hentikan dukungan Debian-10.
  • Hentikan dukungan untuk Ubuntu-16.04.
  • Lepaskan .NET Framework 4.5.2.

Update Dependensi

  • Tambahkan Eigen 3.4.0.
  • Tambahkan Google re2 2021-11-01.
  • Protobuf 3.19.1 -> 3.19.4.
  • SCIP 7.0.1 -> v800.

Python

  • Tambahkan pybind11.

Fitur

  • Menambahkan PDLP sebagai eksperimental.
  • Menambahkan MathOpt sebagai eksperimental.

CP-SAT

  • Mengganti nama beberapa API agar konsisten, misalnya LinearExpr.ScalProd. -> LinearExpr.WeightedSum..
  • Menambahkan metode AddAtLeastOne/AddAtMostOne/AddExactlyOne.
  • Menambahkan AddMultiplicationConstraint(z, x, y) dalam semua bahasa.
  • Menambahkan AddMultipleCircuit() dalam semua bahasa.

C++

  • Krektor IntVar(BoolVar) eksplisit.
  • Menghapus LinearExpr::Add* dan menggantinya dengan operator, misalnya, LinearExpr +=.
  • Menambahkan operator aritmatika pada ekspresi linear.
  • Menghapus LinearExpr::BooleanSum/BooleanScalProd dan menggunakan Sum/WeightedSum.
  • Tambahkan CpModelBuilder::FixVariable() yang menimpa domain variabel ke satu nilai.

Java

  • Tulis ulang LinearExpr, tambahkan class builder tambahan: LinearExpr.newBuilder().add(x).addSum(&lt;array of variables&gt;).build().
  • Ikuti C++ API: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment, dan ForbiddenAssignment sekarang menampilkan class khusus dengan API inkremental untuk menambahkan variabel, persyaratan, permintaan baru...

C

  • Dokumentasikan semua metode.
  • Ikuti C++ API: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment, dan ForbiddenAssignment sekarang menampilkan class khusus dengan API inkremental untuk menambahkan variabel, persyaratan, permintaan baru...
  • Menambahkan class LinearExprBuilder untuk membuat ekspresi secara bertahap.

Sistem Build

CMake

  • Memerlukan setidaknya CMake >= 3.18.

Merek

  • Sekarang gunakan build berbasis CMake secara internal.

Desember 2021

Mengumumkan rilis OR-Tools v9.2

Kami telah merilis OR-Tools v9.2. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Perubahan platform

  • Menambahkan dukungan untuk Ubuntu 21:10 (rilis berkelanjutan terakhir).

Update Dependensi

  • .Net TFM update net5.0 -> net6.0 (perlu .Net SDK 6.0 LTS dan .Net SDK 3.1 LTS).
  • abseil-cpp 20210324.2 -> 20211102.0.
  • Protobuf 3.18.0 -> 3.19.1.
  • Googletest 1.10.0 -> 1.11.0.
  • Python: tambahkan numpy >= 1.13.3.
  • Di MacOS, kompilasi Coin-OR di -O1 untuk menghindari error pada runner.

Pemilihan rute

  • Peningkatan filter.
  • Meningkatkan heuristik solusi pertama.
  • Perbaiki penempatan jeda waktu.

CP-SAT

Perubahan yang dapat menyebabkan gangguan

  • Buffering protokol yang mendasarinya tidak kompatibel dengan versi sebelumnya. Setiap buffering protokol yang disimpan harus dibuat ulang dengan API builder yang diupdate (di C++, Python, Java, dan .NET)
  • Secara khusus, protobuf interval bersih saat kami menghapus kolom lama (awal, ukuran, dan akhir) dan mengganti nama kolom baru (menggunakan _view) agar menggunakan nama kolom yang dihapus.

Fitur baru

  • Batasan all_different, reservoir, modulo, multiplication, dan division menerima ekspresi affine (a * var + b) di mana pun yang diperlukan variabel bilangan bulat.
  • Objektif menerima koefisien floating point (Lihat class DoubleLinearExpr di C++/Java/.NET. Lihat contoh knapsack_2d_sat.py di Python).
  • Batasan no_overlap_2d mendukung interval opsional.
  • C++ API mengimplementasikan operator + dan * untuk membuat ekspresi.

Peningkatan

  • Kode presolve yang lebih baik.
  • Pemeriksa model yang lebih ketat.
  • Mengerjakan ulang batasan reservoir.
  • Tambahkan potongan energik untuk batasan no_overlap_2d.
  • Meningkatkan relaksasi linear batasan encoding (literal implies var == value).

Metode yang tidak digunakan lagi dan dihapus

  • Menghentikan penggunaan C++ BooleanSum dan BooleanScalProd. Cukup gunakan Sum dan ScalProd.
  • Menghapus AddLinMinEquality dan AddLinMaxEquality C++. Cukup gunakan AddMinEquality dan AddMaxEquality.

Inkompatibilitas di masa mendatang

  • Suatu saat nanti, kami akan menulis ulang lapisan pemodelan Java agar lebih dekat dengan lapisan C++.
  • Di lapisan pemodelan C++, kita akan membuat tombol IntVar(BoolVar var) eksplisit.
  • Kami mempertimbangkan untuk membuat API python sesuai dengan PEP 8 (menggunakan nama snake_case). Jika ini terjadi, kami akan memberikan file {i>sed<i} untuk mentransfer kode.

Sistem Build

Bazel

  • Memperbaiki build Windows.

CMake

  • Tambahkan opsi FETCH_PYTHON_DEPS (default ON).
  • Menambahkan dukungan opsional untuk pemecah GPLK (default -DUSE_GLPK=OFF).

Python

  • Mendukung bilangan bulat numpy di sebagian besar CP-SAT API.
  • Memperbaiki __version__ yang tidak ada.

September 2021

Mengumumkan rilis OR-Tools v9.1

Kami telah merilis OR-Tools v9.1. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Perubahan platform

  • Python: gunakan image manylinux2014 (lihat PEP 599).
  • Python: menambahkan dukungan untuk linux aarch64 menggunakan image manylinux2014_aarch64.
  • .Net: tambahkan dukungan .Net 5.0.

Update Dependensi

  • abseil-cpp 20210324.1 -> 20210324.2.
  • Protobuf 3.15.8 -> 3.18.0.
  • SCIP 7.0.1 -> master.
  • Googletest 1.8.0 -> 1.10.0.
  • python: penggunaan warning di cp_model.py (lihat #2530).
  • python: absl-py 0.11 -> 0.13.

CMake

  • Menambahkan versi minimum yang diperlukan 3.14 -> 3.15 (lihat #2528).
  • Python: tambahkan versi minimum yang diperlukan 3.14 -> 3.18 (lihat #2774).

Merek

Build berbasis make tidak digunakan lagi. Harap migrasikan ke CMake atau Bazel untuk mem-build dari sumber.

Java

  • Meningkatkan keandalan loader library native (lihat #2742).
  • Memperbaiki error JVM Garbage Collector saat model perutean atau pemecah batasan berhenti (lihat #2091) (lihat #2466).
  • Memperbaiki error callback logging CP-SAT saat menggunakan beberapa pekerja (lihat #2775).

CP-SAT

  • Meningkatkan keandalan kode LNS (lihat #2525).
  • Meningkatkan kode penjadwalan: metode factory baru untuk membuat interval ukuran tetap, heuristik penelusuran baru, presolve yang lebih baik, dan potongan linear baru.
  • Meningkatkan kode perutean: LNS khusus yang baru.
  • Meningkatkan kualitas pemeriksa model. Sekarang, metode ini lebih bertele-tele, terutama tentang potensi overflow.
  • Memperbaiki kode MIP: penyelesaian yang lebih baik dan beberapa peningkatan pada pelonggaran linear model MIP dan CP.
  • Meningkatkan keberagaman penelusuran. Saat menggunakan lebih dari 12 pekerja, tambahkan pekerja yang didedikasikan untuk meningkatkan batas bawah tujuan.
  • Ubah ke kode paralelisme: secara default, pemecah masalah kini akan menggunakan semua core yang tersedia. Gunakan num_search_parameters untuk menentukan tingkat paralelisme.
  • Menghentikan penggunaan SearchAllSolutions dan SolveWithSolutionCallback.
  • Python API: pemeriksaan yang lebih mendetail saat menggunakan var == ... atau var != ... di luar panggilan model.Add().

April 2021

Mengumumkan rilis OR-Tools v9.0

Kami telah merilis OR-Tools v9.0. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Update dependensi

Java

Perbaikan bug

  • Meningkatkan multi-threading saat menggunakan pemecah masalah CP-SAT (lihat #1588).
  • Memperbaiki dukungan wrapper Python std::vector&ltstd::string&gt (lihat #2453).
  • Mengerjakan ulang dukungan CPLEX (lihat #2470).

Perubahan yang dapat menyebabkan gangguan

  • Menambahkan akses logger di Python, Java, dan .Net (lihat #2245).
  • Penggantian semua jenis Google kustom dengan jenis yang disediakan di cstdint.

CP-SAT

  • Metode SearchForAllSolutions(), SearchAllSolutions(), dan SolveWithSolutionCallback() tidak digunakan lagi. Sebagai gantinya, gunakan Solve().
  • Meningkatkan dukungan operator standar Python. Hal ini dapat merusak kode yang ada, yang salah.

Maret 2021

Mengumumkan rilis OR-Tools v8.2

Kami telah merilis OR-Tools v8.2. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Update dependensi

  • Abseil-cpp 20200923.2 diupdate menjadi 20200923,3 LTS.
  • Protobuf 3.14.0 diupdate ke versi 3.15.3.

Pemilihan rute

  • Menambahkan RoutingModel.RegisterTransitMatrix() dan RoutingModel.RegisterUnaryTransitVector().
  • Ubah hasil RoutingModel.AddVectorDimension() dan RoutingModel.AddMatrixDimension() menjadi std::pair&ltint, bool&gt yang int-nya merupakan ID evaluator transportasi umum.

Desember 2020

Mengumumkan rilis OR-Tools v8.1

Kami telah merilis OR-Tools v8.1. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Update dependensi

  • Abseil-cpp 20200923 diupdate menjadi 20200923.2 LTS.
  • Protobuf 3.13.0 diupdate ke versi 3.14.
  • Menambahkan dukungan untuk Gurobi 9.1.0
  • Tempatkan dependensi GLog (diganti dengan implementasi kustom bergantung pada flag abseil-cpp)
  • Lepaskan dependensi GFlag (diganti dengan komponen flag abseil-cpp)

Perbaikan bug

  • Memperbaiki penghitungan ganda lisensi mengambang Gurobi (lihat #2227).
  • Memperbaiki build Windows (lihat #2200).

Oktober 2020

Mengumumkan rilis OR-Tools v8.0

Kami telah merilis OR-Tools v8.0. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Perubahan platform

  • Menambahkan dukungan untuk Python 3.9 (#2187)
  • Menghentikan dukungan untuk Python 3.5 (#2186) <!-- Menunggu dukungan dotnet-sdk Microsoft, dapat dihasilkan setelah rilis dirilis...
    • Menambahkan dukungan untuk Ubuntu 20.10 (#2188) -->
  • Penghentian dukungan untuk Ubuntu 16.04 LTS (#2188)
  • Menghentikan dukungan untuk Ubuntu 19.10 (#2188)

Update dependensi

  • Abseil-cpp 20200225.2 diupdate menjadi LTS 20200923.
  • Protobuf 3.12.2 diupdate ke versi 3.13.0.

Perubahan yang dapat menyebabkan gangguan

  • Sekarang, kode sumber Pemilihan Rute dan CP-SAT menggunakan beberapa fitur C++17. Peringatan: Jika Anda menyediakan versi abseil-cpp Anda sendiri, pastikan juga bahwa versi tersebut dibuat berdasarkan C++17.
  • Tanda tangan MPSolver::CreateSolver telah diubah. Argumen nama model telah dihapus.

CMake

  • Memperbaiki penonaktifan dukungan SCIP saat menggunakan -DUSE_SCIP=OFF (lihat #2129).
  • Integrasikan contoh dan contoh ke sistem build CMake. catatan: dapat dinonaktifkan menggunakan -DBUILD_SAMPLES=OFF dan -DBUILD_EXAMPLES=OFF. catatan: dapat dinonaktifkan untuk bahasa tertentu menggunakan -DBUILD_<LANG>_SAMPLES=OFF atau -DBUILD_<LANG>_EXAMPLES=OFF.
    • Dengan <LANG> di antara:
    • CXX,
    • PYTHON,
    • JAVA dan
    • DOTNET.

Merek

  • Memerlukan Make >= 4.3 (penggunaan fungsi evaluasi).
  • Memerlukan CMake >= 3.14 (penggunaan opsi --verbose CMake).
  • Menambahkan opsi untuk menonaktifkan dukungan SCIP menggunakan -DUSE_SCIP=OFF (lihat #2134).
  • Menambahkan opsi untuk menonaktifkan dukungan CLP dan CBC menggunakan -DUSE_COINOR=OFF.

Java

  • OR-Tools kini menghasilkan paket maven (lihat #202).

Perbaikan bug

  • Memperbaiki build C++ dan Python di FreeBSD (lihat #2126).
  • Memperbaiki build di debug di Windows (lihat #2077).
  • Memperbaiki error yang sudah lama berjalan secara paralel pada CP-SAT di Windows (lihat #2001, #2019).

Juli 2020

Mengumumkan rilis OR-Tools v7.8

Kami telah merilis OR-Tools v7.8. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Update dependensi

  • Gurobi 9.0.2 sekarang sudah terintegrasi dalam biner bawaan. Tindakan ini akan mencari library bersama gurobi 90 di jalur penginstalan default penginstal Gurobi di MAC OS X dan Windows, atau di direktori GUROBI_HOME.
  • SCIP 7.0.1 sekarang terintegrasi dalam biner bawaan. Pastikan kepatuhan terhadap lisensi SCIP sebelum menggunakannya.
  • Menambahkan dukungan untuk Xpress Solver opsional 8.9.0.

Linear Solver

  • Menambahkan metode LinearSolver::CreateSolver() statis untuk menyederhanakan pemeriksaan dukungan untuk backend pemecah masalah linear terintegrasi. Fitur ini berfungsi dalam semua bahasa.

Perbaikan bug

  • Memperbaiki build berbasis CMake di FreeBSD.
  • Memperbaiki pengurutan CP-SAT dalam pembuatan potongan kumulatif.
  • Memperbaiki kebocoran memori pemecah masalah linear di wrapper .Net.

Juni 2020

Mengumumkan rilis OR-Tools v7.7

Kami telah merilis OR-Tools v7.7. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Update dependensi

  • Abseil-cpp b832dce diupdate ke c51510d (LTS 20200225.2).
  • Protobuf 3.11.4 diupdate ke versi 3.12.2.

Fitur dan peningkatan baru

  • Pemecah CP-SAT sekarang menampilkan Optimal, bukan Feasible dalam model kepuasan (yaitu tanpa objektif).
  • Menambahkan heuristik pompa kelayakan dari komunitas MIP.

Perbaikan bug

Memperbaiki error Multi-threading CP-SAT (lihat #2005).

April 2020

Mengumumkan rilis OR-Tools v7.6

Kami telah merilis OR-Tools v7.6. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Fitur baru CP-SAT

Kami telah menambahkan fitur baru berikut ke pemecah masalah CP-SAT:

  • Peningkatan pengelolaan pesawat potong untuk piringan hitam.
  • Alat proses debug.

Update dependensi

Abseil-cpp 8ba96a8 diupdate ke b832dce (LTS 20200225).

Perbaikan bug

  • Memperbaiki bug CP-SAT UNSAT di presolve (lihat #1908).
  • URL swigwin.exe telah diperbaiki.
  • Memperbaiki pengelolaan typemap SWIG untuk Java dan .Net.

Januari 2020

Mengumumkan rilis OR-Tools v7.5

Kami telah merilis OR-Tools v7.5. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Perubahan platform

  • Menambahkan dukungan untuk Python 3.8 (#1719)
  • Menghapus kompilasi dukungan dari sumber di Visual Studio 2017 (#1852).
  • Memperbarui dukungan dari Centos 7 ke Centos 8 (#1827).

Update dependensi

Perbaikan bug

Masalah berikut telah diperbaiki di OR-Tools v7.5 (Untuk daftar lengkapnya, lihat Milestone v7.5).

Pada khususnya:

  • Memperbaiki pemuatan Assembly. Lihat #1421.
  • Mengekspos metode GetStartIndex() dan GetEndIndex() dari RouteIndexManager (#1843).
  • Memperbaiki SWIG untuk menghapus metode yang rusak (#1838, #1276).

Oktober 2019

Mengumumkan rilis OR-Tools v7.4

Kami telah merilis OR-Tools v7.4. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Fitur dan peningkatan baru

  • Pemecah CP-SAT kini memeriksa batasan yang tidak mendukung literal penegakan kebijakan. Pemeriksa model akan menampilkan error sebelum memecahkan jika batasan tersebut memiliki literal penerapan.
  • Penelusuran lokal yang lebih baik dan lebih cepat untuk library perutean.
  • Pemecah masalah linear kini mendukung software pihak ketiga Xpress-MP. Anda harus membangun ulang OR-Tools dari sumber untuk menggunakannya.
  • Arsitektur paket NuGet telah sepenuhnya ditulis ulang. Secara khusus, framework ini kini mendukung framework .NET >= 4.5.2 di platform Windows.

Platform yang tidak digunakan lagi

Seperti yang diumumkan dalam catatan rilis Juli 2019, OR-Tools tidak lagi mendukung Python 2.7.

Update dependensi

Protobuf 3.9.0 telah diperbarui ke 3.10.0.

Agustus 2019

Mengumumkan rilis OR-Tools v7.3

Kami telah merilis OR-Tools v7.3. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Platform yang tidak digunakan lagi

Kami menghentikan dukungan untuk Python 2.7 agar selaras dengan perpindahan Google ke Python 3. Ini akan menjadi rilis terakhir OR-Tools yang mendukung Python 2.7.

Update dependensi

Protobuf 3.8.0 telah diperbarui ke 3.9.0.

Perbaikan bug

Masalah berikut telah diperbaiki di OR-Tools v7.3. (Untuk daftar lengkapnya, lihat Kanban v7.3).

Pada khususnya:

  • Memperbaiki masalah transmisi init/int64 di Java (#1448),
  • Memperbaiki pemeriksaan presolve saat memproses batasan kumulatif kosong.

Juli 2019

Mengumumkan rilis OR-Tools v7.2

Kami telah merilis OR-Tools v7.2. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Perubahan platform

  • Kami menghentikan dukungan untuk Python 2.7 agar selaras dengan perpindahan Google ke Python 3. Akan ada paling banyak satu rilis lagi OR-Tools yang mendukung Python 2.7.
  • Ubuntu 18.10 diperbarui ke Ubuntu 19.04.
  • Menambahkan dukungan untuk kompilasi dari sumber di Visual Studio 2019.
  • Python 3.5 tidak lagi didukung di Windows; gunakan Python 3.6 atau yang lebih tinggi.

Update pada dependensi

  • Kita sekarang menargetkan CBC 2.10.3.
  • Kami sekarang menargetkan Protobuf 3.8.0.

CP-SAT

  • Kami telah melakukan beberapa peningkatan pada penelusuran, paralelisme, dan relaksasi linear.
  • Menambahkan LinearExpr.Sum() API dan LinearExpr.ScalProd() API di Python.
  • IntVar[].Sum() dan IntVar[].ScalProd() API tidak digunakan lagi di C#.
  • C++: Menghapus SolveWithModel() karena merupakan duplikat dari SolveCpModel().
  • Menambahkan metode CpModel.addGreaterThan() dan CpModel.addLessThan() ke Java API.

Pemecah masalah linear

  • Menambahkan MPSolver.SetHint() untuk Python, Java, dan C# (didukung oleh SCIP dan Gurobi).
  • Menambahkan MPSolver.SetNumThreads() untuk Python, Java, dan C# (didukung oleh CBC, Gurobi, dan SCIP).
  • Menulis ulang dukungan untuk SCIP 6.0.1.

Dokumentasi referensi

  • Kami telah menambahkan panduan referensi berbasis doksigen dan pdoc3 untuk semua bahasa dan semua alat (algoritma, perutean, grafik, linear_Solver, dan CP-SAT). Lihat Panduan Referensi OR-Tools.
  • Dokumentasi referensi lengkap untuk C++ (semua produk) dan CP-SAT (C++, Python, Java).
  • Kami sedang dalam proses mengekspor semua dokumentasi C++ ke Python dan Java.
  • Dokumentasi .NET kurang, dan kami tidak memiliki solusi dalam waktu dekat untuk meningkatkan ini. Kami menyimpannya karena masih menampilkan API yang tersedia.

Mei 2019

Mengumumkan rilis OR-Tools v7.1

Kami telah merilis OR-Tools v7.1. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Perubahan pada dependensi yang diperlukan

OR-Tools v7.1 memiliki dependensi baru dan yang diupdate berikut:

  • glog v0.3.5 diupdate ke v0.4.0
  • protobuf v3.6.1 diupdate ke v3.7.1
  • Cbc 2.9.9 diupdate ke 2.10.1
  • Cgl 0.59.10 diupdate ke versi 0.60.1
  • Clp 1.16.11 diupdate ke 1.77.1
  • Osi 0.107.9 diupdate ke 0.108.1
  • CoinUtils 2.10.14 diupdate ke 2.11.1

Perubahan CP-SAT API

Bagian berikut menjelaskan perubahan pada CP-SAT API di OR-Tools 7.1.

Menggunakan Domain untuk membuat variabel

Contoh berikut menunjukkan cara membuat variabel bilangan bulat dengan domain yang tidak berdekatan. Tindakan ini akan menggantikan metode NewEnumeratedIntVar() yang dihapus. Di sini, variabel x dapat berupa salah satu dari 1, 3, 4, atau 6:

Python

model.NewIntVarFromDomain(cp_model.Domain.FromValues([1, 3, 4, 6]), 'x')

C++

model.NewIntVar(Domain::FromValues({1, 3, 4, 6}));

Java

model.newIntVarFromDomain(Domain.fromValues(new long[] {1, 3, 4, 6}), "x");

C#

model.NewIntVarFromDomain(Domain.FromValues(new long[] {1, 3, 4, 6}), "x");

Variabel juga dapat dibuat menggunakan daftar interval. Di bawah ini, variabel x dibatasi menjadi 1, 2, 4, 5, atau 6:

Python

model.NewIntVarFromDomain(cp_model.Domain.FromIntervals([[1, 2], [4, 6]]), 'x')

C++

model.NewIntVar(Domain::FromIntervals({ {1, 2}, {4, 6} }));

Java

model.newIntVarFromDomain(Domain.fromIntervals(new long[][] { {1, 2}, {4, 6} }), "x");

C#

model.NewIntVarFromDomain(Domain.FromIntervals(new long[][] { new long[] {1, 2}, new long[] {4, 6} }), "x");

Menggunakan Domain dalam ekspresi linear

Contoh berikut menunjukkan cara membatasi ekspresi linear pada domain yang tidak berdekatan. Di sini, ekspresi linear linear_expr didefinisikan pada 5, 6, 8, 9 dan 10:

Python

model.AddLinearExpressionInDomain(linear_expr, cp_model.Domain.FromIntervals([(5, 6), (8, 10)]))

C++

model.AddLinearConstraint(linear_expr, Domain::FromIntervals({ {5, 6}, {8, 10} }))

Java

model.addLinearExpressionInDomain(linear_expr, Domain.fromIntervals(new long[][] { {5, 6}, {8, 10} }))

.NET

model.AddLinearExpressionInDomain(linear_expr, Domain.FromIntervals(new long[][] {new long[] {5, 6}, new long[] {8, 10} }));

Menggunakan helper ekspresi linear

Contoh-contoh berikut menunjukkan cara menggunakan metode bantuan untuk membuat penjumlahan dan perkalian skalar. Berikut contoh tempat kita ingin x + y == 20 dan 4 * x + 2 * y = 56:\

Python

model.Add(x + y == 20)
model.Add(4 * x + 2 * y == 56)

C++

cp_model.AddEquality(LinearExpr::Sum({x, y}), 20);
cp_model.AddEquality(LinearExpr::ScalProd({x, y}, {4, 2}), 56);

Java

model.addEquality(LinearExpr.sum(new IntVar[] {x, y}), 20);
model.addEquality(LinearExpr.scalProd(new IntVar[] {x, y}, new long[] {4, 2}), 56);

.NET

model.Add(x + y == 20);
model.Add(4 * x + 2 * y == 56);

Maret 2019

Mengumumkan rilis OR-Tools v7.0

Kami telah merilis OR-Tools v7.0. Untuk mengupdate versi, lihat bagian Penginstalan OR-Tools yang sesuai.

Perubahan pada platform yang didukung

OR-Tools v7.0 tidak lagi mendukung platform berikut:

  • Visual C++ 2015
  • Ubuntu 14.04
  • Python 3.4 di Linux

Jika menggunakan salah satu platform ini, Anda masih dapat menginstal OR-Tools v6.10.

Perubahan pada dependensi yang diperlukan

OR-Tools v7.0 memiliki dependensi baru dan yang diupdate berikut:

Bagian berikut menjelaskan fitur dan peningkatan baru dalam OR-Tools 7.0.

Pengelola indeks baru untuk program perutean

Di OR-Tools v7.0, program pemilihan rute kendaraan harus menggunakan RoutingIndexManager baru. Hal ini memastikan indeks standar untuk lokasi konsisten dengan indeks internal yang digunakan oleh pemecah, dan membantu mencegah error dalam kode Anda.

RoutingIndexManager baru memerlukan beberapa perubahan kecil pada program pemilihan rute, yang dijelaskan di bagian berikut:

Sertakan/impor RoutingIndexManager

Di OR-Tools 7.0, program pemilihan rute di C++ dan Java harus menyertakan atau mengimpor RoutingIndexManager seperti yang ditunjukkan dalam contoh di bawah:

C++

#include "ortools/constraint_solver/routing_index_manager.h"

Java

import com.google.ortools.constraintsolver.RoutingIndexManager;

Impor Python dan C# tidak berubah.

Mendeklarasikan RoutingIndexManager

Di OR-Tools v7.0, program pemilihan rute harus mendeklarasikan RoutingIndexManager dan membuat model pemilihan rute, seperti yang ditunjukkan dalam contoh berikut:

Python

manager = pywrapcp.RoutingIndexManager(num_locations, num_vehicles, depot)
routing = pywrapcp.RoutingModel(manager)

C++

RoutingIndexManager manager(num_locations, num_vehicles, depot);
RoutingModel routing(manager);

Java

RoutingIndexManager manager = new RoutingIndexManager(numLocations, numVehicles, depot);
RoutingModel routing = new RoutingModel(manager);

.NET

RoutingIndexManager manager = new RoutingIndexManager(numLocations, numVehicles, depot);
RoutingModel routing = new RoutingModel(manager);

Argumen untuk RoutingIndexManager adalah:

  • Jumlah lokasi
  • Jumlah kendaraan
  • Indeks depot (lokasi awal dan akhir untuk semua kendaraan)

Callback

Di OR-Tools v7.0, Anda harus menggunakan RoutingIndexManager untuk membuat callback, seperti callback jarak, yang kemudian diteruskan ke pemecah. Contoh berikut menunjukkan cara membuat callback jarak.

Python

    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["distance_matrix"][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

C++

  const int transit_callback_index = routing.RegisterTransitCallback(
      [&data, &manager](const int64_t from_index,
                        const int64_t to_index) -> int64_t {
        // Convert from routing variable Index to distance matrix NodeIndex.
        const int from_node = manager.IndexToNode(from_index).value();
        const int to_node = manager.IndexToNode(to_index).value();
        return data.distance_matrix[from_node][to_node];
      });
  routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

Java

    final int transitCallbackIndex =
        routing.registerTransitCallback((long fromIndex, long toIndex) -> {
          // Convert from routing variable Index to user NodeIndex.
          int fromNode = manager.indexToNode(fromIndex);
          int toNode = manager.indexToNode(toIndex);
          return data.distanceMatrix[fromNode][toNode];
        });
    routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

.NET

        int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
                                                                   {
                                                                       // Convert from routing variable Index to
                                                                       // distance matrix NodeIndex.
                                                                       var fromNode = manager.IndexToNode(fromIndex);
                                                                       var toNode = manager.IndexToNode(toIndex);
                                                                       return data.DistanceMatrix[fromNode, toNode];
                                                                   });
        routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

Metode IndexToNode mengonversi indeks lokasi internal yang digunakan oleh pemecah masalah menjadi indeks standar untuk matriks jarak.

Daripada meneruskan callback secara langsung ke pemecah, seperti pada versi sebelumnya, di v7.0, pertama-tama Anda membuat transit&nbsp;callback&nbsp;index, referensi ke callback, dan meneruskannya ke pemecah (dalam hal ini oleh SetArcCostEvaluatorOfAllVehicles).

Dimensi

Contoh berikut menunjukkan cara membuat dimensi untuk permintaan dan kapasitas, yang digunakan untuk menyelesaikan masalah pemilihan rute kendaraan kapasitas.

Python

    def demand_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data["demands"][from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        data["vehicle_capacities"],  # vehicle maximum capacities
        True,  # start cumul to zero
        "Capacity",
    )

C++

  const int demand_callback_index = routing.RegisterUnaryTransitCallback(
      [&data, &manager](const int64_t from_index) -> int64_t {
        // Convert from routing variable Index to demand NodeIndex.
        const int from_node = manager.IndexToNode(from_index).value();
        return data.demands[from_node];
      });
  routing.AddDimensionWithVehicleCapacity(
      demand_callback_index,    // transit callback index
      int64_t{0},               // null capacity slack
      data.vehicle_capacities,  // vehicle maximum capacities
      true,                     // start cumul to zero
      "Capacity");

Java

    final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> {
      // Convert from routing variable Index to user NodeIndex.
      int fromNode = manager.indexToNode(fromIndex);
      return data.demands[fromNode];
    });
    routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
        data.vehicleCapacities, // vehicle maximum capacities
        true, // start cumul to zero
        "Capacity");

.NET

        int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) =>
                                                                       {
                                                                           // Convert from routing variable Index to
                                                                           // demand NodeIndex.
                                                                           var fromNode =
                                                                               manager.IndexToNode(fromIndex);
                                                                           return data.Demands[fromNode];
                                                                       });
        routing.AddDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
                                                data.VehicleCapacities, // vehicle maximum capacities
                                                true,                   // start cumul to zero
                                                "Capacity");

Solusi pencetakan

Di OR-Tools v7.0, Anda harus menggunakan RoutingIndexManager untuk menampilkan rute kendaraan dalam solusi. Contoh berikut menunjukkan cara mencetak solusi dalam semua bahasa yang didukung.

Python

def print_solution(manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    index = routing.Start(0)
    plan_output = "Route for vehicle 0:\n"
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += f" {manager.IndexToNode(index)} ->"
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += f" {manager.IndexToNode(index)}\n"
    plan_output += f"Distance of the route: {route_distance}m\n"
    print(plan_output)

C++

//! @brief Print the solution
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const RoutingIndexManager& manager,
                   const RoutingModel& routing, const Assignment& solution) {
  LOG(INFO) << "Objective: " << solution.ObjectiveValue();
  // Inspect solution.
  int64_t index = routing.Start(0);
  LOG(INFO) << "Route for Vehicle 0:";
  int64_t distance{0};
  std::stringstream route;
  while (!routing.IsEnd(index)) {
    route << manager.IndexToNode(index).value() << " -> ";
    const int64_t previous_index = index;
    index = solution.Value(routing.NextVar(index));
    distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{0});
  }
  LOG(INFO) << route.str() << manager.IndexToNode(index).value();
  LOG(INFO) << "Distance of the route: " << distance << "m";
  LOG(INFO) << "";
  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}

Java

  /// @brief Print the solution.
  static void printSolution(
      DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
    // Solution cost.
    logger.info("Objective : " + solution.objectiveValue());
    // Inspect solution.
    logger.info("Route for Vehicle 0:");
    long routeDistance = 0;
    String route = "";
    long index = routing.start(0);
    while (!routing.isEnd(index)) {
      route += manager.indexToNode(index) + " -> ";
      long previousIndex = index;
      index = solution.value(routing.nextVar(index));
      routeDistance += routing.getArcCostForVehicle(previousIndex, index, 0);
    }
    route += manager.indexToNode(routing.end(0));
    logger.info(route);
    logger.info("Distance of the route: " + routeDistance + "m");
  }

.NET

    /// <summary>
    ///   Print the solution.
    /// </summary>
    static void PrintSolution(in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution)
    {
        Console.WriteLine("Objective: {0}", solution.ObjectiveValue());
        // Inspect solution.
        Console.WriteLine("Route for Vehicle 0:");
        long routeDistance = 0;
        var index = routing.Start(0);
        while (routing.IsEnd(index) == false)
        {
            Console.Write("{0} -> ", manager.IndexToNode((int)index));
            var previousIndex = index;
            index = solution.Value(routing.NextVar(index));
            routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
        }
        Console.WriteLine("{0}", manager.IndexToNode((int)index));
        Console.WriteLine("Distance of the route: {0}m", routeDistance);
    }

Dukungan untuk VRP dengan pengambilan dan pengiriman

OR-Tools v7.0 memberikan dukungan untuk memecahkan masalah pemilihan rute kendaraan (VRP) dengan pengambilan dan pengiriman, dengan tujuannya adalah menemukan rute terpendek bagi armada kendaraan yang mengambil dan mengirimkan item di berbagai lokasi. Anda menyiapkan masalah yang mirip dengan VRP standar, tetapi selain itu, Anda menentukan sepasang (i, j) lokasi untuk setiap item, dengan i adalah lokasi penjemputan dan j adalah lokasi pengantaran. Pemecah masalah pemilihan rute menampilkan rute kendaraan sehingga untuk setiap pasangan (i, j), i, dan j berada di rute yang sama, dan kendaraan mengunjungi i sebelum j.

Untuk contoh yang memecahkan masalah jenis ini, lihat Pemilihan Rute Kendaraan dengan Pickup dan Pengiriman.

Dukungan untuk fungsi lambda

OR-Tools v7.0 kini menyertakan dukungan untuk fungsi lambda di C# dan Java (selain C++ dan Python, yang sudah didukung). Fungsi lambda menyediakan cara yang mudah untuk menentukan callback dalam program perutean. Namun, Anda dapat menentukan callback menggunakan fungsi standar jika merasa hal tersebut membuat kode lebih mudah dibaca.

Contoh callback C# dan Java di atas menunjukkan cara menentukan callback menggunakan fungsi lambda.

November 2018

Mengumumkan rilis versi v6.10

Kami telah merilis OR-Tools versi 6.10. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Bagian berikut menjelaskan fitur dan peningkatan baru dalam versi 6.10.

Perintah yang disederhanakan untuk membuat dan menjalankan program

Pada versi 6.10, Anda dapat membuat dan menjalankan program dengan memasukkan perintah seperti berikut: 

make run SOURCE=relative/path/to/program.cc
, dengan <var>relative/path/to</var> adalah jalur ke direktori yang berisi program tersebut.

Untuk membuat program tanpa menjalankannya, masukkan: 

make build SOURCE=relative/path/to/program.cc
Lihat Mulai Menggunakan OR-Tools untuk mengetahui petunjuk khusus menjalankan program menurut bahasa.

Dukungan untuk SCIP 6.0.0

OR-Tools sekarang menyediakan dukungan untuk SCIP 6.0.0.

Biner

Distribusi biner telah dibangun menggunakan Java JDK 8 (JDK 7 untuk Ubuntu 14.04).

Pemecah Soal CP-SAT

Mengupdate API

  • Tambahkan C++ CP-SAT CpModelBuilder API.

Contoh

Beberapa contoh telah dipindahkan.

  • Pindahkan contoh komunitas ke examples/contrib.
  • Pindahkan beberapa contoh ke ortools/<var>component</var>/samples (misalnya, ortools/linear_solver/samples/simple_program.java)

September 2018

Mengumumkan rilis versi v6.9

Kami telah merilis OR-Tools versi 6.9. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Dependensi yang diupdate

  • Protobuf 3.5.1 -> 3.6.1.
  • SCIP 4.0 -> 6.0.

Pemecah Soal CP-SAT

  • Perubahan yang dapat menyebabkan gangguan pada API - detail lengkapnya di sini:
  • Ganti nama SolveWithSolutionObserver menjadi SolveWithSolutionCallback di Python.

  • Ganti nama NewSolution menjadi OnSolutionCallback di class CpSolverSolutionCallback di Python. Contoh berikut menunjukkan cara baru untuk membuat callback solusi di Python. 

    class MySolutionCallback(cp_model.CpSolverSolutionCallback):
def init(self):
cpmodel.CpSolverSolutionCallback.init(self)
self._solution_count = 0
    


    def OnSolutionCallback(self):
print('Solution {}, time = {}s, objective = {}, makespan = {}'.format(
  self.solution_count,
  self.WallTime(),
  self.ObjectiveValue(),
  self.Value(makespan)))
self.solution_count += 1

  • Ekspos StopSearch pada callback solusi di Python, Java, dan C#. Dokumentasinya ada di sini.

  • Mengekspos ModelStats dan CpSolverResponseStats di Python, Java, dan C#.

  • Meningkatkan dokumentasi docstring Python. Dokumentasinya ada di sini.

  • Update pada implementasi Java untuk antarmuka resolver dan buku resep.

  • Mengimplementasikan modulo.

  • Mengubah penerapan reservoir: tambahkan API dengan boolean untuk menentukan peristiwa pengosongan/pengisian opsional.

Linear Solver

  • Mengekspos InterruptSolve di Java dan C#.

Pemecah Soal CP

  • Mengekspos direktur SolutionCollector di C#.

Python

  • Menambahkan dukungan untuk Python 3.7.
  • Saat mengompilasi dari sumber: lebih memilih python3 daripada python2 saat mendeteksi python.

.NET

  • Penulisan ulang lapisan .NET sepenuhnya.
  • Menyediakan paket Nuget Google.OrTools NetStandard 2.0 yang kompatibel dengan Runtime IDentifier win-x64, linux-x64, dan osx-x64.
  • Menyediakan paket Nuget Google.OrTools.FSharp.
  • Menambahkan file project untuk semua contoh .NET.
  • Mengupdate semua contoh skrip F# (.fsx) ke project F# reguler (.fs).
  • Tambahkan dokumentasi tentang pembuatan build paket .NET di sini.

{i>Flatzinc<i}

  • Menambahkan dukungan untuk set dalam flatzinc (menggunakan nosets.mzn).

Kontribusi

  • Menambahkan dukungan untuk Binder. Terima kasih kepada Kevin Mader.
  • Jadikan DecisionVisitor sebagai jenis direktur di binding Java. Terima kasih kepada Jeremy Apthorp.

Juli 2018

Mengumumkan rilis versi v6.8

Kami telah merilis OR-Tools versi 6.8. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Mengumumkan pemecah masalah CP-SAT

Pemecah masalah CP-SAT adalah pemecah masalah baru untuk pemrograman batasan. Pemecah CP-SAT lebih cepat daripada pemecah CP asli, dan harus lebih disukai untuk masalah CP.

Untuk contoh yang menggunakan pemecah masalah CP-SAT, lihat direktori contoh di GitHub untuk file yang memiliki _sat dalam namanya.

Pemecah CP asli akan terus dipertahankan selama jangka waktu tertentu untuk mendukung kode yang ada, tetapi tidak digunakan lagi.

Opsi baru untuk pemecah masalah CP-SAT

Opsi untuk pemecah masalah CP-SAT berikut terbilang baru dalam rilis ini:

  • Penelusuran lingkungan lokal (LNS): Gunakan opsi SatParameters.use_lns untuk mengaktifkan LNS.
  • Penelusuran paralel: Gunakan opsi SatParameters.num_search_workers untuk mengaktifkan beberapa thread selama penelusuran. Setiap thread dapat memiliki parameter yang berbeda, dan seed acak yang berbeda. Hal ini memaksimalkan keberagaman, dan probabilitas bahwa setidaknya satu thread akan menemukan solusi.

Peningkatan performa untuk pemecah masalah

Kami telah melakukan peningkatan performa pada pemecah masalah CP-SAT dan Glop.

Maret 2018

Mengumumkan rilis versi v6.7

Kami telah merilis OR-Tools versi 6.7. Untuk mengupdate versi, lihat bagian yang sesuai dari Penginstalan OR-Tools.

Update ke dependensi yang diperlukan

  • Protobuf 3.5.0 -> 3.5.1.

Lain-lain

  • Faktorkan ulang basis untuk menyiapkan integrasi abseil-cpp.
  • Penggunaan layanan continuous integration (CI) Travis CI dan Appveyor.

SAT

  • Peningkatan performa.
  • Meningkatkan Python API.
  • Tambahkan C# API alias CpSolver.cs (EKSPERIMENTAL).

Glop

  • Pemfaktoran ulang kode.
  • Peningkatan performa.

Dukungan CMake (EKSPERIMENTAL)

  • Menambahkan dukungan CMake C++ OR-Tools.
  • Dapat membangun OR-Tools sebagai project CMake mandiri.
  • Dapat menggabungkan OR-Tools ke dalam project CMake yang Ada.
  • Menambahkan build berbasis CMake OR-Tools Python.
  • Membuat paket (roda) Python menggunakan CMake.

Kontribusi

  • Memperbaiki definisi ulang winsock2.h di Windows. Terima kasih kepada Florent Tollin de Rivarol.
  • Tambahkan Dukungan F# (EKSPERIMENTAL). Terima kasih kepada Matthew Moore. Catatan: hanya tersedia dengan builder Makefile.
  • Tambahkan Dukungan Standard .NET (EKSPERIMENTAL). Terima kasih kepada Ziad El Malki. Catatan: hanya tersedia dengan builder Makefile.

November 2017

Mengumumkan rilis versi v6.6

Kami telah merilis OR-Tools versi 6.6. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Update untuk dependensi yang diperlukan

  • Protobuf ke 3.3.0 -> 3.5.0.
  • gflags ke 2.2.0 -> 2.2.1.
  • CBC 2.9.8 -> 2.9.9.
  • Tambahkan modul Python enam (1.10) sebagai dependensi yang diperlukan untuk Python.

Perbaikan Bug

  • Permintaan pull #494 Pemfaktoran ulang nama. Menambahkan komentar untuk IntelliSense di beberapa editor. Terima kasih kepada Matthew Moore.
  • Permintaan pull #516 Instruksi untuk biner mandiri F#. Terima kasih kepada Matthew Moore.
  • Meningkatkan presisi di Glop.

Pemecah Soal SAT

  • Tingkatkan pemecah SAT internal, Memperbaiki berbagai bug.
  • Tambahkan batasan VRP ke pemecah masalah SAT, yang ditautkan ke pemecah masalah LP.
  • Ubah observer solusi dalam pemecah masalah SAT untuk mengambil CpSolverResponse sebagai parameter.
  • Meningkatkan penggunaan Glop dalam SAT Solver.
  • Percepat koneksi SAT-LP.
  • Menambahkan batasan Reservoir ke format protobuf SAT cp_model.

SAT/Python

Contoh

  • Tulis ulang rcpsp_parser untuk menggunakan format ProtoBuf guna menyimpan masalah.
  • Meningkatkan parser RCPSP.

Oktober 2017

Mengumumkan rilis versi v6.5

Kami telah merilis OR-Tools versi 6.5. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Perubahan pada platform

  • Modul pypi py3-ortools telah digabungkan ke dalam modul ortools. Kini hanya ada satu modul: 'ortools'.
  • Format utama untuk modul Python ini sekarang adalah file {i>wheel<i}. Untuk menginstal OR-Tools untuk python dari pypi, cukup jalankan pip install ortools. Anda memerlukan versi pip terbaru yang terinstal (>= 9.0.1). Cara ini akan menarik rilis terbaru (v6.5).

Bug fixed

File jar protobuf sekarang di-build dengan benar menggunakan class yang dikompilasi.

Contoh Baru

  • Lebih banyak contoh F# yang telah dikontribusikan ke direktori example/fsharp (Sekali lagi, terima kasih kepada Matthew Moore).
  • Contoh Java MIP juga telah dikontribusikan (Terima kasih Darian).

September 2017

Mengumumkan rilis versi v6.4

Kami telah merilis OR-Tools versi 6.4. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Perubahan pada platform

  • Modul Pypi di platform Linux kini dikirimkan sebagai file roda menggunakan tag manylinux1. Terima kasih kepada Federico Ficarelli. Dengan perubahan ini, kami telah melakukan backtrack modul per-linux yang diperkenalkan dalam rilis Juli 2017.

Fitur baru

  • Meningkatkan metode penskalaan yang digunakan di dalam GLOP.
  • Memperbaiki penggabungan evaluator di library pemilihan rute C#. Terima kasih kepada DevNamedZed.
  • Meningkatkan performa flatzinc presolve untuk model besar.
  • Gunakan SAT yang didukung untuk flatzinc secara default.
  • Meningkatkan performa pendekatan berbasis Core untuk sat solver.
  • Memperbaiki bug dalam algoritma penetapan linear yang gagal secara keliru.
  • Menambahkan contoh F# di ortools/examples/fsharp.
  • Hapus pemeriksaan penalti positif di library pemilihan rute.

Agustus 2017

Mengumumkan rilis versi v6.3

Kami telah merilis OR-Tools versi 6.3. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

File download baru

File wheel Python untuk Linux kini tersedia untuk didownload di halaman rilis OR-Tools, beserta versi terbaru dari semua download.

Pemecah masalah minizinc

Versi ini berisi kode sat dan flatzinc terakhir yang dikirim untuk tantangan Minizinc 2017.

Juli 2017

Mengumumkan rilis versi v6.2

Kami telah merilis OR-Tools versi 6.2. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Perubahan pada platform

  • Kini kami mendukung beberapa distribusi biner Linux (Ubuntu 14.04, 16.04, 17.04, CentOS 7, Debian 9).
  • Modul Pypi pada platform Linux kini menyertakan tag yang menjelaskan distribusi (ubuntu-14.04, ubuntu-16.04, ubuntu-17.04, centos-7, debian-9).

Fitur baru

Kami telah menambahkan dukungan untuk Docker guna membangun artefak linux. Buka or-tools/tools/docker, lalu lihat Makefile untuk melihat kemungkinan target (make archive, make pypi, dan make pypi3).

Perintah ini akan membuat subdirektori export dan menambahkan artefak biner di dalamnya.

Juni 2017

Mengumumkan rilis versi v6.1

Kami telah merilis OR-Tools versi 6.1. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Perubahan pada platform

  • Visual Studio 2017 didukung; Visual Studio 2013 tidak lagi didukung.
  • macOS versi 10.9 dan yang lebih baru didukung.

Fitur Baru

Kami telah menambahkan format protobuf baru untuk pemecah masalah CP-SAT kami. Lihat ortools/sat/cp_model.proto untuk menentukan model, dan ortools/sat/cp_model_solver.h untuk menyelesaikan masalah Anda.

Perbaikan Bug

Masalah #420: Kami telah memperbaiki atribut __version__ yang hilang pada modul pypi Python di semua platform.

Mei 2017

Mengumumkan rilis versi v6.0

Kami telah merilis OR-Tools versi 6.0. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Struktur direktori baru di C++

Kami telah mengubah struktur sumber/sertakan dalam OR-Tools saat menggunakan C++. Tujuannya adalah untuk memberikan enkapsulasi file penyertaan C++ yang lebih baik. Alat ini juga memiliki manfaat untuk menyelaraskan struktur direktori C++ dan Python.

  • src/ telah diganti namanya menjadi ortools/.
  • Semua perintah #include dalam file C++ sekarang memiliki awalan ortools yang ditambahkan. #include "constraint/constraint_solver.h" sekarang menjadi #include "ortools/constraint/constraint_solver.h".

Fitur baru

  • Dukungan Bazel. Sekarang Anda dapat membangun OR-Tools dengan bazel, alat build Google. Berfungsi di Linux dan Mac OS X. Setelah mendownload Bazel versi 0.4.5 atau yang lebih baru, ubah direktori ke or-tools dan buat contoh: bazel build examples/cpp/....

Pemilihan rute

Kami telah mengimplementasikan dukungan untuk jeda (misalnya, periode nonaktif kendaraan karena pengemudi makan siang) di library pemilihan rute. Fitur ini ditunjukkan dalam contoh cvrptw_with_breaks.cc.

Dukungan SCIP

Wrapper pemecah masalah linear sekarang mendukung SCIP 4.0. Anda harus membuat SCIP terlebih dahulu, lalu memberi tahu atau alat bahwa Anda akan menggunakannya. Petunjuknya tersedia di sini.

Dukungan GLPK

Kami juga telah mengubah cara build dengan GLPK. Lihat di sini.

Pembersihan

  • Kami telah menghapus semua penggunaan hash_map dan hash_set dalam codebase C++ karena tidak digunakan lagi. Mereka digantikan oleh {i>unordered_map<i} dan {i>unordered_set<i} dari STL.
  • Pembersihan makefile C#, oleh Michael Powell.

Januari 2017

Mengumumkan rilis versi v5.1

Kami telah merilis OR-Tools versi 5.1. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Fitur Baru

Menginstal

Pemilihan rute

Menerapkan algoritma untuk menghitung batas bawah Held-Karp untuk Masalah Penjual Bepergian yang simetris. Dengan begitu, Anda dapat menghitung batas atas dengan kesenjangan antara biaya solusi yang berpotensi tidak optimal dan biaya solusi yang optimal.

  • Menambahkan metode baru ke library pemilihan rute kendaraan, RoutingModel::SetBreakIntervalsOfVehicle, yang memungkinkan Anda menambahkan interval break — jangka waktu saat kendaraan tidak dapat melakukan tugas apa pun (seperti bepergian atau mengunjungi node). Untuk contoh yang menggunakan opsi ini, lihat cvrptw_with_breaks.cc

Penjadwalan

Pemecah soal Sabtu

Peningkatan performa

  • Pemecah masalah SAT — Peningkatan performa pemecah masalah Sat, terutama untuk batasan kumulatif.
  • Pemecah Glop — Peningkatan keandalan numerik dari pemecah masalah Glop, yang kini menampilkan solusi yang lebih akurat untuk masalah numerik yang sulit.
  • Pemecah {i>flatzinc<i}
  • Performa backend Sat yang sangat meningkat untuk penafsir flatzinc.
  • Menyederhanakan antarmuka C# flatzinc. Untuk contoh antarmuka baru, lihat https://github.com/google/or-tools/blob/master/examples/csharp/csfz.cs.

Perbaikan Bug

  • Menggunakan heuristik PathCheapestArc pada model perutean dengan satu kendaraan dan batasan sisi terkadang akan menyebabkan pemecah masalah berjalan dalam waktu yang terlalu lama. Hal ini diperbaiki dengan mempertimbangkan kendala sisi dengan benar.
  • Di Java, pemecah masalah pemilihan rute terkadang akan error saat memecahkan masalah pemilihan rute kendaraan. Masalah ini telah diperbaiki dalam rilis terbaru.

November 2016

Mengumumkan rilis versi v5.0

Kami telah merilis OR-Tools versi 5.0. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Contoh berjalan

  • Memperkenalkan target khusus bahasa yang mempermudah kompilasi dan menjalankan program, serta contoh yang disertakan dengan OR-Tools.

Sab

FlatZinc

Pemecah Masalah

Pemilihan rute

  • Mengimplementasikan AddAtSolutionCallback, yang merupakan callback yang dipanggil setiap kali solusi ditemukan selama penelusuran.
  • Menghapus konstruktor tanpa depot RoutingModel. Menentukan setidaknya satu depot dalam model perutean kini bersifat wajib.

September 2016

Mengumumkan rilis versi v4.4

Kami telah merilis OR-Tools versi 4.4. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Sab

  • API penjadwalan yang diperluas dan contoh yang dimodifikasi (weighted_tardiness_sat, dan jobshop_sat) untuk menggunakannya.

Grafik

  • Menambahkan trait iterator ke class Grafik.

Distribusi OR-Tools

  • Paket Nuget didukung lagi.

Agustus 2016

Mengumumkan rilis versi v4.3

Kami telah merilis OR-Tools versi 4.3. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Pemecah batasan

  • Mengimplementasikan metode NotBetween untuk membatasi variabel agar berada di luar interval tertentu.

routing

  • Menambahkan penguraian model untuk memeriksa batasan NotMember yang ada seperti yang ditunjukkan dalam contoh ini, dan menggunakannya dalam filter penelusuran lokal.
  • Profil penelusuran lokal ditambahkan.
  • Perbaikan untuk pemindahan lokal.

Pemecah masalah linear

  • Memperbaiki pelaporan status SCIP.

Sab

Glop

  • Meningkatkan performa dengan memanfaatkan ketersebaran di lebih banyak tahap komputasi.

{i>Flatzinc<i}

  • Memperbaiki bug yang ditemukan oleh tantangan minizinc.

Lp_data

  • Penyederhanaan template di iterator secara berkelanjutan.

Distribusi OR-Tools

  • Assembly C# sekarang diberi nama kuat secara default.
  • Telah diupgrade ke Protobuf3.0.0.
  • Penambahan script Python untuk memeriksa dependensi arsip OR-Tools.

Juli 2016

Mengumumkan rilis versi v4.2

Kami telah merilis OR-Tools versi 4.2. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Pemecah masalah (perutean)

  • Disjungsi kini dapat ditentukan dengan kardinalitas, yang merupakan jumlah maksimum node yang dapat aktif dalam disjungsi ini. Misalnya, jika Anda menambahkan disjungsi dengan n node dan kardinalitas k, maka k node di antara n node diizinkan untuk aktif. Anda dapat menggunakan definisi baru AddDisjunction untuk melakukannya.
  • Menambahkan dukungan untuk beberapa disjungsi per node. Misalnya, sekarang Anda dapat menambahkan node, N1, ke banyak disjungsi (D1..Dm). Hal ini meningkatkan peluangnya untuk menjadi aktif di salah satunya. Memperkenalkan algoritma penelusuran pemilihan rute yang lebih cepat untuk masalah terkait periode waktu disjungsi.
  • Menambahkan parameter pemecah batasan ke parameter model pemilihan rute dan log_search untuk merutekan parameter penelusuran.
  • Algoritma penelusuran lokal lebih cepat dalam menyelesaikan masalah dengan jendela waktu yang terpisah-pisah. Lihat contoh cvrp_disjoint_tw.cc untuk mengetahui detail selengkapnya.

Glop (pengoptimalan linear)

  • Memperkenalkan Algoritma Simplex yang lebih cepat.

Distribusi OR-Tools

  • Satu arsip per platform, bukan arsip individual untuk setiap arsip C++, Java, dan .Net. Arsip Python masih dihosting di pypi.
  • Di pypi, kami telah beralih ke modul {i>wheel<i} (.whl) di Mac OS X dan Windows. Memperkenalkan skema penomoran MAJOR.MINOR. Nomor ini digunakan sebagai nama arsip, versi yang disimpan di library bersama Mac OS X, modul Python, assembly .NET. Versi pertama yang kami rilis adalah dengan skema ini adalah v4.2

Juni 2016

Mengumumkan rilis versi v2016-06

Kami telah merilis OR-Tools versi v2016-06. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Pemecah Masalah

  • Menghapus sebagian besar instance callback (src/base/callback.h) dari library CP.
  • Menambahkan NotMemberCt (variabel tidak boleh termasuk dalam kumpulan interval).

{i>Routing library<i}

  • PERUBAHAN TIDAK KOMPATIBEL: Untuk menentukan kapasitas kendaraan di AddDimensionWithVehicleCapacity, kini Anda harus meneruskan array (vektor di c++), bukan callback.

GLOP

  • Mengubah representasi internal matriks renggang.
  • Peningkatan performa.

Grafik

  • Menulis ulang algoritma Dijkstra dan Bellman-Ford untuk mengganti callback dengan std::function (C++).
  • Mengubah API implementasi grafik yang berbeda saat melakukan iterasi melalui busur dan node.

Sab

  • Hapus metode inti yang tidak digunakan (Node resolusi).
  • Menambahkan penulis Drat untuk memeriksa bukti terkait ketidakpuasan.
  • Menambahkan praprosesor.

Bop

  • Tambahkan lingkungan baru.

Contoh

  • c++: menghilangkan {i>filelinereader<i} dalam contoh.
  • data: Menambahkan masalah penjadwalan satu mesin.

Dokumentasi

April 2016

Mengumumkan rilis versi v2016-04

Kami telah merilis OR-Tools versi v2016-04. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Dependensi yang diupdate

Desember 2015

Mengumumkan rilis versi v2015-12

Kami telah merilis OR-Tools versi v2015-12. Untuk mengupdate versi, lihat bagian yang sesuai dalam Penginstalan OR-Tools.

Pemecah Masalah

  • Kompatibilitas error di Large Neighborhood Search di pemecah masalah CP (lihat examples/cpp/ls_api.cc, examples/python/pyls_api.py, examples/csharp/csls_api.cs, dan examples/com/google/ortools/sample/LsApi.java untuk melihat API baru).
  • Membersihkan pembungkusan Python. Mendukung keputusan kustom di pemecah masalah CP (lihat examples/test/test_cp_api.py untuk melihat cara kerja API).
  • Beragam peningkatan dan perbaikan bug.

September 2015

Mengumumkan rilis pertama di github.

File akan disimpan di sana mulai sekarang.

{i>Flatzinc<i}

  • Menambahkan arsip biner untuk penafsir flatzinc (lihat www.minizinc.org).
  • Berisi beberapa perbaikan pada versi yang digunakan dalam tantangan.