Ghi chú phát hành công cụ HOẶC

Trang này liệt kê các thay đổi đối với công cụ OR-Tools, bao gồm cả các tính năng mới, bản sửa lỗi và điểm cải tiến đối với mã cũng như quy trình cài đặt.

Nếu bạn gặp sự cố khi cài đặt OR-Tools, hãy xem phần Khắc phục sự cố trong hướng dẫn cài đặt OR-Tools. Nếu vấn đề của bạn không được liệt kê ở đó, hãy kiểm tra các vấn đề trên GitHub hoặc đừng ngần ngại mở một vấn đề mới, chúng tôi rất sẵn lòng hỗ trợ bạn.

Sau đây là các ghi chú phát hành cho công cụ OR-Tools, bắt đầu từ bản phát hành mới nhất.

Tháng 3/2024

Thông báo về việc phát hành OR-Tools phiên bản 9.9

Chúng tôi đã phát hành OR-Tools phiên bản 9.9. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Bạn có thể tìm thấy ghi chú phát hành trên github

Tháng 11 năm 2023

Thông báo về việc phát hành OR-Tools phiên bản 9.8

Chúng tôi đã phát hành OR-Tools v9.8. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Các thay đổi về nền tảng

• Thêm Python 3.12.
• Thêm tính năng hỗ trợ cho Ubuntu 23.10

Trình giải tuyến tính

• Chuyển ModelBuilder sang .Net.
• Đổi tên LogCallback thành MbLogCallback để tránh xung đột với SAT LogCallback.
• Mở rộng API ModelBuilder:
  • Thêm các điều kiện ràng buộc đối với chỉ báo.
  • Thêm tính năng hỗ trợ gợi ý.
  • Thêm tính năng sao chép mô hình.

Chọn toán

• Chỉnh sửa kỹ càng.

Đang định tuyến

• Thêm trạng thái ROUTING_OPTIMAL.
• Đặt RoutingModel là không thể sao chép cũng như di chuyển.
• Sửa một số vòng lặp vô hạn trong các toán tử tìm kiếm cục bộ.
• Thêm một cấu trúc nội bộ PickupDeliveryPosition.
• Thêm phương thức IsPickup() và IsDelivery().

SAT

• Giảm mức sử dụng bộ nhớ đối với mô hình lớn.
• Cải thiện tính năng tìm kiếm về lịch biểu.
• hãy thêm packageing_precedences_lns.
• tối ưu hoá và khắc phục tình trạng tăng đột biến về tính khả thi.
• tối ưu hóa giải pháp giải quyết tuyến tính và ghi nhật ký giải pháp tốt hơn.
• Cải thiện giải pháp cho int_abs, int_mod, int_prod và lin_max.
• Cải thiện khả năng hỗ trợ của Panda
• Sửa một số lỗi.

Nhật ký thay đổi GitHub

Tháng 8/2023

Thông báo về việc phát hành OR-Tools phiên bản 9.7

Chúng tôi đã phát hành OR-Tools v9.7. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Các thay đổi về nền tảng

• Thả Centos-8 (EOL).
• Phát hành Debian 10.
• Ra mắt Panama [33, 36] (EOL).
• Thả Ubuntu 18.04 LTS (EOL).
• Thả Python 3.7 (EOL).
• Tắt tính năng hỗ trợ netcore3.1 trong CMake (EOL).

Trăn tạo mô hình

• Cho phép sử dụng chuỗi dữ liệu và chuỗi dữ liệu của Pandas để tạo biến.
  • xem bài tập
  • xem bin_packing
• Hoàn tất thông tin nhập

Ngăn chặn mất dữ liệu (PDLP)

• nhiều nội dung cập nhật khác nhau.

CP-SAT

• Cải thiện hiệu suất (khả_năng_nhảy_khó; lin_max)
• Cải thiện khả năng quản lý đoạn cắt
• Trình thực thi object_sperform_search mới dành riêng cho việc cải thiện giới hạn dưới của mục tiêu (khi thu nhỏ)
• Nhập chú thích cho cp_model.py python
• Tính năng hỗ trợ thử nghiệm một phần cho gấu trúc trong cp_model.py
  • xem bài tập
  • xem bin_packing
• Trình chạy dựa trên lỗi vi phạm tìm kiếm cục bộ thử nghiệm:
  • được bật với các thông số: num_violation_ls:xxx
  • được tối ưu hóa cho mô hình tuyến tính (linear, bool_or, bool_and, at_most_one, exactly_one)
  • hoạt động chính xác với lin_max, sản phẩm, phép chia
  • hỗ trợ no_overlap, tích luỹ, mạch, tuyến đường
  • đã tắt do no_overlap_2d
  • số lượng worker được đề xuất: num_workers -> num_violation_ls: (8, 1), (16, 2) (24, 3), (32, 4)

Nhật ký thay đổi GitHub

Tháng 3 năm 2023

Thông báo về việc phát hành OR-Tools phiên bản 9.6

Chúng tôi đã phát hành OR-Tools v9.6. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Các thay đổi về nền tảng

• Thêm tính năng hỗ trợ cho Panama 37, 38.
• Thả Python 3.6 (không được protobuf hỗ trợ).
• Thả Python 3.7 trên macOS (không được scipy hỗ trợ).
• Thêm tính năng hỗ trợ net7.0 trong CMake (sử dụng -DUSE_DOTNET_7=ON)
• Giảm netcore3.1 trong các gói nuget .org

Phần phụ thuộc

• SCIP v801 -> v803 (lưu ý: hiện tại, SCIP sử dụng giấy phép tương thích với OSI)
• tuyệt đối 20220623.1 -> 20230105.0
• Protobuf v21.5 -> v21.12
• SWIG 4.1.1
• Java JNA 5.11.0 -> 5.12.1

Bazel

• Thêm tính năng hỗ trợ pybind11.
• Thêm tính năng hỗ trợ trình bao bọc Java.

Trình giải toán

• PDLP: trình bao bọc dd python.
• CP-SAT: Cải thiện hiệu suất.
• GLOP: Tweak presolve.
• ModelBuilder: Python: Cải thiện hỗ trợ numpy.
• Định tuyến: Cải thiện hiệu suất (tìm kiếm cục bộ)

Vấn đề đã biết:

