Ortools

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.

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.

What's Changed
* build(deps): bump urllib3 from 2.0.4 to 2.0.7 in /bazel by dependabot in https://github.com/google/or-tools/pull/3988
* Fix memory leaks in file::GetContents and file::SetContents by pjh in https://github.com/google/or-tools/pull/4011
* build(deps): bump jupyter-server from 2.7.2 to 2.11.2 in /bazel by dependabot in https://github.com/google/or-tools/pull/4014
* Improve the Xpress interface and add dynamic loading of the Xpress library by sgatto in https://github.com/google/or-tools/pull/3966
* improve performance of Xpress interface and fix bug by sgatto in https://github.com/google/or-tools/pull/4030
* build(deps): bump jinja2 from 3.1.2 to 3.1.3 in /bazel by dependabot in https://github.com/google/or-tools/pull/4049
* Include LICENSE file in Python distribution by chrisjbremner in https://github.com/google/or-tools/pull/4048

New Contributors
* pjh made their first contribution in https://github.com/google/or-tools/pull/4011
* sgatto made their first contribution in https://github.com/google/or-tools/pull/3966
* chrisjbremner made their first contribution in https://github.com/google/or-tools/pull/4048

**Full Changelog**: https://github.com/google/or-tools/compare/v9.8...v9.9

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`
sh
$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: https://github.com/google/re2/commit/49d776b9d29d79b6e2876d5f091d2207d8123dfa

issue `operator<<`

sh
$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`

sh
$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: https://github.com/abseil/abseil-cpp/commit/34eb767645347f100bdd66fc1e35eee96e357961

What's Changed
* build(deps): bump tornado from 6.2 to 6.3.3 in /bazel by dependabot in https://github.com/google/or-tools/pull/3893
* build(deps): bump pygments from 2.14.0 to 2.15.0 in /bazel by dependabot in https://github.com/google/or-tools/pull/3885
* build(deps): bump jupyter-server from 2.7.0 to 2.7.2 in /bazel by dependabot in https://github.com/google/or-tools/pull/3904
* Update Visual Studio Version in README.md by arnabanimesh in https://github.com/google/or-tools/pull/3968

New Contributors
* dependabot made their first contribution in https://github.com/google/or-tools/pull/3893
* arnabanimesh made their first contribution in https://github.com/google/or-tools/pull/3968

**Full Changelog**: https://github.com/google/or-tools/compare/v9.7...v9.8

Platforms
* Drop Fedora [33,36] ([EOL](https://endoflife.date/fedora)).
* Drop Centos 8.
* Drop Debian 10.
* Drop Ubuntu 18.04 LTS.
* Drop Python 3.7 support ([EOL](https://devguide.python.org/versions/)).
* Disable .Net Core 3.1 ([EOL](https://dotnet.microsoft.com/en-us/platform/support/policy/dotnet-core))

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](https://github.com/google/or-tools/blob/main/ortools/linear_solver/samples/assignment_mb.py)
- see [bin_packing](https://github.com/google/or-tools/blob/main/ortools/linear_solver/samples/bin_packing_mb.py)
* 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](https://github.com/google/or-tools/blob/main/ortools/sat/samples/assignment_sat.py)
- see [bin_packing](https://github.com/google/or-tools/blob/main/ortools/sat/samples/bin_packing_sat.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
* Ignore the close error when reading fails in file.cc by ciarand in https://github.com/google/or-tools/pull/3717
* Fix reference to solve_wrapper in Solve method by djsilcock in https://github.com/google/or-tools/pull/3719
* ensure absolute native library path in Java Loader by afloren in https://github.com/google/or-tools/pull/3728
* Allow last_variable_index_ to be zero by rajgoel in https://github.com/google/or-tools/pull/3758
* Xpress fixes by djunglas in https://github.com/google/or-tools/pull/3576
* Update cplex_interface.cc by Robot-1x in https://github.com/google/or-tools/pull/3764 https://github.com/google/or-tools/pull/3766
* feat(python): unignore Solver::TopProgressPercent and SearchMonitor::… by bertuccellimatteo in https://github.com/google/or-tools/pull/3831
* Evaluate LinearExp for the found solution by koen-lee in https://github.com/google/or-tools/pull/3837
* Fix CMake build in `test` subdirectories by lnikkila in https://github.com/google/or-tools/pull/3845
* Python CP-SAT type hints by stradivari96 in https://github.com/google/or-tools/pull/3668
* Fix RUNPATHs for libraries and executables by StefanBruens in https://github.com/google/or-tools/pull/3383

New Contributors
* ciarand made their first contribution in https://github.com/google/or-tools/pull/3717
* djsilcock made their first contribution in https://github.com/google/or-tools/pull/3719
* afloren made their first contribution in https://github.com/google/or-tools/pull/3728
* rajgoel made their first contribution in https://github.com/google/or-tools/pull/3758
* djunglas made their first contribution in https://github.com/google/or-tools/pull/3576
* Robot-1x made their first contribution in https://github.com/google/or-tools/pull/3764
* bertuccellimatteo made their first contribution in https://github.com/google/or-tools/pull/3831

**Full Changelog**: https://github.com/google/or-tools/compare/v9.6...v9.7

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

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)