Skip to content

Releases: google/or-tools

v9.11

13 Sep 14:35
Compare
Choose a tag to compare

Platforms

  • Add Almalinux 9 support.
  • Add Rockylinux 9 support.
  • Add Ubuntu 24.04 LTS support.

Dependencies

C++

  • abseil-cpp: 20240722.0.
  • HiGHS: 1.7.2.
  • googletest: v1.15.2.
  • Add support for Gurobi 11.0.3

Java

  • maven 3.6+

Algorithms

  • Add experimental set_cover python binding.

CP-SAT

  • Improve no_overlap_2d, linear propagation

What's Changed

New Contributors

Known issues

  • CP-SAT callbacks in Python, Java, .NET can slow down search performance a lot as it is possible that search will continue until the time limit is crossed even as the problems has been closed before.

Full Changelog: v9.9...v9.11

v9.10

08 May 08:27
Compare
Choose a tag to compare

Dependencies

  • ZLIB 1.3.1.

  • abseil-cpp 20240116.2.

  • Protobuf v26.1.

  • Re2 2024-04-01.

  • HiGHS v1.7.0.

  • Scip v900.

  • Add support for Gurobi 11.

C++ Changes

  • replace std::vector& with absl::Span.
  • replace const std::string& with absl::string_view.
  • Improve XPRESS support.
  • Remove the command line flags --logtostderr which was a no-op since the implementation of the logging module in abseil. Please use --stderrthreshold=0 instead.

Algorithms

  • more work on set covering.

CP-SAT

  • Improve propagation of no_overlap_2d
  • Fix crash in no_overlap_2d Large Neighborhood Search
  • Improve core based search
  • Preserve hints during presolve
  • Improve lb_tree_search
  • Improve python typing
  • Improve communication between shared_tree workers
  • Add best bound callback
  • Improve presolve (in particular lin_max)
  • Merge the linear propagator and the difference propagator
  • Change pseudo-cost implementation to be closer to the literature
  • Add missing int_mod evaluation for violation_ls and feasibility_jump