• CP-SAT: Việc bỏ qua trình phân giải phụ pseudo_costs sẽ trả về các tham số không hợp lệ (xem #3706).

Tháng 11 năm 2022

Thông báo về việc phát hành OR-Tools phiên bản 9.5

Chúng tôi đã phát hành OR-Tools v9.5. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Các thay đổi về nền tảng

• Thêm tính năng hỗ trợ Debian Sid.
• Thêm tính năng hỗ trợ cho Panama 35, 36.
• Thêm tính năng hỗ trợ Ubuntu 22.10.
• Thả Python 3.6 trên macOS.
• Thêm tính năng hỗ trợ Python 3.11.

Cập nhật phần phụ thuộc

• Protobuf v19.4 -> v21.5.
• Trình giải toán SCIP v800 -> v801.

CP-SAT

• Cải tiến giải pháp: max(mảng), ràng buộc Boolean, ràng buộc tuyến tính.
• Tìm kiếm xen kẽ phải có tính tất định song song.
• Cắt theo đường thẳng: xoá bớt hình vuông và int_prod cắt; viết lại quy trình cắt.
• Giải pháp và mô hình nhập vân tay (hiển thị trong nhật ký).
• Cải tiến tính năng lên lịch.
• Nhóm bản sửa lỗi thông thường (sự cố trong quá trình giải quyết, sự cố khi cắt, giải pháp không khả thi, mô hình không khả thi trong LNS).

TỔNG QUAN

• Tăng tốc bằng cách viết lại đại số tuyến tính cũng như quy tắc lựa chọn tổng hợp.

Trình giải tuyến tính

• Thêm knapsack_interface.cc.
• Di chuyển API model_builder trong thư mụcLinear_Solve (tiêu đề và mẫu).
• Thêm hỗ trợ cho Gurobi 10.

Đang định tuyến

• Giải phóng một số trình phân tích cú pháp cho nhiều thử thách định tuyến.

Tháng 8 năm 2022

Thông báo về việc phát hành OR-Tools phiên bản 9.4

Chúng tôi đã phát hành OR-Tools v9.4. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Nền tảng

• Thêm tính năng hỗ trợ Debian-10 (xem #3029).
• Thêm tính năng hỗ trợ LTS Ubuntu 22.04 (xem #3276). Lưu ý: sẽ không hỗ trợ .Net 3.1 (xem dotnet/core#7038).
• Xoá tính năng hỗ trợ Ubuntu 21.10.

Tính năng khác

• Phân tách tệp lưu trữ theo ngôn ngữ và thêm cấu hình CMake vào C++ (phiên bản 3200).

Biểu đồ

Tách ortools.graph.pywrapgraph thành:

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

Điều này cho phép sử dụng numpy để tăng tốc độ thiết lập vấn đề.

CP-SAT

Một số điểm cải thiện về:

• lập lịch (truyền tải, cắt, giới hạn dưới).
• MaxSAT (giải quyết, suy đoán dựa trên cốt lõi).
• Hiệu suất MIP (giải quyết, cắt giảm).

Tháng 3/2022

Thông báo về việc phát hành OR-Tools phiên bản 9.3

Chúng tôi đã phát hành OR-Tools v9.3. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Các thay đổi về nền tảng

• Ngừng hỗ trợ Debian-10.
• Ngừng hỗ trợ Ubuntu-16.04.
• Thả .NET Framework 4.5.2.

Cập nhật phần phụ thuộc

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

Python

• Thêm pybind11.

Tính năng

• Thêm tính năng PDLP làm thử nghiệm.
• Thêm MathOpt dưới dạng thử nghiệm.

CP-SAT

• Đổi tên một số API để đảm bảo tính nhất quán, ví dụ: LinearExpr.ScalProd. -> LinearExpr.WeightedSum..
• Thêm các phương thức AddAtLeastOne/AddAtMostOne/AddExactlyOne.
• Thêm AddMultiplicationConstraint(z, x, y) bằng mọi ngôn ngữ.
• Thêm AddMultipleCircuit() bằng mọi ngôn ngữ.

C++

• Đối tượng rõ ràng IntVar(BoolVar).
• Xoá LinearExpr::Add* và thay thế bằng toán tử, ví dụ: LinearExpr +=.
• Thêm toán tử số học trên biểu thức tuyến tính.
• Đã xoá LinearExpr::BooleanSum/BooleanScalProd, hãy sử dụng Sum/WeightedSum.
• Thêm CpModelBuilder::FixVariable() để ghi đè miền của biến thành một giá trị duy nhất.

Java

• Viết lại LinearExpr, thêm một lớp trình tạo gia tăng: LinearExpr.newBuilder().add(x).addSum(<array of variables>).build().
• Tuân theo API C++: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment và ForbiddenAssignment hiện trả về một lớp chuyên biệt với API tăng dần để thêm các biến, thuật ngữ, yêu cầu mới...

C

• Ghi lại tất cả các phương pháp.
• Tuân theo API C++: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment và ForbiddenAssignment hiện trả về một lớp chuyên biệt với API tăng dần để thêm các biến, thuật ngữ, yêu cầu mới...
• Thêm lớp LinearExprBuilder để tạo biểu thức tăng dần.

Hệ thống xây dựng

CMake

• Yêu cầu tối thiểu là CMake >= 3.18.

Tạo

• Bây giờ, hãy sử dụng bản dựng dựa trên CMake trong nội bộ.

Tháng 12 năm 2021

Thông báo về việc phát hành OR-Tools phiên bản 9.2

Chúng tôi đã phát hành OR-Tools v9.2. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Các thay đổi về nền tảng

• Thêm tính năng hỗ trợ cho Ubuntu 21:10 (bản phát hành lần cuối).

Cập nhật phần phụ thuộc

• Cập nhật .Net TFM net5.0 -> net6.0 (cần .Net SDK 6.0 LTS và .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: thêm numpy >= 1.13.3.
• Trên MacOS, hãy biên dịch Coin-OR trong -O1 để tránh sự cố trong các trình chạy.

Đang định tuyến

• Cải tiến bộ lọc.
• Cải thiện những thông tin phỏng đoán đầu tiên về giải pháp.
• Cải thiện vị trí ngắt thời gian.

CP-SAT

Thay đổi có thể gây lỗi

• Vùng đệm giao thức cơ bản không tương thích với các phiên bản trước. Mọi vùng đệm giao thức được lưu trữ sẽ phải được tạo lại bằng các API trình tạo đã cập nhật (trong C++, Python, Java và .NET)
• Cụ thể, khoảng protobuf đã được xoá sạch vì chúng tôi xoá các trường cũ (bắt đầu, kích thước và kết thúc) và đổi tên các trường mới (sử dụng _view) để sử dụng tên của các trường đã xoá.

Tính năng mới

• Các ràng buộc all_different, reservoir, modulo, multiplication và division chấp nhận biểu thức affine (a * var + b) ở mọi nơi yêu cầu biến số nguyên.
• Mục tiêu chấp nhận hệ số dấu phẩy động (Xem lớp DoubleLinearExpr trong C++/Java/.NET. Hãy xem ví dụ về knapsack_2d_sat.py trong Python).
• Quy tắc ràng buộc no_overlap_2d hỗ trợ các khoảng thời gian không bắt buộc.
• API C++ triển khai các toán tử + và * để tạo biểu thức.

Những điểm cải tiến

• Cải tiến mã presolve (giải quyết vấn đề).
• Trình kiểm tra mô hình chặt chẽ hơn.
• Sửa lại quy tắc ràng buộc của vùng chứa.
• Thêm các thao tác cắt mạnh mẽ cho quy tắc ràng buộc no_overlap_2d.
• Cải thiện tính năng nới lỏng tuyến tính của các quy tắc ràng buộc mã hoá (literal implies var == value).

Các phương thức không dùng nữa và đã bị xoá

• Không dùng C++ BooleanSum và BooleanScalProd nữa. Chỉ cần sử dụng Sum và ScalProd.
• Xoá C++ AddLinMinEquality và AddLinMaxEquality. Chỉ cần sử dụng AddMinEquality và AddMaxEquality.

Tính không tương thích trong tương lai

• Tại một thời điểm trong tương lai, chúng tôi sẽ ghi lại lớp mô hình Java để gần với lớp C++ hơn.
• Trong lớp mô hình hoá C++, chúng ta sẽ làm cho tác nhân IntVar(BoolVar var) trở nên rõ ràng.
• Chúng tôi đang dự tính việc làm cho API của python tuân thủ PEP 8 (sử dụng tên hiển_case). Nếu trường hợp này xảy ra, chúng tôi sẽ cung cấp một tệp sed để chuyển mã.

Hệ thống xây dựng

Bazel

• Sửa lỗi bản dựng Windows.

CMake

• Thêm lựa chọn FETCH_PYTHON_DEPS (mặc định là ON).
• Thêm tuỳ chọn hỗ trợ không bắt buộc cho trình giải GPLK (mặc định là -DUSE_GLPK=OFF).

Python

• Hỗ trợ số nguyên numpy trong hầu hết API CP-SAT.
• Khắc phục vấn đề thiếu __version__.

Tháng 9/2021

Thông báo về việc phát hành OR-Tools v9.1

Chúng tôi đã phát hành OR-Tools v9.1. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Các thay đổi về nền tảng

• Python: sử dụng hình ảnh manylinux2014 (xem PEP 599).
• Python: thêm tính năng hỗ trợ cho linux aarch64 bằng cách sử dụng hình ảnh manylinux2014_aarch64.
• .Net: thêm tính năng hỗ trợ .Net 5.0.

Cập nhật phần phụ thuộc

• abseil-cpp 20210324.1 -> 20210324.2.
• Protobuf 3.15.8 -> 3.18.0.
• SCIP 7.0.1 -> chủ.
• Googletest 1.8.0 -> 1.10.0.
• python: sử dụng warning trong cp_model.py (xem #2530).
• python: absl-py 0,11 -> 0,13.

CMake

• Chuyển đổi phiên bản tối thiểu bắt buộc là 3.14 -> 3.15 (xem #2528).
• Python: vượt qua mức tối thiểu bắt buộc đối với phiên bản 3.14 -> 3.18 (xem #2774).

Tạo

Ngừng sử dụng bản dựng dựa trên bản dựng, vui lòng di chuyển sang CMake hoặc Bazel để tạo bản dựng từ nguồn.

Java

• Cải thiện khả năng hoạt động của trình tải thư viện gốc (xem #2742).
• Khắc phục sự cố Trình thu gom rác của JVM khi mô hình định tuyến hoặc trình giải quy tắc ràng buộc bị loại bỏ (xem #2091) (xem #2466).
• Khắc phục sự cố gọi lại ghi nhật ký CP-SAT khi sử dụng nhiều worker (xem #2775).

CP-SAT

• Cải thiện độ mạnh của mã LNS (xem #2525).
• Cải thiện mã lập lịch: các phương thức nhà máy mới để tạo khoảng kích thước cố định, phỏng đoán tìm kiếm mới, cải thiện khả năng phân giải và các đoạn cắt tuyến tính mới.
• Cải thiện mã định tuyến: LNS chuyên dụng mới.
• Cải thiện trình kiểm tra mô hình. Giờ đây, công việc này còn táo bạo hơn, đặc biệt là bị tràn ngập tiềm năng.
• Cải thiện mã MIP: khả năng phân giải hiệu quả hơn và tăng cường khả năng giải quyết vấn đề cho tuyến tính của các mô hình MIP và CP.
• Cải thiện tính đa dạng của kết quả tìm kiếm. Khi sử dụng hơn 12 trình thực thi, hãy thêm trình thực thi dành riêng để cải thiện giới hạn dưới của mục tiêu.
• Thay đổi sang mã hoạt động song song: theo mặc định, giờ đây trình giải quyết sẽ sử dụng tất cả các lõi hiện có. Sử dụng num_search_parameters để chỉ định mức độ song song.
• Ngừng sử dụng SearchAllSolutions và SolveWithSolutionCallback.
• API Python: các hoạt động kiểm tra thông thường hơn khi sử dụng var == ... hoặc var != ... bên ngoài lệnh gọi model.Add().

Tháng 4 năm 2021

Thông báo về việc phát hành OR-Tools phiên bản 9.0

Chúng tôi đã phát hành OR-Tools v9.0. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Cập nhật phần phụ thuộc

• Cập nhật Abseil-cpp 20200923.3 thành LTS 20210324.1.
• Protobuf 3.15.3 được cập nhật lên 3.15.8.
• Java: jna-platform 5.5.0 cập nhật lên 5.8.0

Java

• OR-Tools hiện đã có trên Maven Central (xem com.google.ortools:ortools-java).

Sửa lỗi

• Cải thiện hoạt động đa luồng khi sử dụng trình phân giải CP-SAT (xem #1588).
• Khắc phục tính năng hỗ trợ trình bao bọc Python của std::vector&ltstd::string&gt (xem #2453).
• Sửa lại tính năng hỗ trợ CPLEX (xem #2470).

Thay đổi có thể gây lỗi đã biết

• Thêm quyền truy cập của trình ghi nhật ký trong Python, Java và .Net (xem #2245).
• Thay thế tất cả các loại tuỳ chỉnh của Google bằng các loại được cung cấp trong cstdint.

CP-SAT

• Ngừng sử dụng các phương thức SearchForAllSolutions(), SearchAllSolutions() và SolveWithSolutionCallback(). Thay vào đó, hãy sử dụng Solve().
• Cải thiện khả năng hỗ trợ cho các toán tử chuẩn Python. Điều này có thể làm hỏng mã hiện có không chính xác.

Tháng 3/2021

Thông báo về việc phát hành OR-Tools phiên bản 8.2

Chúng tôi đã phát hành OR-Tools v8.2. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Cập nhật phần phụ thuộc

• Cập nhật Abseil-cpp 20200923.2 lên LTS 20200923.3.
• Protobuf 3.14.0 được cập nhật lên 3.15.3.

Đang định tuyến

• Thêm RoutingModel.RegisterTransitMatrix()và RoutingModel.RegisterUnaryTransitVector().
• Thay đổi trả về của RoutingModel.AddVectorDimension() và RoutingModel.AddMatrixDimension() thành std::pair&ltint, bool&gt có int là mã nhận dạng của trình đánh giá phương tiện công cộng.

Tháng 12 năm 2020

Thông báo về việc phát hành OR-Tools phiên bản 8.1

Chúng tôi đã phát hành OR-Tools v8.1. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Cập nhật phần phụ thuộc

• Abseil-cpp 20200923 được cập nhật thành LTS 20200923.2.
• Protobuf 3.13.0 được cập nhật lên 3.14.
• Thêm tính năng hỗ trợ cho Gurobi 9.1.0
• Thả phần phụ thuộc GLog (được thay thế bằng một phương thức triển khai tuỳ chỉnh tuỳ thuộc vào các cờ abseil-cpp)
• Thả phần phụ thuộc Gflag (được thay thế bằng thành phần cờ abseil-cpp)

Sửa lỗi

• Khắc phục lỗi tính hai lần giấy phép nổi Gurobi (xem #2227).
• Sửa lỗi bản dựng cửa sổ (xem #2200).

Tháng 10 năm 2020

Thông báo về việc phát hành OR-Tools phiên bản 8.0

Chúng tôi đã phát hành OR-Tools phiên bản 8.0. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Các thay đổi về nền tảng

• Thêm tính năng hỗ trợ cho Python 3.9 (#2187)
• Đã bỏ hỗ trợ cho Python 3.5 (#2186) <!-- Đang chờ Microsoft dotnet-sdk hỗ trợ, có thể được tạo sau khi phát hành...
  • Thêm tính năng hỗ trợ cho Ubuntu 20.10 (#2188) -->
• Ngừng hỗ trợ Ubuntu 16.04 LTS (#2188)
• Ngừng hỗ trợ Ubuntu 19.10 (#2188)

Cập nhật phần phụ thuộc

• Cập nhật Abseil-cpp 20200225.2 lên LTS 20200923.
• Protobuf 3.12.2 được cập nhật lên 3.13.0.

Thay đổi có thể gây lỗi đã biết

• Hiện tại, tính năng Định tuyến và mã nguồn CP-SAT sử dụng một số tính năng của C++17. Cảnh báo: Nếu bạn cung cấp phiên bản abseil-cpp của riêng mình, vui lòng xác minh rằng phiên bản này cũng được tạo dựa trên C++17.
• Chữ ký MPSolver::CreateSolver đã được thay đổi. Đã bỏ đối số tên mô hình.

CMake

• Khắc phục việc tắt tính năng hỗ trợ SCIP khi sử dụng -DUSE_SCIP=OFF (xem #2129).
• Tích hợp các mẫu và ví dụ vào hệ thống xây dựng CMake. Lưu ý: bạn có thể tắt bằng cách sử dụng -DBUILD_SAMPLES=OFF và -DBUILD_EXAMPLES=OFF. lưu ý: bạn có thể tắt đối với một ngôn ngữ cụ thể bằng cách sử dụng -DBUILD_<LANG>_SAMPLES=OFF hoặc -DBUILD_<LANG>_EXAMPLES=OFF.
  • Với <LANG> trong số:
  • CXX,
  • PYTHON,
  • JAVA và
  • DOTNET.

Tạo

• Yêu cầu Make >= 4.3 (sử dụng hàm eval của Make).
• Yêu cầu CMake >= 3.14 (sử dụng tuỳ chọn --chi tiết của CMake).
• Thêm tuỳ chọn để tắt tính năng hỗ trợ SCIP bằng -DUSE_SCIP=OFF (xem #2134).
• Thêm tuỳ chọn để tắt tính năng hỗ trợ CLP và CBC bằng -DUSE_COINOR=OFF.

Java

• Giờ đây, các công cụ OR-Tools sẽ tạo ra các gói maven (xem #202).

Sửa lỗi

• Khắc phục bản dựng C++ và Python trên FreeBSD (xem #2126).
• Sửa lỗi bản dựng trong gỡ lỗi trên cửa sổ (xem #2077).
• Khắc phục sự cố kéo dài song song trên CP-SAT trên Windows (xem #2001, #2019).

Tháng 7 năm 2020

Thông báo về việc phát hành OR-Tools phiên bản 7.8

Chúng tôi đã phát hành OR-Tools v7.8. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Cập nhật phần phụ thuộc

• Gurobi 9.0.2 hiện đã được tích hợp sẵn trong các tệp nhị phân được tạo sẵn. Công cụ này sẽ tìm kiếm thư viện dùng chung gurobi 90 trong đường dẫn cài đặt mặc định của trình cài đặt Gurobi trên MAC OS X và Windows hoặc trong thư mục GUROBI_HOME.
• SCIP 7.0.1 hiện được tích hợp trong các tệp nhị phân tạo sẵn. Vui lòng đảm bảo tuân thủ giấy phép SCIP trước khi sử dụng.
• Thêm tính năng hỗ trợ cho Xpress Solver 8.9.0 không bắt buộc.

Trình giải tuyến tính

• Thêm phương thức LinearSolver::CreateSolver() tĩnh để đơn giản hoá việc kiểm tra khả năng hỗ trợ cho các phần phụ trợ trình giải toán tuyến tính tích hợp. Tính năng này hoạt động ở mọi ngôn ngữ.

Sửa lỗi

• Sửa lỗi bản dựng dựa trên CMake trên FreeBSD.
• Sửa lỗi sắp xếp CP-SAT trong quá trình tạo cảnh cắt tích luỹ.
• Khắc phục lỗi rò rỉ bộ nhớ của trình giải quyết tuyến tính trong trình bao bọc .Net.

Tháng 6 năm 2020

Thông báo về việc phát hành OR-Tools phiên bản 7.7

Chúng tôi đã phát hành OR-Tools v7.7. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Cập nhật phần phụ thuộc

• Cập nhật Abseil-cpp b832dce thành c51510d (LTS 20200225.2).
• Protobuf 3.11.4 được cập nhật lên 3.12.2.

Cải tiến và tính năng mới

• Trình giải CP-SAT hiện trả về Optimal thay vì Feasible trong mô hình mức độ thoả mãn (tức là không có mục tiêu).
• Thêm phương pháp phỏng đoán về bơm khả thi của cộng đồng MIP.

Sửa lỗi

Khắc phục sự cố đa luồng CP-SAT (xem #2005).

Tháng 4 năm 2020

Thông báo về việc phát hành OR-Tools phiên bản 7.6

Chúng tôi đã phát hành OR-Tools v7.6. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Tính năng mới của CP-SAT

Chúng tôi đã bổ sung các tính năng mới sau đây vào trình giải CP-SAT:

• Cải thiện tính năng quản lý mặt phẳng cắt cho LP.
• Công cụ gỡ lỗi.

Cập nhật phần phụ thuộc

Cập nhật Abseil-cpp 8ba96a8 thành b832dce (LTS 20200225).

Sửa lỗi

• Khắc phục lỗi CP-SAT UNSAT trong presolve (xem #1908).
• Sửa URL swigwin.exe.
• Khắc phục tính năng quản lý sơ đồ kiểu chữ SWIG cho Java và .Net.

Tháng 1 năm 2020

Thông báo về việc phát hành OR-Tools phiên bản 7.5

Chúng tôi đã phát hành OR-Tools v7.5. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Các thay đổi về nền tảng

• Thêm tính năng hỗ trợ cho Python 3.8 (#1719)
• Xoá tính năng biên dịch hỗ trợ từ các nguồn trên Visual Studio 2017 (#1852).
• Cập nhật dịch vụ hỗ trợ từ Centos 7 lên Centos 8 (#1827).

Cập nhật phần phụ thuộc

• protobuf phiên bản 3.10.0 được cập nhật lên phiên bản 3.11.2 (#1829).

Sửa lỗi

Các vấn đề sau đã được khắc phục trong OR-Tools phiên bản 7.5 (Để biết danh sách đầy đủ, hãy xem Mốc quan trọng phiên bản 7.5).

Cụ thể:

• Khắc phục lỗi tải Cấu trúc. Hãy xem #1421.
• Cấp quyền truy cập các phương thức GetStartIndex() và GetEndIndex() của RouteIndexManager (#1843).
• Khắc phục SWIG để xoá các phương thức bị lỗi (#1838, #1276).

Tháng 10 năm 2019

Thông báo về việc phát hành OR-Tools phiên bản 7.4

Chúng tôi đã phát hành OR-Tools v7.4. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Cải tiến và tính năng mới

• Trình giải quyết CP-SAT hiện sẽ kiểm tra các quy tắc ràng buộc không hỗ trợ các nguyên tắc thực thi. Trình kiểm tra mô hình sẽ trả về một lỗi trước khi giải quyết nếu quy tắc ràng buộc như vậy có giá trị thực thi cố định.
• Tìm kiếm cục bộ tốt hơn và nhanh hơn cho thư viện định tuyến.
• Trình giải tuyến tính hiện đã hỗ trợ phần mềm bên thứ ba là Xpress-MP. Bạn sẽ cần tạo lại công cụ OR-Tools từ nguồn để sử dụng công cụ này.
• Kiến trúc của gói NuGet đã được viết lại hoàn toàn. Cụ thể, phiên bản này hiện hỗ trợ khung .NET >= 4.5.2 trên các nền tảng Windows.

Nền tảng không dùng nữa

Như đã thông báo trong ghi chú phát hành tháng 7 năm 2019, OR-Tools không còn hỗ trợ Python 2.7 nữa.

Cập nhật phần phụ thuộc

Protobuf 3.9.0 đã được cập nhật lên 3.10.0.

Tháng 8 năm 2019

Thông báo về việc phát hành OR-Tools phiên bản 7.3

Chúng tôi đã phát hành OR-Tools v7.3. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Nền tảng không dùng nữa

Chúng tôi sẽ ngừng hỗ trợ Python 2.7 để phù hợp với việc Google chuyển sang Python 3. Đây sẽ là bản phát hành cuối cùng của OR-Tools hỗ trợ Python 2.7.

Cập nhật phần phụ thuộc

Protobuf 3.8.0 đã được cập nhật lên 3.9.0.

Sửa lỗi

Các vấn đề sau đã được khắc phục trong OR-Tools phiên bản 7.3. (Để xem danh sách đầy đủ, hãy xem Kanban v7.3).

Cụ thể:

• Khắc phục lỗi truyền init/int64 trên Java (#1448),
• Khắc phục việc kiểm tra presolve khi xử lý các điều kiện ràng buộc tích luỹ trống.

Tháng 7 năm 2019

Thông báo về việc phát hành OR-Tools phiên bản 7.2

Chúng tôi đã phát hành OR-Tools v7.2. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Các thay đổi về nền tảng

• Chúng tôi sẽ ngừng hỗ trợ Python 2.7 để phù hợp với việc Google chuyển sang Python 3. Sẽ có nhiều nhất một bản phát hành OR-Tools hỗ trợ Python 2.7.
• Ubuntu 18.10 được cập nhật lên Ubuntu 19.04.
• Thêm tính năng hỗ trợ biên dịch từ các nguồn trên Visual Studio 2019.
• Python 3.5 không còn được hỗ trợ trên Windows; vui lòng sử dụng Python 3.6 trở lên.

Nội dung cập nhật đối với phần phụ thuộc

• Bây giờ chúng tôi nhắm mục tiêu CBC 2.10.3.
• Bây giờ chúng tôi nhắm đến Protobuf 3.8.0.

CP-SAT

• Chúng tôi đã thực hiện nhiều điểm cải tiến cho tính năng tìm kiếm, tính song song và thư giãn tuyến tính.
• Thêm các API LinearExpr.Sum() và LinearExpr.ScalProd() trong Python.
• Ngừng sử dụng các API IntVar[].Sum() và IntVar[].ScalProd() trong C#.
• C++: Xoá SolveWithModel() vì đây là bản sao của SolveCpModel().
• Thêm các phương thức CpModel.addGreaterThan() và CpModel.addLessThan() vào API Java.

Trình giải tuyến tính

• Thêm MPSolver.SetHint() cho Python, Java và C# (được SCIP và Gurobi hỗ trợ).
• Thêm MPSolver.SetNumThreads() cho Python, Java và C# (được CBC, Gurobi và SCIP hỗ trợ).
• Viết lại hỗ trợ cho SCIP 6.0.1.

Tài liệu tham khảo

• Chúng tôi đã thêm hướng dẫn tham khảo dựa trên doxygen và pdoc3 cho tất cả ngôn ngữ và mọi công cụ (thuật toán, định tuyến, biểu đồ, biện pháp tuyến tính và CP-SAT). Xem Hướng dẫn tham khảo về công cụ OR.
• Tài liệu tham khảo đã hoàn chỉnh cho C++ (tất cả sản phẩm) và CP-SAT (C++, Python, Java).
• Chúng tôi đang xuất tất cả tài liệu C++ sang Python và Java.
• Còn thiếu tài liệu về .NET và chúng tôi không có giải pháp nào trong tương lai gần để cải thiện vấn đề này. Chúng tôi đã giữ lại vì nó vẫn cho thấy API có sẵn.

Tháng 5 năm 2019

Thông báo về việc phát hành OR-Tools phiên bản 7.1

Chúng tôi đã phát hành OR-Tools v7.1. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Các thay đổi đối với các phần phụ thuộc bắt buộc

OR-Tools v7.1 có các phần phụ thuộc mới và được cập nhật sau đây:

• glog phiên bản 0.3.5 được cập nhật lên phiên bản 0.4.0
• protobuf phiên bản 3.6.1 được cập nhật lên phiên bản 3.7.1
• Cbc 2.9.9 được cập nhật thành 2.10.1
• Cgl 0.59.10 được cập nhật thành 0.60.1
• Clp 1.16.11 được cập nhật lên 1.77.1
• Osi 0.107.9 được cập nhật thành 0.108.1
• CoinUtils 2.10.14 được cập nhật lên 2.11.1

Thay đổi về API CP-SAT

Các phần sau đây mô tả các thay đổi đối với API CP-SAT trong OR-Tools 7.1.

• Sử dụng Miền để tạo biến.
• Sử dụng Miền trong biểu thức tuyến tính.
• Sử dụng trình trợ giúp biểu thức tuyến tính.

Sử dụng Miền để tạo biến

Các ví dụ sau đây minh hoạ cách tạo biến số nguyên có các miền không liền kề. Thao tác này sẽ thay thế phương thức đã bị xoá NewEnumeratedIntVar(). Ở đây, biến x có thể là bất kỳ giá trị nào bằng 1, 3, 4 hoặc 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");

Biến cũng có thể được tạo bằng danh sách khoảng thời gian. Dưới đây, biến x bị ràng buộc ở mức 1, 2, 4, 5 hoặc 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");

Sử dụng Miền trong biểu thức tuyến tính

Các ví dụ sau đây minh hoạ cách giới hạn một biểu thức tuyến tính trên một miền không liền kề. Ở đây, biểu thức tuyến tínhLinear_expr được xác định trên 5, 6, 8, 9 và 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} }));

Sử dụng trình trợ giúp biểu thức tuyến tính

Các ví dụ sau đây minh hoạ cách sử dụng các phương thức trợ giúp để tạo tổng và tích vô hướng. Ở đây, chúng ta sẽ xem ví dụ về x + y == 20 và 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);

Tháng 3 năm 2019

Thông báo về việc phát hành OR-Tools phiên bản 7.0

Chúng tôi đã phát hành OR-Tools phiên bản 7.0. Để cập nhật phiên bản, hãy xem phần Cài đặt công cụ OR thích hợp.

Các thay đổi đối với nền tảng được hỗ trợ

OR-Tools phiên bản 7.0 không còn hỗ trợ các nền tảng sau:

• Visual C++ 2015
• Ubuntu 14.04
• Python 3.4 trên Linux

Nếu đang sử dụng một trong những nền tảng này, bạn vẫn có thể cài đặt OR-Tools v6.10.

Các thay đổi đối với các phần phụ thuộc bắt buộc

OR-Tools v7.0 có các phần phụ thuộc mới và được cập nhật sau đây:

• Mới: Abseil-cpp
• gflags 2.2.1 được cập nhật lên 2.2.2

Các phần sau đây mô tả các tính năng và điểm cải tiến mới trong OR-Tools 7.0.

• Trình quản lý chỉ mục mới dành cho các chương trình định tuyến
• Hỗ trợ VRP về tính năng đến lấy hàng và giao hàng
• Hỗ trợ các hàm lambda trong Java và C#

Trình quản lý chỉ mục mới dành cho các chương trình định tuyến

Trong phiên bản OR-Tools phiên bản 7.0, các chương trình định tuyến xe phải sử dụng RoutingIndexManager mới. Điều này đảm bảo rằng các chỉ mục tiêu chuẩn cho các vị trí nhất quán với các chỉ mục nội bộ mà trình giải quyết sử dụng, đồng thời giúp ngăn ngừa lỗi trong mã của bạn.

Lưu ý: Các chỉ mục vị trí chuẩn là từ 0 đến N-1, trong đó N là số vị trí (bao gồm cả kho). Vì lý do kỹ thuật, các chỉ mục vị trí nội bộ của trình giải toán có thể nằm ngoài phạm vi đó.

RoutingIndexManager mới yêu cầu một số thay đổi nhỏ đối với việc định tuyến các chương trình, như mô tả trong các phần sau:

• Đưa vào hoặc nhập RoutingIndexManager trong C++ và Java.
• Khai báo RoutingIndexManager
• Thêm RoutingIndexManager vào lệnh gọi lại thứ nguyên.
• Sử dụng RoutingIndexManager để in giải pháp.

Bao gồm/nhập RoutingIndexManager

Trong OR-Tools 7.0, các chương trình định tuyến trong C++ và Java phải bao gồm hoặc nhập RoutingIndexManager như minh hoạ trong các ví dụ dưới đây:

C++

#include "ortools/constraint_solver/routing_index_manager.h"

Java

import com.google.ortools.constraintsolver.RoutingIndexManager;

Các lệnh nhập Python và C# không thay đổi.

Khai báo RoutingIndexManager

Trong OR-Tools phiên bản 7.0, các chương trình định tuyến phải khai báo RoutingIndexManager và tạo mô hình định tuyến, như trong các ví dụ sau:

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);

Các đối số cho RoutingIndexManager là:

• Số lượng địa điểm
• Số lượng xe
• Chỉ số của kho hàng (vị trí bắt đầu và kết thúc của tất cả các xe)

Lưu ý: Trong các phiên bản trước, các đối số này được chuyển trực tiếp đến RoutingModel thay vì RoutingIndexManager.

Lệnh gọi lại

Trong OR-Tools phiên bản 7.0, bạn cần sử dụng RoutingIndexManager để tạo các lệnh gọi lại, chẳng hạn như lệnh gọi lại khoảng cách mà sau đó bạn sẽ truyền đến trình giải quyết. Các ví dụ sau đây minh hoạ cách tạo lệnh gọi lại khoảng cách.

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);

Phương thức IndexToNode sẽ chuyển đổi các chỉ mục vị trí nội bộ mà trình giải quyết sử dụng thành các chỉ mục chuẩn cho ma trận khoảng cách.

Thay vì truyền lệnh gọi lại trực tiếp đến trình giải toán, như trong các phiên bản trước, trong các phiên bản trước, trong phiên bản 7.0, bạn sẽ tạo transit callback index để tham chiếu đến lệnh gọi lại và truyền thông tin đó đến trình giải toán (trong trường hợp này là SetArcCostEvaluatorOfAllVehicles).

Kích thước

Các ví dụ sau đây minh hoạ cách tạo phương diện cho nhu cầu và công suất. Phương diện này dùng để giải quyết vấn đề về định tuyến xe có sức chứa.

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");

Giải pháp in

Trong OR-Tools phiên bản 7.0, bạn phải sử dụng RoutingIndexManager để hiển thị tuyến đường của xe trong một giải pháp. Các ví dụ sau đây minh hoạ cách in giải pháp bằng tất cả ngôn ngữ được hỗ trợ.

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);
    }

Hỗ trợ VRP về tính năng đến lấy hàng và giao hàng

OR-Tools phiên bản 7.0 hỗ trợ giải quyết các vấn đề về việc định tuyến xe (VRP) đối với hoạt động đến lấy hàng và giao hàng, trong đó mục tiêu là tìm tuyến đường ngắn nhất cho một nhóm xe đến lấy hàng và giao hàng tại nhiều vị trí. Bạn thiết lập vấn đề tương tự như VRP tiêu chuẩn, nhưng ngoài ra, bạn chỉ định một cặp (i, j) địa điểm cho từng mặt hàng, trong đó i là vị trí nhận hàng và j là vị trí trả xe. Trình phân giải định tuyến sẽ trả về tuyến đường của xe sao cho mỗi cặp (i, j), i và j ở trên cùng một tuyến đường và xe truy cập vào i trước j.

Để xem ví dụ giải quyết loại vấn đề này, hãy xem phần Định tuyến xe bằng cách đến lấy hàng và giao hàng.

Hỗ trợ các hàm lambda

OR-Tools v7.0 hiện đã hỗ trợ các hàm lambda trong C# và Java (ngoài C++ và Python, đã được hỗ trợ). Các hàm Lambda cung cấp một cách thuận tiện để xác định lệnh gọi lại trong các chương trình định tuyến. Tuy nhiên, bạn có thể xác định các lệnh gọi lại bằng các hàm tiêu chuẩn nếu cảm thấy mã của mình dễ đọc hơn.

Các ví dụ về lệnh gọi lại C# và Java ở trên minh hoạ cách xác định lệnh gọi lại bằng các hàm lambda.

Tháng 11 năm 2018

Thông báo ra mắt phiên bản v6.10

Chúng tôi đã phát hành OR-Tools phiên bản 6.10. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Các phần sau đây mô tả các tính năng và điểm cải tiến mới trong phiên bản 6.10.

Các lệnh đơn giản để xây dựng và chạy chương trình

Trong phiên bản 6.10, bạn có thể tạo và chạy chương trình bằng cách nhập các lệnh như sau:

make run SOURCE=relative/path/to/program.cc

, trong đó <var>relative/path/to</var> là đường dẫn đến thư mục chứa chương trình.

Lưu ý: Bạn không cần phải chỉnh sửa Makefile để chạy các chương trình nữa.

Để tạo một chương trình mà không cần chạy chương trình đó, hãy nhập:

make build SOURCE=relative/path/to/program.cc

Xem phần Bắt đầu sử dụng công cụ OR-Tools để biết hướng dẫn cụ thể về cách chạy chương trình theo ngôn ngữ.

Hỗ trợ SCIP 6.0.0

OR-Tools hiện hỗ trợ SCIP 6.0.0.

Tệp nhị phân

Các bản phân phối nhị phân đã được xây dựng bằng Java JDK 8 (JDK 7 cho Ubuntu 14.04).

Trình giải CP-SAT

Cập nhật API

• Thêm API CpModelBuilder C++ CP-SAT.

Ví dụ

Một số ví dụ đã được di chuyển.

• Di chuyển các ví dụ về cộng đồng sang examples/contrib.
• Di chuyển một số ví dụ sang ortools/<var>component</var>/samples (ví dụ: ortools/linear_solver/samples/simple_program.java)

Tháng 9 năm 2018

Công bố phát hành phiên bản v6.9

Chúng tôi đã phát hành OR-Tools phiên bản 6.9. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Phần phụ thuộc được cập nhật

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

Trình giải CP-SAT

• Các thay đổi có thể gây lỗi cho API – thông tin chi tiết đầy đủ tại đây:
• Đổi tên SolveWithSolutionObserver thành SolveWithSolutionCallback trong Python.

• Đổi tên NewSolution thành OnSolutionCallback trong lớp CpSolverSolutionCallback bằng Python. Ví dụ sau đây cho thấy cách mới để tạo lệnh gọi lại giải pháp trong 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

• Hiển thị StopSearch khi gọi lại giải pháp trong Python, Java và C#. Xem tài liệu tại đây.

• Hiển thị ModelStats và CpSolverResponseStats trong Python, Java và C#.

• Cải thiện tài liệu chuỗi tài liệu Python. Xem tài liệu tại đây.

• Thông tin cập nhật về cách triển khai giao diện trình giải toán và sổ tay nấu ăn bằng Java.

• Triển khai mô-đun.

• Thay đổi cách triển khai hồ chứa: thêm API bằng boolean để chỉ định các sự kiện rút/điền không bắt buộc.

Trình giải tuyến tính

• Hiển thị InterruptSolve trong Java và C#.

Trình giải toán CP

• Hiển thị đạo diễn SolutionCollector trong C#.

Python

• Thêm tính năng hỗ trợ cho Python 3.7.
• Khi biên dịch từ nguồn: ưu tiên python3 hơn python2 khi phát hiện python.

.NET

• Hoàn tất việc viết lại lớp .NET.
• Cung cấp gói Nuget Google.OrTools NetStandard 2.0 tương thích với Trình nhận dạng thời gian chạy win-x64, linux-x64 và osx-x64.
• Cung cấp một gói Nuget Google.OrTools.FSharp.
• Thêm tệp dự án cho tất cả các ví dụ về .NET.
• Cập nhật tất cả các ví dụ về tập lệnh F# (.fsx) thành dự án F# thông thường (.fs).
• Thêm tài liệu về cách tạo bản dựng gói .NET tại đây.

Nhựa flatzinc

• Thêm tính năng hỗ trợ cho các tập hợp trong bằng phẳng (sử dụng nosets.mzn).

Đóng góp

• Thêm tính năng hỗ trợ cho Binder. Nhờ có Kevin Mader.
• Đặt DecisionVisitor làm kiểu đạo diễn trong các liên kết Java. Nhờ có Jeremy Apthorp.

Tháng 7 năm 2018

Công bố phát hành phiên bản v6.8

Chúng tôi đã phát hành OR-Tools phiên bản 6.8. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Công bố trình giải CP-SAT

Trình giải CP-SAT là một trình giải quyết mới để lập trình quy tắc ràng buộc. Trình giải CP-SAT nhanh hơn trình giải CP gốc và nên được ưu tiên sử dụng cho các bài tập về CP.

Để xem các ví dụ sử dụng trình giải CP-SAT, hãy tìm trong thư mục examples (ví dụ) trên GitHub để tìm các tệp có _sat trong tên.

Trình phân giải CP ban đầu sẽ tiếp tục được duy trì trong một khoảng thời gian để hỗ trợ mã hiện có nhưng mã này sẽ không được dùng nữa.

Các lựa chọn mới cho trình giải CP-SAT

Sau đây là các lựa chọn mới cho trình giải CP-SAT trong bản phát hành này:

• Tìm kiếm khu vực lân cận cục bộ (LNS): Sử dụng tuỳ chọn SatParameters.use_lns để bật LNS.
• Tìm kiếm song song: Sử dụng tuỳ chọn SatParameters.num_search_workers để bật nhiều luồng trong một lượt tìm kiếm. Mỗi luồng có thể có các tham số khác nhau và các hạt giống ngẫu nhiên khác nhau. Điều này sẽ tối đa hoá tính đa dạng và xác suất để ít nhất một luồng tìm thấy giải pháp.

Cải thiện hiệu suất cho trình giải toán

Chúng tôi đã cải thiện hiệu suất cho trình phân giải CP-SAT và Glop.

Tháng 3 năm 2018

Công bố phát hành phiên bản v6.7

Chúng tôi đã phát hành OR-Tools phiên bản 6.7. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools installed (Cài đặt công cụ OR).

Cập nhật các phần phụ thuộc bắt buộc

• Protobuf 3.5.0 -> 3.5.1.

Tính năng khác

• Tái cấu trúc cơ sở để chuẩn bị tích hợp abseil-cpp.
• Sử dụng dịch vụ tích hợp liên tục (CI) của Travis CI và Appveyor.

SAT

• Cải thiện hiệu suất.
• Cải thiện API Python.
• Thêm API C# còn gọi là CpSolver.cs (THỬ NGHIỆM).

Nháy mắt

• Tái cấu trúc mã.
• Cải thiện hiệu suất.

Hỗ trợ CMake (THỬ NGHIỆM)

• Thêm tính năng hỗ trợ C++ HOẶC-Tools CMake.
• Có thể xây dựng OR-Tools dưới dạng một dự án CMake độc lập.
• Có thể kết hợp OR-Tools vào một dự án CMake hiện có.
• Thêm bản dựng dựa trên CMake HOẶC-Tools trên Python.
• Tạo gói Python (bánh xe) bằng CMake.

Đóng góp

• Sửa lỗi định nghĩa lại Winock2.h trên Windows. Nhờ có Florent Tollin de Rivarol.
• Thêm tính năng hỗ trợ F# (THỬ NGHIỆM). Nhờ có Matthew Moore. Lưu ý: chỉ dùng được với trình tạo Makefile.
• Thêm Hỗ trợ .NET Standard (THỬ NGHIỆM). Nhờ có Ziad El Malki. Lưu ý: chỉ dùng được với trình tạo Makefile.

Tháng 11 năm 2017

Công bố phát hành phiên bản v6.6

Chúng tôi đã phát hành OR-Tools phiên bản 6.6. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Cập nhật các phần phụ thuộc bắt buộc

• Protobuf lên 3.3.0 -> 3.5.0.
• gflags sang 2.2.0 -> 2.2.1.
• CBC 2.9.8 -> 2.9.9.
• Thêm mô-đun Python sáu (1.10) làm phần phụ thuộc bắt buộc cho Python.

Sửa lỗi

• Lấy yêu cầu tái cấu trúc tên #494. Thêm nhận xét cho IntelliSense trong một số trình chỉnh sửa. Nhờ có Matthew Moore.
• Yêu cầu lấy dữ liệu #516 Hướng dẫn cho tệp nhị phân độc lập F#. Nhờ có Matthew Moore.
• Cải thiện độ chính xác trong Glop.

Trình giải bài tập SAT

• Cải thiện trình giải toán SAT nội bộ, Khắc phục nhiều lỗi.
• Thêm một điều kiện ràng buộc VRP vào trình giải SAT, được liên kết với trình giải LP.
• Thay đổi trình quan sát giải pháp trong trình giải SAT để lấy CpSolverResponse làm tham số.
• Cải thiện việc sử dụng Glop trong SAT Solver.
• Tăng tốc kết nối SAT-LP.
• Thêm quy tắc ràng buộc Hồ sơ vào định dạng SAT cp_model protobuf.

SAT/Python

• Giới thiệu về SAT API bằng Python.
• Mã trong ortools/sat/python/cp_model.py.
• Thêm ví dụ trong examples/python/:
• assignment_sat.py
• assignment_with_constraints_sat.py
• code_samples_sat.py
• cp_is_fun_sat.py
• gate_scheduling_sat.py
• hidato_sat.py
• jobshop_ft06_sat.py
• nqueens_sat.py
• nurses_sat.py
• rcpsp_sat.py
• steel_mill_slab_sat.py
• worker_schedule_sat.py
• Thêm tính năng hỗ trợ cho sổ tay IPython.
• Các ví dụ về Python được xuất sang các sổ tay và có trong ví dụ/sổ tay.

Ví dụ

• Viết lại rcpsp_parser để sử dụng định dạng ProtoBuf nhằm lưu trữ vấn đề.
• Cải thiện trình phân tích cú pháp RCPSP.

Tháng 10 năm 2017

Công bố phát hành phiên bản v6.5

Chúng tôi đã phát hành OR-Tools phiên bản 6.5. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Thay đổi về nền tảng

• Mô-đun pypi py3-ortools đã được hợp nhất vào mô-đun ortools. Hiện chỉ có một mô-đun: "ortools".
• Định dạng chính cho các mô-đun Python này hiện là tệp bánh xe. Để cài đặt OR-Tools cho python từ pypi, chỉ cần chạy pip install ortools. Bạn cần cài đặt phiên bản pip gần đây (>= 9.0.1). Thao tác này sẽ lấy bản phát hành mới nhất (v6.5).

Lỗi được khắc phục

Tệp jar protobuf hiện được tạo bản dựng chính xác với các lớp đã biên dịch.

Ví dụ mới

• Chúng tôi đã đóng góp thêm nhiều ví dụ về F# cho thư mục example/fsharp (Một lần nữa, xin cảm ơn Matthew Moore).
• Các ví dụ về Java MIP cũng đã được đóng góp (Cảm ơn Darian).

Tháng 9 năm 2017

Công bố phát hành phiên bản v6.4

Chúng tôi đã phát hành OR-Tools phiên bản 6.4. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Thay đổi về nền tảng

• Các mô-đun Pypi trên nền tảng Linux hiện được phân phối dưới dạng tệp bánh xe bằng cách sử dụng thẻ nhiều linux1. Nhờ có Federico Ficarelli. Với thay đổi này, chúng tôi đã đẩy lùi các mô-đun mỗi linux được giới thiệu trong bản phát hành tháng 7 năm 2017.

Tính năng mới

• Cải thiện phương thức điều chỉnh theo tỷ lệ dùng bên trong GLOP.
• Sửa việc gói trình đánh giá trong thư viện định tuyến C#. Nhờ có DevNamedZed.
• Cải thiện hiệu suất của phương pháp giải quyết phẳng cho các mô hình lớn.
• Sử dụng SAT được hỗ trợ cho phẳng theo mặc định.
• Cải thiện hiệu suất của phương pháp dựa trên cốt lõi dành cho trình giải toán.
• Sửa lỗi thuật toán gán tuyến tính bị lỗi không chính xác.
• Thêm ví dụ về F# trong ortools/examples/fsharp.
• Xoá hoạt động kiểm tra các hình phạt tích cực trong thư viện định tuyến.

Tháng 8 năm 2017

Công bố phát hành phiên bản v6.3

Chúng tôi đã phát hành OR-Tools phiên bản 6.3. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Tệp tải xuống mới

Bạn hiện có thể tải các tệp bánh xe Python cho Linux xuống trang phát hành OR-Tools, cùng với các phiên bản mới nhất của tất cả các tệp đã tải xuống.

Máy giải kẽm mini

Phiên bản này chứa mã sat và flatzinc cuối cùng được gửi cho Thử thách Minizinc 2017.

Tháng 7 năm 2017

Công bố phát hành phiên bản v6.2

Chúng tôi đã phát hành OR-Tools phiên bản 6.2. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Thay đổi về nền tảng

• Chúng tôi hiện hỗ trợ nhiều bản phân phối nhị phân Linux (Ubuntu 14.04, 16.04, 17.04, CentOS 7, Debian 9).
• Các mô-đun Pypi trên nền tảng Linux hiện bao gồm một thẻ mô tả bản phân phối (ubuntu-14.04, ubuntu-16.04, ubuntu-17.04, centos-7, debian-9).

Tính năng mới

Chúng tôi đã thêm tính năng hỗ trợ cho Docker để tạo các cấu phần phần mềm Linux. Hãy chuyển đến or-tools/tools/docker và xem Makefile để xem các mục tiêu có thể có (make archive, make pypi và make pypi3).

Các lệnh này sẽ tạo một thư mục con export và thêm các cấu phần phần mềm nhị phân trong đó.

Tháng 6 năm 2017

Công bố phát hành phiên bản v6.1

Chúng tôi đã phát hành OR-Tools phiên bản 6.1. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Thay đổi về nền tảng

• Visual Studio 2017 được hỗ trợ; Visual Studio 2013 không còn được hỗ trợ.
• Hỗ trợ macOS phiên bản 10.9 trở lên.

Tính năng mới

Chúng tôi đã thêm một định dạng protobuf mới cho trình giải CP-SAT. Hãy xem ortools/sat/cp_model.proto để xác định mô hình và xem ortools/sat/cp_model_solver.h để giải bài tập.

Sửa lỗi

Vấn đề #420: Chúng tôi đã khắc phục thuộc tính __version__ bị thiếu trên các mô-đun pypi Python trên tất cả nền tảng.

Tháng Năm năm 2017

Công bố phát hành phiên bản v6.0

Chúng tôi đã phát hành OR-Tools phiên bản 6.0. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Cấu trúc mới của thư mục trong C++

Chúng tôi đã thay đổi cấu trúc nguồn/bao gồm của Công cụ OR khi sử dụng C++. Mục tiêu là cung cấp cách đóng gói tốt hơn các tệp C++. Thư mục này cũng có lợi ích là điều chỉnh cấu trúc thư mục C++ và Python.

• src/ đổi tên thành ortools/.
• Tất cả các lệnh #include trong tệp C++ hiện đã được thêm tiền tố ortools. #include "constraint/constraint_solver.h" đổi tên thành #include "ortools/constraint/constraint_solver.h".

Tính năng mới

• Hỗ trợ của Bazel. Giờ đây, bạn có thể tạo OR-Tools bằng bazel (công cụ xây dựng của Google). Phiên bản này hoạt động trên Linux và Mac OS X. Sau khi tải Bazel phiên bản 0.4.5 trở lên, hãy thay đổi thư mục thành or-tools và tạo các ví dụ: bazel build examples/cpp/....

Đang định tuyến

Chúng tôi đã triển khai tính năng hỗ trợ nghỉ giải lao (ví dụ: thời gian ngừng hoạt động của xe do người lái xe ăn trưa) trong thư viện định tuyến. Tính năng này được thể hiện trong ví dụ về cvrptw_with_breaks.cc.

Hỗ trợ SCIP

Trình bao bọc trình giải tuyến tính hiện đã hỗ trợ SCIP 4.0. Bây giờ, bạn cần tạo SCIP trước, sau đó cho các công cụ hoặc công cụ biết rằng bạn sẽ sử dụng SCIP đó. Bạn có thể xem hướng dẫn tại đây.

Hỗ trợ GLPK

Chúng tôi cũng đã thay đổi cách tạo bản dựng bằng GLPK. Hãy xem ở đây.

Dọn dẹp

• Chúng tôi đã xoá toàn bộ việc sử dụng hash_map và hash_set trong cơ sở mã C++ vì chúng không được dùng nữa. Các thuộc tính này được thay thế bằng un nâng thứ tự_map và không sắp xếp theo thứ tự từ STL.
• Dọn dẹp các tệp tạo tệp C# với sự cho phép của Michael Powell.

Tháng 1 năm 2017

Công bố phát hành phiên bản v5.1

Chúng tôi đã phát hành OR-Tools phiên bản 5.1. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Tính năng mới

Đang cài đặt

• Giới thiệu các quy trình đơn giản hơn để cài đặt Công cụ OR, từ bản phân phối nhị phân hoặc từ mã nguồn. Vui lòng xem phần Cài đặt OR-Tools từ tệp nhị phân hoặc Cài đặt OR-Tools từ nguồn để biết thêm thông tin.

Đang định tuyến

Triển khai một thuật toán để tính toán giới hạn dưới Đây là Giới hạn dưới cho các Bài toán đối xứng về Nhân viên bán hàng du lịch. Điều này cho phép bạn tính toán giới hạn trên so với khoảng cách giữa chi phí của một giải pháp có khả năng không tối ưu và chi phí của giải pháp tối ưu.

• Thêm một phương thức mới vào thư viện định tuyến xe, RoutingModel::SetBreakIntervalsOfVehicle. Phương thức này cho phép bạn thêm các khoảng thời gian break – khoảng thời gian khi xe không thể thực hiện bất kỳ nhiệm vụ nào (chẳng hạn như di chuyển hoặc truy cập vào một nút). Để xem ví dụ sử dụng tuỳ chọn này, hãy xem bài viết cvrptw_with_breaks.cc

Lập lịch

• Thêm tính năng hỗ trợ nhiều định dạng dữ liệu hơn trong trình phân tích cú pháp cho Thư viện lập lịch dự án.

Trình giải sự cố

• Giờ đây, quy tắc ràng buộc tích luỹ của trình giải SAT chấp nhận các khoảng thời gian không bắt buộc, được tạo bằng phương thức NewOptionalInterval. Để xem ví dụ, hãy truy cập vào https://github.com/google/or-tools/blob/master/examples/cpp/rcpsp_sat.cc.
• Bây giờ, bạn có thể giải quyết Max-SAT (vấn đề về mức độ hài lòng tối đa bằng cách chỉ định mục tiêu làm tổng các giá trị cố định có trọng số). Bạn không cần phải tạo một biến số nguyên trung gian nữa.

Điểm cải tiến về hiệu suất

• Trình giải SAT – Cải thiện hiệu suất của trình giải quyết SAT, đặc biệt là đối với quy tắc ràng buộc tích luỹ.
• Trình giải toàn cầu – Cải thiện độ mạnh về mặt số của trình giải Glop. Hiện nay, công cụ này cung cấp các giải pháp chính xác hơn cho các bài toán số khó.
• Dung dịch flatzinc
• Cải thiện đáng kể hiệu suất của phần phụ trợ Sat cho trình phiên dịch flatzinc.
• Đơn giản hoá giao diện flatzinc C#. Để xem ví dụ về giao diện mới, hãy truy cập https://github.com/google/or-tools/blob/master/examples/csharp/csfz.cs.

Sửa lỗi

• Việc sử dụng phương pháp phỏng đoán PathCheapestArc trong các mô hình định tuyến có một xe và các điều kiện ràng buộc bên hông đôi khi khiến trình giải quyết chạy quá lâu. Chúng tôi đã khắc phục vấn đề này bằng cách xem xét đúng các điều kiện ràng buộc bên.
• Trong Java, trình giải quyết tuyến đường đôi khi sẽ gặp sự cố khi giải quyết các vấn đề về định tuyến xe. Vấn đề này đã được khắc phục trong bản phát hành mới nhất.

Tháng 11 năm 2016

Công bố phát hành phiên bản v5.0

Chúng tôi đã phát hành OR-Tools phiên bản 5.0. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Ví dụ về chạy

• Giới thiệu các mục tiêu theo ngôn ngữ cụ thể giúp bạn dễ dàng biên dịch và chạy chương trình, cũng như các ví dụ đi kèm với OR-Tools.

Thứ Bảy

• Thêm tính năng hỗ trợ lập trình ràng buộc.
• Triển khai các quy tắc ràng buộc diffn, tích luỹ , mạch và mạch con.
• Triển khai trình kiểm tra quá tải trên cơ sở Thuật toán lọc năng lượng tối đa dành cho ràng buộc tích luỹ rời rạc.
• Triển khai tất cả bộ truyền tải nhất quán có giới hạn khác nhau để triển khai tính năng lan truyền tốt hơn cho quy tắc ràng buộc AllVarious.

FlatZinc

• Triển khai trình giải SAAT cho các bài toán FlatZinc.

Trình giải quyết ràng buộc

• Đã triển khai các quy tắc ràng buộc sau :
• atMost: Đặt giới hạn trên cho số lượng biến bằng với một giá trị nhất định.
• MakePathPrecedenceConstraint và MakePathTransitPrecedenceConstraint: Triển khai quy tắc ràng buộc ưu tiên cho một tập hợp các cặp.

Đang định tuyến

• Triển khai AddAtSolutionCallback. Đây là lệnh gọi lại được gọi mỗi khi tìm thấy một giải pháp trong quá trình tìm kiếm.
• Xoá các hàm khởi tạo không có kho hàng RoutingModel. Giờ đây, bạn bắt buộc phải chỉ định ít nhất một kho hàng trong mô hình định tuyến.

Tháng 9 năm 2016

Công bố phát hành phiên bản v4.4

Chúng tôi đã phát hành OR-Tools phiên bản 4.4. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Thứ Bảy

• API lập lịch mở rộng và các ví dụ đã sửa đổi (Weight_tardiness_sat và jobshop_sat) để sử dụng API này.

Biểu đồ

• Thêm các đặc điểm biến lặp vào lớp Biểu đồ.

Phân phối OR-Tools

• Gói Nuget được hỗ trợ lại.

Tháng 8 năm 2016

Công bố phát hành phiên bản v4.3

Chúng tôi đã phát hành OR-Tools phiên bản 4.3. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Trình giải quyết ràng buộc

• Triển khai phương thức NotBetween để ràng buộc một biến nằm ngoài một khoảng thời gian nhất định.

định tuyến

• Thêm quy trình phân tích cú pháp của mô hình để kiểm tra các quy tắc ràng buộc hiện có của NotMember như trong ví dụ này và sử dụng chúng trong bộ lọc tìm kiếm cục bộ.
• Đã thêm chế độ phân tích tìm kiếm cục bộ.
• Khắc phục vấn đề khi chuyển nhà.

Trình giải tuyến tính

• Sửa tính năng báo cáo trạng thái SCIP.

Thứ Bảy

• Triển khai phương thức SolveWithPresolve để đơn giản hóa việc sử dụng trình giải quyết trước SAT.
• Các tiện ích tìm kiếm được nhóm lại trong src/sat/util.h|cc.
• Các quy tắc ràng buộc đối với việc lập lịch biểu SMT (Tạo mệnh đề lazy) đã triển khai: hãy xem jobshop_sat.cc và weighted_tardiness_sat.cc.

Nháy mắt

• Cải thiện hiệu suất bằng cách khai thác độ thư giãn ở nhiều giai đoạn tính toán hơn.

Nhựa flatzinc

• Khắc phục các lỗi do thử thách minizinc phát hiện.

Lp_data

• Tiếp tục đơn giản hoá các mẫu trong các biến lặp.

Phân phối OR-Tools

• Theo mặc định, các tập hợp C# hiện được đặt tên mạnh mẽ.
• Đã nâng cấp lên Protobuf3.0.0.
• Thêm một tập lệnh Python để kiểm tra các phần phụ thuộc lưu trữ OR-Tools.

Tháng 7 năm 2016

Công bố phát hành phiên bản v4.2

Chúng tôi đã phát hành OR-Tools phiên bản 4.2. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Trình giải quyết ràng buộc (định tuyến)

• Giờ đây, bạn có thể xác định một trường hợp phân biệt bằng lượng số. Đây là số lượng nút tối đa có thể hoạt động trong sự phân biệt này. Ví dụ: nếu bạn thêm một phép phân tách có n nút và một lượng số là k, thì k nút trong số n nút được phép hoạt động. Bạn có thể sử dụng định nghĩa mới của AddDisjunction để thực hiện việc này.
• Thêm tính năng hỗ trợ cho nhiều phân biệt cho mỗi nút. Ví dụ: giờ đây, bạn có thể thêm nút, N1, vào nhiều phân biệt (D1..Dm). Điều này giúp tăng cơ hội hoạt động trong bất kỳ mạng nào trong số đó. Giới thiệu một thuật toán tìm kiếm định tuyến nhanh hơn cho các vấn đề liên quan đến cửa sổ thời gian bị tạm ngưng.
• Thêm các tham số giải quy tắc ràng buộc vào các tham số mô hình định tuyến và log_search để định tuyến tham số tìm kiếm.
• Thuật toán tìm kiếm cục bộ hoạt động nhanh hơn nhờ khả năng giải quyết các vấn đề liên quan đến các khoảng thời gian không liền mạch. Hãy xem ví dụ về cvrp_disjoint_tw.cc để biết thêm thông tin.

Glop (tối ưu hóa tuyến tính)

• Ra mắt thuật toán Simplex nhanh hơn.

Phân phối OR-Tools

• Một tệp lưu trữ cho mỗi nền tảng, thay vì từng tệp lưu trữ riêng lẻ cho mỗi C++, Java và .Net. Các tệp lưu trữ Python vẫn được lưu trữ trên pypi.
• Trên pypi, chúng tôi đã chuyển sang mô-đun bánh xe (.whl) trên Mac OS X và Windows. Giới thiệu giản đồ đánh số MAJOR.MINOR. Những số này được dùng tên kho lưu trữ, phiên bản được lưu trữ trong thư viện chia sẻ Mac OS X, mô-đun Python, cụm .NET. Phiên bản đầu tiên chúng tôi phát hành là theo giản đồ này là v4.2

Tháng 6 năm 2016

Công bố phát hành phiên bản v2016-06

Chúng tôi đã phát hành phiên bản OR-Tools v2016-06. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Trình giải quyết ràng buộc

• Xoá hầu hết các thực thể của lệnh gọi lại (src/base/callback.h) khỏi thư viện CP.
• Thêm NotmemberCt (biến không thể thuộc về một tập hợp các khoảng thời gian).

Thư viện định tuyến

• THAY ĐỔI KHÔNG TƯƠNG TÁC: Để chỉ định sức chứa của xe trong AddDimensionWithVehicleCapacity, giờ đây, bạn cần truyền một mảng (một vectơ trong c++) thay vì một lệnh gọi lại.

TỔNG QUAN

• Thay đổi cách biểu diễn nội bộ của ma trận thưa.
• Cải thiện hiệu suất

Biểu đồ

• Viết lại thuật toán Dijkstra và Bellman-Ford để thay thế lệnh gọi lại bằng std::function (C++).
• Thay đổi API của nhiều cách triển khai biểu đồ khi lặp lại qua các vòng cung và nút.

Thứ Bảy

• Xoá phương thức cốt lõi không dùng đến (Nút độ phân giải).
• Thêm người viết drat để kiểm tra bằng chứng về sự không hài lòng.
• Thêm bộ tiền xử lý.

Bop

• Thêm các vùng lân cận mới.

Ví dụ

• c++: loại bỏ trình đọc fileline trong ví dụ.
• dữ liệu: Thêm bài toán về việc lập lịch biểu một máy.

Tài liệu

• Vui lòng xem tài liệu mới.

Tháng 4 năm 2016

Công bố phát hành phiên bản v2016-04

Chúng tôi đã phát hành phiên bản OR-Tools v2016-04. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Phần phụ thuộc được cập nhật

• Dùng protobuf thay vì cờ trong Thư viện lập trình quy tắc ràng buộc và thư viện định tuyến. Hãy truy cập vào http://or-tools.blogspot.fr/2016/02/heads-up-upcoming-incompatibility-in.html để biết thông tin chi tiết.

Tháng 12 năm 2015

Công bố phát hành phiên bản v2015-12

Chúng tôi đã phát hành phiên bản OR-Tools v2015-12. Để cập nhật phiên bản, hãy xem phần phù hợp trong phần OR-Tools Inspection (Cài đặt công cụ OR).

Trình giải quyết ràng buộc

• Khả năng tương thích giới hạn trên Công cụ tìm kiếm vùng lân cận trên diện rộng trong trình giải CP (xem examples/cpp/ls_api.cc, examples/python/pyls_api.py, examples/csharp/csls_api.cs và examples/com/google/ortools/sample/LsApi.java để xem API mới).
• Xoá gói Python. Hỗ trợ quyết định tuỳ chỉnh trong trình giải CP (xem examples/test/test_cp_api.py để xem API trong thực tế).
• Các cải tiến và sửa các lỗi khác nhau.

Tháng 9 năm 2015

Công bố bản phát hành đầu tiên trên github.

Từ giờ trở đi, tệp sẽ được lưu trữ ở đó.

Nhựa flatzinc

• Thêm bản lưu trữ nhị phân cho trình thông dịch phẳng (xem www.minizinc.org).
• Chứa một số bản sửa lỗi cho phiên bản dùng trong thử thách này.