v9.9

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

• @pjh made their first contribution in #4011
• @sgatto made their first contribution in #3966
• @chrisjbremner made their first contribution in #4048

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

v9.8

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

• build(deps): bump tornado from 6.2 to 6.3.3 in /bazel by @dependabot in #3893
• build(deps): bump pygments from 2.14.0 to 2.15.0 in /bazel by @dependabot in #3885
• build(deps): bump jupyter-server from 2.7.0 to 2.7.2 in /bazel by @dependabot in #3904
• Update Visual Studio Version in README.md by @arnabanimesh in #3968

New Contributors

• @dependabot made their first contribution in #3893
• @arnabanimesh made their first contribution in #3968

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

v9.7 (2023/08)

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.
  • see assignment
  • see bin_packing
• 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
  • see assignment
  • see bin_packing
• 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

• Ignore the close error when reading fails in file.cc by @ciarand in #3717
• Fix reference to solve_wrapper in Solve method by @djsilcock in #3719
• ensure absolute native library path in Java Loader by @afloren in #3728
• Allow last_variable_index_ to be zero by @rajgoel in #3758
• Xpress fixes by @djunglas in #3576
• Update cplex_interface.cc by @Robot-1x in #3764 #3766
• feat(python): unignore Solver::TopProgressPercent and SearchMonitor::… by @bertuccellimatteo in #3831
• Evaluate LinearExp for the found solution by @koen-lee in #3837
• Fix CMake build in test subdirectories by @lnikkila in #3845
• Python CP-SAT type hints by @stradivari96 in #3668
• Fix RUNPATHs for libraries and executables by @StefanBruens in #3383

New Contributors

• @ciarand made their first contribution in #3717
• @djsilcock made their first contribution in #3719
• @afloren made their first contribution in #3728
• @rajgoel made their first contribution in #3758
• @djunglas made their first contribution in #3576
• @Robot-1x made their first contribution in #3764
• @bertuccellimatteo made their first contribution in #3831

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

v9.6 (2023/03)

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)

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)

Platforms

• Add Debian-10 support (#3209)
• Add Ubuntu 22.04 LTS support (#3276)
  • note: won't have .Net 3.1 support (see: dotnet/core#7038 (comment))
• Remove Ubuntu 21.10 support

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)

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)

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__.

v9.1 (2021/09)

Platform changes

• Ubuntu 16.04 LTS is deprecated (actions/runner-images#3287).
• Add support for Debian 11 (Bullseye).
• Add support for Fedora 34.
• python: use manylinux2014 image (PEP 599).
• python: add support for aarch64 linux using manylinux2014_aarch64 image.
• .Net: add .Net5 support.

Dependencies Update

• 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: use of warning in cp_model.py (#2530).
• python: absl-py 0.11 -> 0.13.

CMake

• Bump minimum version required 3.14 -> 3.15 (#2528).
• python: bump minimum required version 3.14 -> 3.18 (#2774).

Make

• Make based build is deprecated please migrate to Bazel or CMake

Java

• Improve robustness of the native library loader (#2742).
• Fix jvm GC crash when routing model or the constraint solver were disposed (#2091, #2466).
• Fix CP-SAT logging callback crash when using multiple workers (#2775).

CP-SAT

• Improve robustness of the LNS code (see #2525).
• Improve scheduling code: new factory methods to create fixed size intervals,
  new search heuristics, improved presolve and new linear cuts.
• Improve routing code: new dedicated LNS.
• Improve model checker. It is now more pedantic, especially w.r.t. potential overflows.
• Improve MIP code: better presolve and multiple improvements to the linear relaxation of MIP
  and CP models.
• Improve search diversity. When using more than 12 workers, add workers dedicated to
  improving the lower bound of the objective.
• Change to the parallelism code: by default, the solver will now use all available cores.
  Use the num_search_parameters to specify the level of parallelism.
• Deprecate SearchAllSolutions and SolveWithSolutionCallback.
• Python API: more pedantic checks when using var == ... or var != ... outside a model.Add() call.

v9.0 (2021/04)

Platform changes

• Added support for Centos-7 (#2498)

Dependencies Update

• abseil-cpp 20200923.3 -> 20210324.1 (#2523)
• Protobuf 3.15.3 -> 3.15.8 (#2524)
• Java: jna-platform 5.5.0 -> 5.8.0 (#252)

Features/Fix

• Improve multi-threading when using CP-SAT solver (#1588)
• Add logger access support in Python, Java and .Net (#2245)
• C++: Replace Google type [u]int(16|32|64) by cstdint ones (e.g. uint64_t)
• Python: Fix std::vector<std::string> support (#2453)

Makefile

• Rework CPLEX support (#2470)