Known Issue

  • [bazel] Highs 1.7.0 math_opt tests failed #4203
  • [python ]MathOpt solver_test timeout on macOS #4209
  • [windows] Lots of report of crashes (#4224, #4225, #4226, #4227). Make sure visual studio is fully updated.
  • [java] Protobuf was updated to v26.1. On the java platform, the corresponding package (5.26.1) in incompatible with 3.x.
  • [bazel] Building on Windows against MSVC is not working #4241.

Full Changelog: v9.9...v9.10

v9.9

07 Mar 13:33
Compare
Choose a tag to compare

Dependencies

  • abseil-cpp 20240116.1.
  • re2 2024-02-01.
  • Protobuf v25.3.
  • Scip v810.
  • pybind11 v2.11.1.
  • googletest 1.14.0.

C++ Changes

  • use of absl::Span instead of std::vector.
  • replace const std::string& with absl::string_view.
  • use of absl log.

CP-SAT

  • Improvements to no_overlap_2d algorithms.
  • rewrite python API to be pep8 compliant. model.AddBoolOr -> model.add_bool_or
  • Improve the linear propagator code.
  • Use the ~ operator in C++ and Python for the negation of a literal.

Linear Solver

  • make XPRESS support using a dynamic load (like gurobi support)

Math Opt

  • Sync with google3
  • Add c++ and python support in CMake based build.
  • Add math_opt in Python wheel package
  • Enable few C++ tests with bazel based build.

Known Issue

  • Python windows wheel package are 108Mb so we can't upload them to pypi yet.
    note: a file limite request has been filled (pypi/support#3714)

  • Build on Ubuntu 20.04 LTS failed -> no archives available for this OS...
    dev note: looking at the trace of the release process...

    $ cd tools/docker
    $ make amd64_ubuntu-20.04_cpp_build
    ...
    In file included from /root/or-tools/ortools/graph/dag_constrained_shortest_path.cc:14:
    /root/or-tools/ortools/graph/dag_constrained_shortest_path.h:18:10: fatal error: concepts: No such file or directory
       18 | #include <concepts>
          |          ^~~~~~~~~~
    

    This means or-tools source code is poissed with C++20 headers since google3 now allow C++20...
    => Will have no choice but to drop C++17 support in the short term as an internal component of google3 code base.

What's Changed

  • build(deps): bump urllib3 from 2.0.4 to 2.0.7 in /bazel by @dependabot in #3988
  • Fix memory leaks in file::GetContents and file::SetContents by @pjh in #4011
  • build(deps): bump jupyter-server from 2.7.2 to 2.11.2 in /bazel by @dependabot in #4014
  • Improve the Xpress interface and add dynamic loading of the Xpress library by @sgatto in #3966
  • improve performance of Xpress interface and fix bug by @sgatto in #4030
  • build(deps): bump jinja2 from 3.1.2 to 3.1.3 in /bazel by @dependabot in #4049
  • Include LICENSE file in Python distribution by @chrisjbremner in #4048

New Contributors

Full Changelog: v9.8...v9.9

v9.8

15 Nov 19:18
Compare
Choose a tag to compare

Platforms

  • Add Python 3.12 support.
  • Add Ubuntu 23.10 support.

Dependencies

  • abseil-cpp 20230802.1.
  • Protobuf v25.0.
  • re2 2023-11-01.
  • SCIP v804.

Linear Solver

  • Port ModelBuilder to .Net.
  • Rename LogCallback to MbLogCallback to avoid collision with SAT LogCallback.
  • Extend ModelBuilder API:
    • Add indicator constraints.
    • Add hinting support.
    • Add model cloning.

Math Opt

  • Deep rework.

Routing

  • Add ROUTING_OPTIMAL status.
  • Make RoutingModel non copyable nor movable.
  • Fix some infinite loop in local search operators.
  • Add a PickupDeliveryPosition internal struct.
  • Add IsPickup() and IsDelivery() methods.

SAT

  • Reduce memory footprint for large model.
  • Improved scheduling search.
  • add packing_precedences_lns.
  • optimize and fix feasibility jump.
  • optimize linear presolve and better presolve logging.
  • Improve presolve for int_abs, int_mod, int_prod and lin_max.
  • Improve Panda support
  • Few bug fix.

Troubleshoot for Distro Maintainers

issue re2::StringPiece

$SRC_DIR/ortools/lp_data/lp_parser.cc: In function 'absl::lts_20230802::StatusOr<operations_research::glop::ParsedConstraint> operations_research::glop::ParseConstraint(absl::lts_20230802::string_view)':
$SRC_DIR/ortools/lp_data/lp_parser.cc:365:20: error: cannot convert 'absl::lts_20230802::string_view*' {aka 'std::basic_string_view<char>*'} to 'operations_research::glop::{anonymous}::StringPiece*' {aka 're2::StringPiece*'}
  365 |       ConsumeToken(&constraint, &consumed_name, &consumed_coeff);
      |                    ^~~~~~~~~~~
      |                    |
      |                    absl::lts_20230802::string_view* {aka std::basic_string_view<char>*}

answer: You need to bump re2 to at least 2023-06-01 (re2::StringPiece become an alias to absl::string_view)
src: google/re2@49d776b

issue operator<<

$PREFIX/include/absl/log/internal/log_message.h:289:17: error: no match for 'operator<<' (operand types are 'std::ostream' {aka 'std::basic_ostream<char>'} and 'const operations_research::sat::CpSolverResponse')
  289 |   view.stream() << log_internal::NullGuard<T>().Guard(v);
      |   ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

answer: You need to bump Protobuf to at least v23.3 (protobuf depends on abseil-cpp)

issue absl::int128

$SRC_DIR/ortools/sat/cuts.cc:79:36: error: no matching function for call to 'StrCat(const char [13], const absl::lts_20230802::int128&, const char [2])'
   79 |   std::string result = absl::StrCat("CutData rhs=", rhs, "\n");
      |                        ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

answer: : You need to bump abseil-cpp to at least 20230802.1 (abseil-cpp will provide a int128::toString())
src: abseil/abseil-cpp@34eb767

What's Changed

New Contributors

Full Changelog: v9.7...v9.8

v9.7 (2023/08)

08 Aug 15:24
ed8db90
Compare
Choose a tag to compare

Platforms

  • Drop Fedora [33,36] (EOL).
  • Drop Centos 8.
  • Drop Debian 10.
  • Drop Ubuntu 18.04 LTS.
  • Drop Python 3.7 support (EOL).
  • Disable .Net Core 3.1 (EOL)

Dependencies

  • ZLIB 1.2.13.
  • abseil-cpp 20230125.3.
  • Protobuf v21.12 -> v23.3.
  • re2 2023-07-01.
  • googletest v1.13.0.
  • Java JNA 5.12.1 -> 5.13.0.

Bazel

  • Require Bazel 6+.
  • Update rules, fix build.
    • rules_jvm_external: 4.5 -> 5.2
    • contrib_rules_jvm: 0.9.0 -> 0.9.0
    • rules_python: 0.20.0 -> 0.23.1

Graphs

  • Deep Rework.

Model Builder python

  • Allow use of Pandas dataframes and series to create variables.
  • Complete typing information

PDLP

  • various update.

CP-SAT

  • Performance improvements. (feasibility_jump, lin_max)
  • Improve cut management
  • New objective_shaving_search worker dedicated to improving the lower bound of the objective (when minimizing)
  • Typing annotations for the python cp_model.py
  • Experimental partial support for pandas in cp_model.py
  • Experimental local search violation based workers:
    • enabled with parameters: num_violation_ls:xxx
    • optimized for linear model (linear, bool_or, bool_and, at_most_one, exactly_one)
    • works correctly with lin_max, product, division
    • supports no_overlap, cumulative, circuit, routes
    • disabled with no_overlap_2d
    • recommended number of ls workers: num_workers -> num_violation_ls (8, 1), (16, 2) (24, 3), (32, 4)

What's Changed

New Contributors

Full Changelog: v9.6...v9.7

v9.6 (2023/03)

13 Mar 09:18
Compare
Choose a tag to compare

Platforms

  • Add Fedora 37 support.
  • Add Fedora 38 support.
  • Drop Python 3.6 (not supported by protobuf).
  • Drop Python 3.7 on MacOS (not supported by scipy).
  • Add net7.0 support
  • Drop netcore3.1 in nuget .org packages

Dependencies

  • SCIP v801 -> v803 (note: now SCIP use an OSI compatible license)
  • abseil 20220623.1 -> 20230105.0
  • Protobuf v21.5 -> v21.12
  • SWIG 4.1.1
  • Java JNA 5.11.0 -> 5.12.1

PDLP

  • Add python wrapper.

CP-SAT

  • Performance improvements.

GLOP

  • Tweak presolve.

ModelBuilder

  • Python: Improve numpy support.

Bazel

  • Add pybind11 support.
  • Add java wrapper support.

Routing

  • Few improvements (local search)

Known Issues:

  • CP-SAT: Ignoring pseudo_costs subsolver returns Invalid parameters. (#3706)
  • Maven ortools-java package only depends on ortools-linux-x86-64 and thus will only work on linux...

v9.5 (2022/11)

28 Nov 14:31
Compare
Choose a tag to compare

Platforms

  • Add Debian-SID support (#3457).
  • Add Fedora 35 support.
  • Add Fedora 36 support.
  • Add Ubuntu 22.10.
  • Drop Python 3.6 macOS x86_64 (Intel) .
  • Add Python 3.11 wheel (#3515).

CP-SAT

  • Presolve improvements: max(array), Boolean constraints, linear constraints.
  • Interleaved search should be deterministic in parallel.
  • Linear cuts: cleanup square and int_prod cuts; rewrite cut pipeline.
  • Fingerprint input model and solution (visible in the log).
  • Scheduling improvements
  • The usual bunch of bugfixes (crash during presolve, crash in cuts, infeasible solutions, model infeasible in LNS).

GLOP

  • Speedup by rewriting the linear algebra, as well as the pivot selection rule

Linear Solver

  • add knapsack_interface.cc.
  • Move model_builder API under the linear_solver directory (headers and samples).
  • Add support for Gurobi 10.

Routing

  • Liberate few parser for various routing challenge.

v9.4 (2022/08)

11 Aug 21:43
Compare
Choose a tag to compare

Platforms

Misc

  • Split archive by languages and add CMake config to the C++ one (#3200)

Graph

Split ortools.graph.pywrapgraph into:

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

This allows using numpy to speed up the setup of the problems.

CP-SAT

Some improvement on:

  • scheduling (propagation, cuts, lower bounds)
  • MaxSAT (presolve, core based heuristics)
  • MIP performance (presolve, cuts)

v9.3 (2022/03)

17 Mar 00:47
Compare
Choose a tag to compare

Platform changes

  • Drop Debian-10 support
  • Drop Ubuntu-16.04 support
  • Drop .NET Framework 4.5.2

Dependencies Update

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

Python

  • Add pybind11.

Features

  • Add PDLP as experimental
  • Add MathOpt as experimental.

CP-SAT

  • renamed few API for consistency
    e.g. LinearExpr.ScalProd -> LinearExpr.WeightedSum.
  • Add AddAtLeastOne/AddAtMostOne/AddExactlyOne methods.
  • Add AddMultiplicationConstraint(z, x, y) in all languages.
  • AddMultipleCircuit() in all languages

C++

  • explicit ctor IntVar(BoolVar)
  • remove LinearExpr::Add*and replaced them by operator e.g. LinearExpr +=
  • Add arithmetic operators on linear expression
  • removed LinearExpr::BooleanSum/BooleanScalProd, use Sum/WeightedSum
  • Add CpModelBuilder::FixVariable() which overwrite the domain of the variable to a single value

Java

  • Rewrite LinearExpr, add a incremental builder class: LinearExpr.newBuilder().add(x).addSum(<array of variables).build()
  • Follow C++ API: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment and ForbiddenAssignment now return a specialized class with incremental API to add new variables, terms, demands…

C#

  • Document all methods
  • Follow C++ API: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment and ForbiddenAssignment now return a specialized class with incremental API to add new variables, terms, demands…
  • Add LinearExprBuilder class to build expression incrementally.

Build System

CMake

  • Require at least CMake >= 3.18

Make

  • Now use the CMake based build internally.

v9.2 (2021/12)

16 Dec 09:01
Compare
Choose a tag to compare

Platform changes

  • Add support for Ubuntu 21:10 (last rolling release).

Dependencies Update

  • .Net TFM update net5.0 -> net6.0 (need .Net SDK 6.0 LTS and .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: add numpy >= 1.13.3.
  • On MacOS compile Coin-OR in -O1 to avoid crash in runners.

Routing

  • Improvement on filters.
  • Improve first solution heuristics.
  • Improve time break placements.

CP-SAT

  • Breaking changes:
    • The underlying protocol buffer is incompatible with previous versions. Any stored protocol buffer will have to be re-generated with the updated builder APIs (in C++, Python, Java, and .NET)
    • In particular, the interval protobuf was clean as we removed the old fields (start, size, and end) and renamed the new ones (using _view) to use the name of the removed fields.
    • AddProductEquality has been removed. Please use AddMultiplicationEquality.
    • Now that we have floating point coefficients for the objective, we have removed ScaleObjectiveBy which had a problematic semantics.
  • New features:
    • The all_different, reservoir, modulo, multiplication and division constraints accept affine expressions (a * var + b) everywhere it required integer variables.
    • The objective accepts floating point coefficients (See the DoubleLinearExpr class in C++/Java/.NET. See the knapsack_2d_sat.py example in Python).
    • The no_overlap_2d constraint supports optional intervals.
    • The C++ API implements + and * operators to build expressions.
  • Improvements:
    • Improved presolve code.
    • Tighter model checker.
    • Rework reservoir constraint.
    • Add energetic cuts for the no_overlap_2d constraint.
    • Improved linear relaxation of encoding constraints (literal implies var == value).
  • Deprecated and removed methods
    • Deprecated C++ BooleanSum and BooleanScalProd. Just use Sum and ScalProd.
    • Removed C++ AddLinMinEquality and AddLinMaxEquality. Just use AddMinEquality and AddMaxEquality.
  • Future incompatibilities
    • At some point in the future, we will rewrite the Java modelling layer to be closer to the C++ layer.
    • In the C++ modelling layer, we will make the IntVar(BoolVar var) ctor explicit.
    • We are contemplating making the python API PEP 8 compliant (using snake_case names). If this happen, we will provide a sed file to port the code.

Build System

Bazel

  • Fix Windows build.

CMake

  • Add FETCH_PYTHON_DEPS option (default ON).
  • Add optional support for GPLK solver (default -DUSE_GLPK=OFF).

Python

  • Support numpy integers in most of the CP-SAT API.
  • Fix missing __version__.