Ortools

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.

Platforms
* Add Debian-10 support (3209)
* Add Ubuntu 22.04 LTS support (3276)
* note: won't have .Net 3.1 support (see: https://github.com/dotnet/core/issues/7038#issuecomment-1110377345)
* 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)

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.

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

Platform changes
* Ubuntu 16.04 LTS is deprecated (https://github.com/actions/virtual-environments/issues/3287).
* Add support for Debian 11 (Bullseye).
* Add support for Fedora 34.
* python: use `manylinux2014` image ([PEP 599](https://www.python.org/dev/peps/pep-0599/)).
* 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.

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)