or-tools Documentation

Technical Documentation: google/or-tools

ℹ️ Provenance: Multi-Tier Ingestion · CodeWiki Reference

Overview (`README.md`) Copy Section

OR-Tools - Google Optimization Tools

Google's software suite for combinatorial optimization.

Table of Contents Copy Chapter

• About OR-Tools
• Codemap
• Installation
• Quick Start
• Documentation
• Contributing
• License

About OR-Tools Copy Chapter

Google Optimization Tools (a.k.a., OR-Tools) is an open-source, fast and
portable software suite for solving combinatorial optimization problems.

The suite contains:

• Two constraint programming solver (CP* and CP-SAT);
• Two linear programming solvers (Glop and PDLP);
• Wrappers around commercial and other open source solvers, including mixed
  integer solvers;
• Bin packing and knapsack algorithms;
• Algorithms for the Traveling Salesman Problem and Vehicle Routing Problem;
• Graph algorithms (shortest paths, min cost flow, max flow, linear sum
  assignment).

We wrote OR-Tools in C++, but provide wrappers in Python, C# and Java.

Codemap Copy Chapter

This software suite is composed of the following components:

• Makefile Top-level for
  GNU Make based build.
• makefiles Subsidiary Make files, CI and build system documentation.
• CMakeLists.txt Top-level for
  CMake based build.
• cmake Subsidiary CMake files, CI and build system documentation.
• WORKSPACE Top-level for
  Bazel based build.
• bazel Subsidiary Bazel files, CI and build system documentation.
• ortools Root directory for source code.
  • base Basic utilities.
  • algorithms Basic algorithms.
    • samples Carefully crafted samples.
  • graph Graph algorithms.
    • samples Carefully crafted samples.
  • linear_solver Linear solver wrapper.
    • samples Carefully crafted samples.
  • glop Simplex-based linear programming solver.
    • samples Carefully crafted samples.
  • pdlp First-order linear programming solver.
    • samples Carefully crafted samples.
  • lp_data Data structures for linear models.
  • constraint_solver Constraint and Routing
    solver.
    • docs Documentation of the component.
    • samples Carefully crafted samples.
  • sat SAT solver.
    • docs Documentation of the component.
    • samples Carefully crafted samples.
  • bop Boolean solver based on SAT.
  • util Utilities needed by the constraint solver
• examples Root directory for all examples.
  • contrib Examples from the community.
  • cpp C++ examples.
  • dotnet .Net examples.
  • java Java examples.
  • python Python examples.
  • notebook Jupyter/IPython notebooks.
  • flatzinc FlatZinc examples.
• tools Delivery Tools (e.g. Windows GNU binaries, scripts, release dockers)

Installation Copy Chapter

This software suite has been tested under:

• Ubuntu 18.04 LTS and up (64-bit);
• Apple macOS Mojave with Xcode 9.x (64-bit);
• Microsoft Windows with Visual Studio 2022 (64-bit).

OR-Tools currently builds with a Makefile, but also provides Bazel and CMake
support.

For installation instructions (both source and binary), please visit
https://developers.google.com/optimization/introduction/installing.

Build from source using Make (legacy) Copy Section

We provide a Make based build.Please check the
Make build instructions.

Build from source using CMake Copy Section

We provide a CMake based build.Please check the
CMake build instructions.

Build from source using Bazel Copy Section

We provide a Bazel based build.Please check the
Bazel build instructions.

Quick Start Copy Chapter

The best way to learn how to use OR-Tools is to follow the tutorials in our
developer guide:

https://developers.google.com/optimization/introduction/get_started

If you want to learn from code examples, take a look at the examples in the
examples directory.

Documentation Copy Chapter

The complete documentation for OR-Tools is available at:
https://developers.google.com/optimization/

Contributing Copy Chapter

The CONTRIBUTING.md file contains instructions on how to
submit the Contributor License Agreement before sending any pull requests (PRs).
Of course, if you're new to the project, it's usually best to discuss any
proposals and reach consensus before sending your first PR.

License Copy Chapter

The OR-Tools software suite is licensed under the terms of the Apache License 2.0.
See LICENSE for more information.

Overview (`bazel/README.md`) Copy Section

OR-Tools Bazel Build Instructions

OS	C++
amd64 Linux
arm64 MacOS
amd64 MacOS
amd64 Windows

Dockers [Alpine, Archlinux, Centos, Debian, Fedora, OpenSuse, Ubuntu]:

Introduction Copy Chapter

OR-Tools comes with a Bazel based build (WORKSPACE) that can be
used on a wide range of platforms. If you don't have Bazel installed already,
you can download it for free from https://bazel.build/.

warning: Currently OR-Tools Bazel doesn't support Python, Java nor .Net,
please use the Makefile or CMake based build instead.

Requirement Copy Chapter

You'll need:

• Bazel >= 5.4.0.
• A compiler with C++17 support.

Solvers supported Copy Chapter

Here the list of supported solvers:

• CP-SAT
• GLOP
• GLPK
• PDLP
• SCIP

Dependencies Copy Chapter

OR-Tools depends on several mandatory libraries.

• Eigen
• Google Abseil-cpp,
• Google Protobuf,
• Google Gtest,
• Bliss,
• SCIP,
• GLPK (GNU Linear Programming Kit)

Compilation Copy Chapter

You must compile OR-Tools using at least C++17 (C++20 on windows):

• on UNIX:

  sh Copy

  bazel build -c opt --cxxopt=-std=c++17 ...

• on Windows when using MSVC:

  sh Copy

  bazel build -c opt --cxxopt="/std:c++20" ...

Testing Copy Chapter

You may run tests using:

• on UNIX:

  sh Copy

  bazel test -c opt --cxxopt=-std=c++17 ...

• on Windows when using MSVC:

  sh Copy

  bazel test -c opt --cxxopt="/std:c++20" ...

Integration Copy Chapter

To integrate OR-Tools in your own Bazel project,
you can take a look at the template project:
or-tools/bazel_or-tools.

Overview (`cmake/README.md`) Copy Section

OR-Tools CMake Build Instructions

OS	C++	Python	Java	.NET
amd64 Linux
arm64 MacOS
amd64 MacOS
amd64 Windows

Dockers:
[AlmaLinux, Alpine, Archlinux, Debian, Fedora, OpenSuse, RockyLinux, Ubuntu]x
[C++, Python, Java, .Net]:

Introduction Copy Chapter

OR-Tools comes with a CMake-based build (CMakeLists.txt)
that can be used on a wide range of platforms (the "C" stands for
cross-platform). If you don't have CMake installed already, you can download it
for free from http://www.cmake.org/.

CMake works by generating native Makefiles or build projects that can be used in
the compiler environment of your choice.You can either build OR-Tools with
CMake as a standalone project or incorporate it into an existing CMake project.

Requirement Copy Chapter

You'll need:

• CMake >= 3.24.
• A C++20 compiler (GCC 10 or above)

Solvers supported Copy Chapter

Here the list of supported solvers:

• CBC
• CLP
• CP-SAT
• CPLEX*
• GLOP
• GLPK*
• HiGHS*
• PDLP
• SCIP
• XPRESS

*: these solvers are disabled by default.

Dependencies Copy Chapter

OR-Tools depends on several mandatory librariess, either as infrastructure or as
optimization solvers. You can either compile them all at configure time using
the option -DBUILD_DEPS=ON (OFF by default) or compile some of them using
the options below (see CMake Options below).

• zlib (BUILD_ZLIB),
• bzip2 (BUILD_BZip2),
• Google Abseil-cpp (BUILD_absl),
• Google Protobuf (BUILD_Protobuf),
• COIN-OR solvers:
  • COIN-OR CoinUtils (BUILD_CoinUtils),
  • COIN-OR Osi (BUILD_Osi),
  • COIN-OR Clp (BUILD_Clp),
  • COIN-OR Cgl (BUILD_Cgl),
  • COIN-OR Cbc (BUILD_Cbc),
    note: You can disable the support of COIN-OR solvers
    (i.e. Cbc and Clp solver) by using -DUSE_COINOR=OFF (ON by default).
• HIGHS (BUILD_HIGHS),
  note: You must enable the support of HiGHS solver by using -DUSE_HIGHS=ON
  (OFF by default).
• SCIP (BUILD_SCIP),
  note: You can disable the support of SCIP solver by using -DUSE_SCIP=OFF
  (ON by default).

OR-Tools can also optionally (disabled by default i.e. OFF) be compiled with
support for the following third-party solvers:

• GLPK (BUILD_GLPK),
  note: You must enable the support of GLPK solver by using -DUSE_GLPK=ON
  (OFF by default).
• CPLEX (USE_CPLEX),

warning: Since these solvers are either proprietary (and require a specific
license) or available under the GPL, we can't test them on public CI and their
support may be broken.

Enabling CPLEX Support Copy Section

To enable CPLEX support, configure with -DUSE_CPLEX=ON and
-DCPLEX_ROOT=/absolute/path/to/CPLEX/root/dir, replacing
/absolute/path/to/CPLEX/root/dir with the path to your CPLEX installation.
CPLEX_ROOT can also be defined as an environment variable rather than an
option at configure time.

For ease of migration from legacy make third_party builds, CMake will also
read the CPLEX installation path from the UNIX_CPLEX_DIR environment variable,
if defined.

CMake Options Copy Chapter

There are several options that can be passed to CMake to modify how the code
is built.
To set these options and parameters, use -D=<value>.

All CMake options are passed at configure time, i.e., by running
cmake -S. -B<your_chosen_build_directory> -DOPTION_ONE=ON -DOPTION_TWO=OFF ...
before running cmake --build <your_chosen_build_directory>

For example, to generate build files including dependencies in a new
subdirectory called 'build', run:

cmake -S. -Bbuild -DBUILD_DEPS:BOOL=ON

and then build with:

cmake --build build

Following is a list of available options, for the full list run:

cmake -S. -Bbuild -LH

Integrating OR-Tools in your CMake Project Copy Chapter

You should be able to integrate OR-Tools in your C++ CMake project following one
of these methods.

For API/ABI compatibility reasons, if you will be using OR-Tools inside a larger
C++ project, we recommend using CMake and incorporate OR-Tools as a CMake
subproject (i.e. using add_sudirectory() or FetchContent).

Consuming OR-Tools in a CMake Project Copy Section

If you already have OR-Tools installed in your system, you can use the CMake
command
find_package()
to include OR-Tools in your C++ CMake Project.

note: You may need to set
CMAKE_PREFIX_PATH
in order for CMake to find your OR-Tools installation.

cmake_minimum_required(VERSION 3.14)
project(myproj VERSION 1.0)

find_package(ortools CONFIG REQUIRED)

add_executable(myapp main.cpp)
target_link_libraries(myapp ortools::ortools)

Include directories, compile definitions and compile options will be added
automatically to your target as needed.

Incorporating OR-Tools into a CMake Super Project Copy Section

Using add_subdirectory

The recommendations below are similar to those for using CMake
within the googletest framework

Thus, you can use the CMake command
add_subdirectory()
to include OR-Tools directly from a subdirectory of your C++ CMake project.
Note: The ortools::ortools target is in this case an ALIAS library target
for the ortools library target.

cmake_minimum_required(VERSION 3.18)
project(myproj VERSION 1.0)

add_subdirectory(or-tools)

add_executable(myapp main.cpp)
target_link_libraries(myapp ortools::ortools)

Again, include directories, compile definitions and compile options will be
added automatically to your target as needed.

Using FetchContent

If you have CMake >= 3.18 you can use the built-in module
FetchContent
instead. Note: The ortools::ortools target is in this case an ALIAS library
target for the ortools library target.

cmake_minimum_required(VERSION 3.18)
project(myproj VERSION 1.0 LANGUAGES CXX)

include(FetchContent)
FetchContent_Declare(
  or-tools
  GIT_REPOSITORY https://github.com/google/or-tools.git
  GIT_TAG        main
)

# After the following call, the CMake targets defined by OR-Tools
# will be defined and available to the rest of the build
FetchContent_MakeAvailable(or-tools)

add_executable(myapp main.cpp)
target_link_libraries(myapp ortools::ortools)

note: You may need to use the option -DBUILD_DEPS=ON to get all the OR-Tools
dependencies as well.

Overview (`makefiles/README.md`) Copy Section

OR-Tools Makefile Build Instructions

Introduction Copy Chapter

warning: Makefile build is deprecated, please use CMake or Bazel based build.

OR-Tools comes with a GNU Make based build (Makefile) that can be
used on a wide range of platforms.

Requirement Copy Chapter

You'll need:

• GNU Make >= 4.3.
• A C++20 compiler (gcc 10 or above)

Dependencies Copy Chapter

OR-Tools depends on several mandatory libraries, either as infrastructure or as
optimization solvers. You can either compile all of these dependencies using the
target third_party or compile some of them on your own and give their
installation directories to the others using the Make variables below.

• zlib (UNIX_ZLIB_DIR or WINDOWS_ZLIB_DIR),
• Google Abseil-cpp (UNIX_ABSL_DIR or WINDOWS_ABSL_DIR),
• Google Protobuf (UNIX_PROTOBUF_DIR or WINDOWS_PROTOBUF_DIR),
• SCIP (UNIX_SCIP_DIR or WINDOWS_SCIP_DIR),
• COIN-OR solvers:
  • COIN-OR CoinUtils (UNIX_COINUTILS_DIR or WINDOWS_COINUTILS_DIR),
  • COIN-OR Osi (UNIX_OSI_DIR or WINDOWS_OSI_DIR),
  • COIN-OR Clp (UNIX_CLP_DIR or WINDOWS_CLP_DIR),
  • COIN-OR Cgl (UNIX_CGL_DIR or WINDOWS_CGL_DIR),
  • COIN-OR Cbc (UNIX_CBC_DIR or WINDOWS_CBC_DIR),

OR-Tools can also optionally (disabled by default) be compiled with support for
the following third-party solvers:

• CPLEX (UNIX_CPLEX_DIR or WINDOWS_CPLEX_DIR),
• GLPK (UNIX_GLPK_DIR or WINDOWS_GLPK_DIR),
• GUROBI (UNIX_GUROBI_DIR or WINDOWS_GUROBI_DIR),
• XPRESS (UNIX_XPRESS_DIR or WINDOWS_XPRESS_DIR)

warning: Since these solvers are either proprietary (and require a specific
license) or available under the GPL, we can't test them on public CI and their
support may be broken.

Overview (`examples/cpp/README.md`) Copy Section

C++ examples

The following examples showcase how to use the different Operations Research
libraries.

Examples list Copy Chapter

• Constraint Solver examples:

  • cryptarithm.cc Demonstrates the use of basic modeling objects
    (integer variables, arithmetic constraints and expressions,
    simple search).
  • golomb.cc Demonstrates how to handle objective functions and collect
    solutions found during the search.
  • magic_square.cc Shows how to use the automatic search to solve your
    problem.
  • costas_array.cc Solves the problem of Costas Array (a constrained
    assignment problem used for radars) with two version. On version is
    a feasibility version with hard constraints, the other version is
    an optimization version with soft constraints and violation costs.
  • jobshop.cc Demonstrates scheduling of jobs on different machines.
  • nqueens.cc Solves the n-queen problem. It also demonstrates how to break
    symmetries during search.
  • network_routing_sat.cc Solves a multicommodity mono-routing
    problem with capacity constraints and a max usage cost structure.
  • sports_scheduling_sat.cc Finds a soccer championship schedule. Its uses an
    original approach where all constraints attached to either one team,
    or one week are regrouped into one global 'AllowedAssignment' constraints.
  • dobble_ls.cc Shows how to write Local Search operators and Local Search
    filters in a context of an assignment/partitioning problem. It also
    shows how to write a simple constraint.

• Routing examples:

  • cvrptw.cc Capacitated Vehicle Routing Problem with Time Windows.
  • pdptw.cc Pickup and Delivery Problem with Time Windows.

• Graph examples:

  • flow_api.cc Demonstrates how to use Min-Cost Flow and Max-Flow api.
  • linear_assignment_api.cc Demonstrates how to use the Linear Sum
    Assignment solver.
  • dimacs_assignment.cc Solves DIMACS challenge on assignment
    problems.

• Linear and integer programming examples:

  • linear_programming.cc Demonstrates how to use the linear solver
    wrapper API to solve Linear Programming problems.
  • integer_programming.cc Demonstrates how to use the linear solver
    wrapper API to solve Integer Programming problems.
  • linear_solver_protocol_buffers.cc Demonstrates how protocol
    buffers can be used as input and output to the linear solver wrapper.
  • strawberry_fields_with_column_generation.cc Complex example that
    demonstrates how to use dynamic column generation to solve a 2D
    covering problem.

Execution Copy Chapter

Running the examples will involve building them, then running them.
You can run the following command from the top directory:

make build SOURCE=examples/cpp/<example>.cc
make run SOURCE=examples/cpp/<example>.cc

Overview (`examples/dotnet/README.md`) Copy Section

.NetCoreApp examples

The following examples showcase how to use OrTools.
The project solution has examples for C#.

We recommend that all projects you create target net8.0,
as this allows you to compile for various frameworks and
keep up-to-date with the latest frameworks.

Wherever you have or-tools installed, be sure to PackageReference the Google.OrTools
from the project file.

Execution Copy Chapter

Running the examples will involve building them, then running them.
You can run the following command:

dotnet build <example>.csproj
dotnet run --no-build --project <example>.csproj

Overview (`examples/flatzinc/README.md`) Copy Section

The majority of these examples are here curtesy of Hakan Kjellerstrand.

See http://www.hakank.org/minizinc for details.

Overview (`examples/java/README.md`) Copy Section

Java examples

The following examples showcase how to use the different Operations Research libraries.

Execution

Running the examples will involve building them, then running them.
You can run the following command from the top directory:

make build SOURCE=examples/java/<example>.java
make run SOURCE=examples/java/<example>.java

Overview (`examples/notebook/README.md`) Copy Section

Introduction

First and foremost, the Jupyter Notebook is an interactive environment for writing and running code.

Prerequisite: Python3

These notebooks are associated with the IPython3 kernel, therefore runs Python3 code.
Thus, to run these notebooks you'll need Python3 and python ortool package.

Once you have python3 installed, ensure you have the latest pip:

pip3 install --user --upgrade pip

note: on Ubuntu you can also use: apt-get install python3-pip

Installing Jupyter

Install Jupyter Notebook using:

pip3 install --user jupyter

Then install our notebooks dependencies:

pip3 install --user plotly numpy svgwrite

Running the Notebooks

To run the notebook, run the following command at the Terminal (Mac/Linux) or Command Prompt (Windows):

jupyter notebook

You should see the notebook dashboard open in your browser.

Then go to your or-tools source directory and try to open a notebook (located in
examples/notebook).

note: You can run a code cell using Shift-Enter or pressing the >| button in the toolbar.

Overview (`examples/python/README.md`) Copy Section

Python examples

The following examples showcase how to use OrTools.
These examples should work for any Python3.7+.

We recommend that all projects you create target Python 3.9,
as this allows you to keep up-to-date with the latest Python frameworks.

Wherever you have ortools package installed, be sure to import it from your python file.

Execution

For running the examples you can use the following command:

python3 -m pip install --upgrade --user ortools
python3 <example>.py

Overview (`ortools/algorithms/README.md`) Copy Section

Various algorithms

This directory contains data structures and algorithms for various problems.

It used to contain a solver for set covering, which has moved to the
set_cover folder.

Overview (`ortools/constraint_solver/README.md`) Copy Section

Constraint Programming (CP) and Routing Solver

This directory contains a Constraint Programming (CP) solver and a Vehicle
Routing solver.

CP solver Copy Chapter

Constraint Programming is
a technology issued from AI and used in operations research.

To begin, skim:

• constraint_solver.h:
  Declaration of the core objects for the constraint solver.
• constraint_solveri.h:
  Collection of objects used to extend the Constraint Solver library.

Parameters Copy Section

• solver_parameters.proto:
  This file contains protocol buffers for all parameters of the CP solver.
• search_limit.proto:
  Holds parameters to limit the search space within the CP solver, which is
  important for performance.

Solution Copy Section

• assignment.proto:
  Holds the solution of a CP problem.
• demon_profiler.proto:
  Holds the timeline and execution profile of constraints and demons
  (daemons).

Routing solver Copy Chapter

Vehicle Routing is a useful
extension that is implemented on top of the CP solver library.

To begin, skim:

• routing.h:
  The vehicle routing library lets one model and solve generic vehicle routing
  problems ranging from the Traveling Salesman Problem to more complex problems
  such as the Capacitated Vehicle Routing Problem with Time Windows.

Parameters Copy Section

• routing_parameters.proto:
  The Vehicle Routing solver parameters.
• routing_enums.proto:
  Enums used to define routing parameters.

Solution Copy Section

• assignment.proto:
  Holds the solution of a Routing problem.

Recipes Copy Chapter

You can find a set of code recipes in
the documentation directory.

Overview (`ortools/cpp/README.md`) Copy Section

Introduction

This directory contains some CMake templates files use to build a project which
will depends on OR-Tools.

Overview (`ortools/dotnet/README.md`) Copy Section

Introduction

This is the documentation page for the .NET wrapper of OR-Tools.

This project aim to explain how you build a .Net native (for win-x64, linux-x64
and osx-x64) nuget package using dotnet and few .csproj.

Table of Content Copy Chapter

• Requirement
• Directory Layout
• Build
  • Build Process
  • Local Google.OrTools Package
    • Building a runtime Google.OrTools Package
    • Building a Local Google.OrTools Package
  • Complete Google.OrTools Package
    • Building all runtime Google.OrTools Package
    • Building a Complete Google.OrTools Package
• Examples
• Appendices
  • Resources
  • Issues
• Misc

Requirement Copy Chapter

The library is compiled against netcoreapp3.1 and net8.0, so you'll only
need:

• .Net Core 3.1 LTS SDK
• .Net 8.0 LTS SDK

note: We won't/can't rely on VS 2022 since we want a portable cross-platform
dotnet/cli pipeline.

Project Layout Copy Chapter

• Google.OrTools.runtime.linux-x64: Contains the .Net Standard 2.1 native
  project for the rid linux-x64.
• Google.OrTools.runtime.linux-arm64: Contains the .Net Standard 2.1 native
  project for the rid linux-arm64.
• Google.OrTools.runtime.osx-x64: Contains the .Net Standard 2.1 native
  project for the rid osx-x64.
• Google.OrTools.runtime.osx-arm64: Contains the .Net Standard 2.1 native
  project for the rid osx-arm64.
• Google.OrTools.runtime.win-x64: Contains the .Net Standard 2.1 native
  project for the rid win-x64.
• Google.OrTools Is the .Net Standard 2.1 meta-package which should depends on
  all previous available packages and contains the Reference Assembly.

note: While Microsoft use runtime-<rid>.Company.Project for native libraries
naming, it is very difficult to get ownership on it, so you should prefer to use
Company.Project.runtime-<rid> instead since you can have ownership on
Company.* prefix more easily.

Build Copy Chapter

Either use the CMake base build or the Makefile based build. The workflow is
typically make dotnet which will build both C# and F# libraries package. The
output will be placed in /dotnet/packages folder. All tests will be
run based on this folder.

Build Process Copy Section

To Create a native dependent package we will split it in two parts:

• A bunch of Google.OrTools.runtime.{rid}.nupkg packages for each
  Runtime Identifier (RId)
  targeted.
• A generic package Google.OrTools.nupkg depending on each runtime packages
  and containing the managed .Net code.

Actually, You don't need a specific variant of .Net Standard wrapper, simply
omit the library extension and .Net magic will pick the correct native library.
ref: https://www.mono-project.com/docs/advanced/pinvoke/#library-names

note: Microsoft.NetCore.App packages
follow this layout.

We have two use case scenario:

1. Locally, be able to build a Google.OrTools package which only target the
   local OS Platform, i.e. building for only one
   Runtime Identifier (RID).
   
   note: This is useful since the C++ build is a complex process for Windows,
   Linux and MacOS. i.e. We don't support cross-compilation for the native
   library generation.

2. Be able to create a complete cross-platform (ed. platform as multiple rid)
   Google.OrTools package.
   i.e. First you generate each native Nuget package
   (Google.OrTools.runtime.{rid}.nupkg) on each native architecture, then
   copy paste these artifacts on one native machine to generate the
   meta-package Google.OrTools.

Local Google.OrTools Package Copy Section

Let's start with scenario 1: Create a Local Google.OrTools package targeting one
Runtime Identifier (RID).
We would like to build a Google.OrTools.nupkg package which only depends
on one Google.OrTools.runtime.{rid}.nupkg in order to work locally.

The pipeline for linux-x64 should be as follow:

note: The pipeline will be similar for osx-x64 and win-x64 architecture,
don't hesitate to look at the CI log.

Building local runtime Google.OrTools Package

disclaimer: We won't cover the C++ ortools library build. So first let's create
the local Google.OrTools.runtime.{rid}.nupkg nuget package.

Here some dev-note concerning this Google.OrTools.runtime.{rid}.csproj.

• AssemblyName must be Google.OrTools.dll i.e. all {rid} projects must
  generate an assembly with the same name (i.e. no {rid} in the name).
  On the other hand package identifier will contain the {rid}...
  csproj Copy

  <RuntimeIdentifier>{rid}</RuntimeIdentifier>
  <AssemblyName>Google.OrTools</AssemblyName>
  <PackageId>Google.OrTools.runtime.{rid}</PackageId>

• Once you specify a RuntimeIdentifier then dotnet build or dotnet build -r {rid}
  will behave identically (save you from typing it).
  note: not the case if you use RuntimeIdentifiers (notice the 's')
• It is recommended
  to add the tag native to the
  nuget package tags
  csproj Copy

  <PackageTags>native</PackageTags>

• Specify the output target folder for having the assembly output in
  runtimes/{rid}/lib/netstandard2.0 in the nupkg
  csproj Copy

  <BuildOutputTargetFolder>runtimes/$(RuntimeIdentifier)/lib</BuildOutputTargetFolder>

  note: Every files with an extension different from .dll will be filter out
  by nuget.
  note: dotnet/cli automatically add the $(TargetFramework) (i.e.
  netstandard2.0) to the output path.
• Add the native shared library to the nuget package in the repository
  runtimes/{rib}/native. e.g. for linux-x64:
  csproj Copy

  <Content Include="*.so">
    <PackagePath>runtimes/linux-x64/native/%(Filename)%(Extension)</PackagePath>
    <Pack>true</Pack>
    <CopyToOutputDirectory>PreserveNewest</CopyToOutputDirectory>
  </Content>

• Generate the runtime package to a defined directory (i.e. so later in
  Google.OrTools package we will be able to locate it)
  csproj Copy

  <PackageOutputPath>{...}/packages</PackageOutputPath>

• Generate the Reference Assembly (but don't include it to this runtime nupkg !,
  see below for explanation) using:
  csproj Copy

  <ProduceReferenceAssembly>true</ProduceReferenceAssembly>

Then you can generate the package using:

dotnet pack Google.OrTools.runtime.{rid}

note: this will automatically trigger the dotnet build.

If everything good the package (located where your PackageOutputPath was
defined) should have this layout:

{...}/packages/Google.OrTools.runtime.{rid}.nupkg:
\- Google.OrTools.runtime.{rid}.nuspec
\- runtimes
   \- {rid}
      \- native
         \- *.so / *.dylib / *.dll
...

note: {rid} could be linux-x64 and {framework} could be netstandard2.0

tips: since nuget package are zip archive you can use unzip -l .nupkg
to study their layout.

Building local Google.OrTools Package

So now, let's create the local Google.OrTools.nupkg nuget package which will
depend on our previous runtime package.

Here some dev-note concerning this Google.OrTools.csproj.

• Add the previous package directory:
  csproj Copy

  <RestoreSources>{...}/packages;$(RestoreSources)</RestoreSources>

• Add dependency (i.e. PackageReference) on each runtime package(s) available:
  csproj Copy

  <ItemGroup Condition="Exists('{...}/packages/Google.OrTools.runtime.linux-x64.1.0.0.nupkg')">
    <PackageReference Include="Google.OrTools.runtime.linux-x64" Version="1.0.0" />
  </ItemGroup>

  Thanks to the RestoreSource we can work locally with our just
  builded package without the need to upload it on
  nuget.org.
• To expose the .Net Surface API the Google.OrTools.csproj must contains at
  least one
  Reference Assembly
  of the previously rumtime package. xml <Content Include="../Google.OrTools.runtime.{rid}/bin/$(Configuration)/$(TargetFramework)/{rid}/ref/*.dll"> ref/$(TargetFramework)/%(Filename)%(Extension) true <CopyToOutputDirectory>PreserveNewest</CopyToOutputDirectory> </Content>

Then you can generate the package using:

dotnet pack Google.OrTools

If everything good the package (located where your PackageOutputPath was
defined) should have this layout:

{...}/packages/Google.OrTools.nupkg:
\- Google.OrTools.nuspec
\- lib
   \- {framework}
      \- Google.OrTools.dll
...

note: {framework} could be netcoreapp3.1 or/and net8.0

Complete Google.OrTools Package Copy Section

Let's start with scenario 2: Create a Complete Google.OrTools.nupkg package
targeting multiple
Runtime Identifier (RID).
We would like to build a Google.OrTools.nupkg package which depends on several
Google.OrTools.runtime.{rid}.nupkg.

The pipeline should be as follow:
note: This pipeline should be run on any architecture, provided you have
generated the three architecture dependent Google.OrTools.runtime.{rid}.nupkg
nuget packages.

Building All runtime Google.OrTools Package

Like in the previous scenario, on each targeted OS Platform you can build the
corresponding Google.OrTools.runtime.{rid}.nupkg package.

Simply run on each platform:

dotnet build <build_dir>/dotnet/Google.OrTools.runtime.{rid}
dotnet pack <build_dir>/dotnet/Google.OrTools.runtime.{rid}

note: replace {rid} by the Runtime Identifier associated to the current OS
platform.

Then on one machine used, you copy all other packages in the {...}/packages so
when building Google.OrTools.csproj we can have access to all package...

Building Complete Google.OrTools Package

This is the same step than in the previous scenario, since we "see" all runtime
packages in {...}/packages, the project will depends on each of them.

Once copied all runtime package locally, simply run:

dotnet build <build_dir>/dotnet/Google.OrTools
dotnet pack <build_dir>/dotnet/Google.OrTools

Examples Copy Chapter

The Test projects show examples of building applications with net8.0.

The F# example folder shows how to compile against the typical .NET Framework
installed on machine.

Appendices Copy Chapter

Few links on the subject...

.Net runtime can deduce library extension so don’t use a platform-specific
library name in the DllImport statement.
Instead, just use the library name itself, without any prefixes or suffixes,
and rely on the runtime to find the appropriate library at runtime.
ref: Mono pinvoke#libraryname

Resources Copy Section

Target Framework Moniker (TFM)

• .NET TFM list
• .NET Standard implementation support

.Net:Runtime IDentifier (RID)

• .Net Support Policy
• .NET Core RID Catalog
• Creating native packages
• Blog on Nuget Rid Graph

Reference on .csproj format

• Common MSBuild project properties
• MSBuild well-known item metadata
• Additions to the csproj format for .NET Core

Issues Copy Section

dotnet seems to use a previous package version ?
You can clear your local cache using: dotnet nuget locals all --clear

Some issue related to this process

• PackageReference only support TargetFramework condition
• Nuget needs to support dependencies specific to target runtime #1660
• Improve documentation on creating native packages #238
• Guide for packaging C# library using P/Invoke

Misc Copy Section

Image has been generated using plantuml:

plantuml -Tpng docs/{file}.dot

So you can find the dot source files in docs.

Overview (`ortools/glop/README.md`) Copy Section

GLOP

GLOP is Google's Linear Optimization Package. It is a full-featured,
production-ready implementation of the revised simplex method designed for
performance and numerical stability in solving linear programming problems.

It's written in C++ but can also be used from Java, Python, or C# via our
linear solver wrapper.

It contains in particular:

• parameters.proto: Contains the definitions for all the
  GLOP algorithm parameters and their default values.
• lp_solver.h: Contains the primary entry point class
  LPSolver.
• preprocessor.h: Contains the presolving code for a
  Linear Program.
• revised_simplex.h: Contains the core implementation of
  the revised simplex algorithm as described by G.B. Dantzig.
• status.h: Return type for various solver functions.

Overview (`ortools/graph/README.md`) Copy Section

Graph and Network Flows

This directory contains data structures and algorithms for graph and network
flow problems.

It contains in particular:

• well-tuned algorithms (for example, shortest paths and
  Hamiltonian paths).
• hard-to-find algorithms (Hamiltonian paths, push-relabel flow algorithms).
• other, more common algorithms, that are useful to use with graphs from
  util/graph.

Generic algorithms for shortest paths:

• bounded_dijkstra.h: entry point for shortest paths.
  This is the preferred implementation for most needs.
• bidirectional_dijkstra.h: for large graphs,
  this implementation might be faster than bounded_dijkstra.h.
• shortest_paths.h: shortest paths that are computed in
  parallel (only if there are several sources). Includes
  Dijkstra and
  Bellman-Ford
  algorithms. Although its name is very generic, only use this implementation
  if parallelism makes sense.

Specific algorithms for paths:

• dag_shortest_path.h: shortest paths on directed
  acyclic graphs. If you have such a graph, this implementation is likely to be
  the fastest. Unlike most implementations, these algorithms have two interfaces
  : a "simple" one (list of edges and weights) and a standard one (taking as
  input a graph data structure from //ortools/graph/graph.h).
• dag_constrained_shortest_path.: shortest
  paths on directed acyclic graphs with resource constraints.
• hamiltonian_path.h: entry point for computing minimum
  Hamiltonian paths and cycles
  on directed graphs with costs on arcs, using a dynamic-programming algorithm.
• eulerian_path.h: entry point for computing minimum
  Eulerian paths and cycles on
  undirected graphs.

Graph decompositions:

• connected_components.h: entry point for computing
  connected components in an undirected graph. (It does not need an explicit
  graph class.)
• strongly_connected_components.h: entry
  point for computing the strongly connected components of a directed graph.
• cliques.h: entry point for computing maximum cliques and clique
  covers in a directed graph, based on the Bron-Kerbosch algorithm.(It does not
  need an explicit graph class.)

Flow algorithms:

• linear_assignment.h: entry point for solving linear
  sum assignment problems (classical assignment problems where the total cost is
  the sum of the costs of each arc used) on directed graphs with arc costs,
  based on the Goldberg-Kennedy push-relabel algorithm.
• max_flow.h: entry point for computing maximum flows on
  directed graphs with arc capacities, based on the Goldberg-Tarjan push-relabel
  algorithm.
• min_cost_flow.h: entry point for computing minimum-cost
  flows on directed graphs with arc capacities, arc costs, and supplies/demands
  at nodes, based on the Goldberg-Tarjan push-relabel algorithm.

Class design Copy Chapter

BaseGraph is a generic graph interface on which most algorithms can be built
and provides efficient implementations with a fast construction time. Its design
is based on the experience acquired in various graph algorithm implementations.

The main ideas are:

• Graph nodes and arcs are represented by integers.

• Node or arc annotations (weight, cost, ...) are not part of the graph class,
  they can be stored outside in one or more arrays and can be easily retrieved
  using a node or arc as an index.

Terminology Copy Section

An arc (or forward arc) of a graph is directed and going from a tail node
to a head node.

graph TD;
tail -->|arc| head;

Node and arc indices are of type NodeIndexType and ArcIndexType
respectively. Those default to int32_t, which allows representing most
practical graphs, but applications that have smaller graphs can improve memory
usage and locality by parameterizing the graph type (e.g. BaseGraph allows representing graphs with up to 65k nodes and arcs).

A node or arc index is valid if it represents a node or arc of the graph. The
validity ranges are always [0, num_nodes()) for nodes and [0, num_arcs())
for forward arcs. For example, the following graph has 4 nodes numbered 0
through 3 and 5 forward arcs numbered 0 through 4:

graph TD;
0-->|0| 1;
2-->|1| 1;
0-->|2| 2;
3-->|3| 3;
1-->|4| 2;

Some graph implementations also store reverse arcs and can be used for
undirected graphs or flow-like algorithms. Reverse arcs are elements of
[-num_arcs(), 0) and are also considered valid by the implementations that
store them. In the following diagram, reverse arcs are represented with dashed
lines. A reverse arc is created for each forward arc (the forward and
reverse arc in this pair are called opposite of each other). This possibly
results in multiarcs:

graph TD;
0-->|0| 1;
1-.->|-1| 0;
2-->|1| 1;
1-.->|-2| 2;
0-->|2| 2;
2-.->|-3| 0;
3-->|3| 3;
3-.->|-4| 3;
1-->|4| 2;
2-.->|-5| 1;

Graph traversal

• The outgoing arcs of a node v are the forward arcs whose tail is v.
• The incoming arcs of v are the forward arcs whose head is v.
• The opposite incoming arcs of v are the opposite arcs of the incoming
  arcs for v.

Forward graph classes allow iteration on outgoing arcs using accessor
OutgoingArcs(). Graph classes with both forward and reverse arcs additionally
provide IncomingArcs and OppositeIncomingArcs(), that return iterators for
the two other categories. They also provide OutgoingOrOppositeIncomingArcs(),
which allows iterating both outgoing and opposite incoming arcs at the same
time, which corresponds to iterating forward and reverse arcs leaving the
node.

Graph implementations Copy Section

• ListGraph<>: Simplest API. Iterating outgoing arcs requires 2 + degree
  memory loads.

• StaticGraph<>: More memory and speed efficient than ListGraph<>, but
  requires calling Build() once after adding all nodes and arcs. Iterating
  outgoing arcs requires only 2 memory loads.

• ReverseArcListGraph<> adds reverse arcs to ListGraph<>. Iterating
  neighboring arcs for a node requires O(degree) memory loads.

• ReverseArcStaticGraph<> adds reverse arcs to StaticGraph<>. Iterating
  neighboring arcs for a node requires O(1) memory loads.

• CompleteGraph<>: If you need a fully connected graph. O(1) memory usage
  and much faster than explicitly storing nodes and arcs using
  StaticGraph<>.

• CompleteBipartiteGraph<>: If you need a fully connected bipartite graph.
  O(1) memory usage and much faster than explicitly storing nodes and arcs
  using StaticGraph<>.

• FlowGraph<>: A graph specialized for max-flow/min-cost-flow algorithms.
  For max-flow or min-cost-flow we need a directed graph where each arc from
  tail to head has a reverse arc from head to tail. In practice many input
  graphs already have such reverse arc and it can make a big difference just
  to reuse them. This is similar to ReverseArcStaticGraph but handles
  reverse arcs in a different way. Instead of always creating a new reverse
  arc for each arc of the input graph, this detects if a reverse arc is
  already present in the input, and does not create a new one when this is the
  case. In the best case, this can gain a factor 2 in the final graph size,
  note however that the graph construction is slightly slower because of this
  detection.

Wrappers Copy Chapter

• python: This directory contains the pybind11 bindings to make
  these C++ libraries available in Python.
• java: the SWIG code that makes the wrapper available in Java and its
  unit tests.
• csharp: the SWIG code that makes the wrapper available in C# and
  its unit tests.

Samples Copy Chapter

You can find some canonical examples in samples.

Overview (`ortools/java/README.md`) Copy Section

Introduction

This is the documentation page for the Java wrapper of OR-Tools.

This project aim to explain how you build a Java 1.8 native (for win32-x86-64,
linux-x86-64 and darwin-x86-64) maven multiple package using mvn
and few POM.xml.

Table of Content Copy Chapter

• Requirement
• Directory Layout
• Build Process
  • Local Package
  • Building a native Package
  • Building a Local Package
  • Testing the Local Package
• Appendices
  • Resources
• Misc

Requirement Copy Chapter

You'll need a "Java SDK >= 1.8" and "Maven >= 3.6".

Directory Layout Copy Chapter

• pom-native.xml.in POM template to build the native
  project.
• com/google/ortools/Loader.java Helper to
  unpack and load the correct native libraries.
• pom-local.xml.in POM template to build the "pure" Java
  project.
• pom-sample.xml.in POM template used to build samples
  and examples.
• pom-test.xml.in POM template used to build tests.

Build Process Copy Chapter

To Create a native dependent package we will split it in two parts:

• A bunch of com.google.ortools:ortools-{platform} maven packages for each
  supported platform targeted and containing the native libraries.
• A java maven package com.google.ortools:ortools-java depending on the native
  package and containing the Java code.

platform names
come from the JNA project (Java Native Access) which will be use to find at
runtime on which platform the code is currently running.

Local Package Copy Section

The pipeline for linux-x86-64 should be as follow:
note: The pipeline will be similar for darwin-x86-64 and win32-x86-64
architecture, don't hesitate to look at the CI log!

Building local native Package

Thus we have the C++ shared library libortools.so and the SWIG generated JNI
wrappers libjniortools.so.

So first let's create the local com.google.ortools:ortools-{platform}.jar
maven package.

Here some dev-note concerning this POM.xml.

• This package is a native package only containing native libraries.

Then you can generate the package and install it locally using:

mvn package
mvn install

note: this will automatically trigger the mvn compile phase.

If everything good the package (located in
/java/ortools-/target/) should have this layout:

{...}/target/ortools-<platform>-1.0.jar:
\- <platform>
   \-libortools.so.8.0
   \-libjniortools.so
...

note: `` could be linux-x86-64, darwin-x86-64 or win32-x86-64.

tips: since maven package are just zip archive you can use unzip -l .jar
to study their layout.

Building local Package

Standard Maven Package

So now, let's create the local com.google.ortools:ortools-java.jar maven
package which will depend on our previous native package.

Here some dev-note concerning this POM.xml.

• Add runtime dependency on each native package(s) available:
  xml Copy

  <dependency>
    <groupId>com.google.ortools</groupId>
    <artifactId>ortools-linux-x86-64</artifactId>
    <version>[8.0,)</version>
    <type>jar</type>
    <scope>runtime</scope>
  </dependency>

  • Add dependency to jna so we can find at runtime the current ``:
  xml Copy

  <dependency>
    <groupId>net.java.dev.jna</groupId>
    <artifactId>jna-platform</artifactId>
    <version>5.14.0</version>
  </dependency>

Then you can generate the package using:

mvn package
mvn install

If Maven executes these commands successfully, the package (located in
/temp_java/ortools-java/target/) should have this layout:

{...}/target/ortools-java-{build version}.jar:
\- com/
   \- google/
      \- ortools/
         \- Loader$PathConsumer.class
         \- Loader$1.class
         \- Loader.class
         \- constraintsolver/
            \- RoutingModel.class
            \- RoutingIndexManager.class
            \- ...
         \- ...
...

Dependency-inclusive Maven Package (fat .jar)

We can also create a Maven package that includes all of its own dependencies,
also known as a 'fat .jar'. This is useful for situations in which it is more
convenient, or even necessary, to use a single .jar as a dependency for a Java
OR-Tools project.

One example is when OR-Tools is compiled with third-party solver support (such
as CPLEX or XPress), and one needs to build and execute in an environment that
does not have access to one's local Maven repository (for example, a
remotely-built Docker container).

Building a fat .jar with all dependencies included (including the native
package) allows one to have a single dependency, namely
com.google.ortools:ortools-java.jar, which can be marked as
<scope>provided</scope> in one's project pom.xml:

<dependency>
  <groupId>com.google.ortools</groupId>
  <artifactId>ortools-java</artifactId>
  <version>{insert build version here}</version>
  <scope>provided</scope>
</dependency>

One would then make this fat .jar available in the execution environment's Java
classpath, for example:

java -cp "/path/to/dependency.jar" -jar "/path/to/your/executable/.jar"

There are several ways to make the fat .jar dependency available to your Java
program - please consult JDK documentation (this links to
OpenJDK 15 documentation), as well as documentation for any packaging and/or
execution frameworks/tools you may be using.

To package a fat .jar with Maven, run

mvn package -Dfatjar=true

To then (optionally) install it to your local Maven repository, run

mvn install

Note that this will replace any previously downloaded or built 'non-fat-.jar'
ortools-java packages in your local Maven repository

If Maven executes these commands successfully, the package (located in
/temp_java/ortools-java/target/) should have this layout:

{...}/target/ortools-java-{build version}.jar:
\- com/
   \- google/
      \- ortools/
         \- Loader$PathConsumer.class
         \- Loader$1.class
         \- Loader.class
         \- constraintsolver/
            \- RoutingModel.class
            \- RoutingIndexManager.class
            \- ...
         \- ...
...

Testing local Package

We can test everything is working by using any sample project.

First you can build it using:

cmake --build build

note: ortools-java which is locally installed in the local maven cache
(~/.m2/repository/com/google/ortools/ortools-java/...).

Then you can run it using:

cmake --build build --target test

or manually using:

cd <builddir>/java/component/example
mvn compile
mvn exec:java

Appendices Copy Chapter

Few links on the subject...

Resources Copy Section

• POM.xml reference
• Maven Central POM requirement
• Maven Javadoc Plugin
• Maven Source Plugin
• Maven GPG Plugin
• Maven Assembly Plugin
• Java Native Access Project

Misc Copy Chapter

Image has been generated using plantuml:

plantuml -Tsvg docs/{file}.dot

So you can find the dot source files in docs.

Overview (`ortools/linear_solver/README.md`) Copy Section

Linear Programming (LP) and Integer Programming (IP) Solver

Linear optimization problems are common throughout Google, and the Operations
Research team has a few ways to help with them.

These models have the form:
$$\begin{array}{lll}
(P) & \max & cx\
& s.t. & L\leq Ax\leq U\
& & l\leq x\leq u\
& &x_i\in\mathbb{Z}\quad\forall i\in I
\end{array}$$

Where $$A\in\mathbb{R}^{m\times n}$$, $$l,u,c\in\mathbb{R}^n$$,
$$L,U\in\mathbb{R}^m$$, $$n,m\in\mathbb{N}^+$$ and $$I\subseteq{1,\ldots,n}$$.

This module provides:

• The MPModelRequest Proto API (in linear_solver.proto) for modeling an
  optimization problem.
• The function SolveMPModel() (in solve_mp_model.h) for solving an
  optimization problem with a solver (Glop, Bop, Sat, SCIP, Gurobi etc.)
• ModelBuilder (in model_builder.h) and similar classes in Python and Java
  to help construct an MPModelRequest (e.g. to provide linear expressions).
• MPSolver which is no longer in development. MPSolver is largely
  interoperable with the MPModelRequest API, although the features supported
  are not identical.

To begin, skim

• linear_solver.proto:
  Specifically, look at MPModelProto. This gives a succinct description of
  what problems can be solved.

• solve_mp_model.h:
  This file contains the key functions to run various solvers.

Available solvers Copy Chapter

Each *_interface.cc file corresponds to one of the solver accessible
through the wrapper.

• Google's BOP (boolean) solver: bop_interface.cc

• Google's GLOP (lp) solver: glop_interface.cc

• Gurobi (MIP) solver: gurobi_interface.cc

• Google's PLDP solver: pdlp_interface.cc

• SCIP (MIP) solver: scip_interface.cc

• Google's CP-SAT solver: sat_interface.cc

• Coin-OR Cbc (MIP) solver: cbc_interface.cc

• Coin-OR Clp (LP) solver: clp_interface.cc

• CPLEX (MIP) solver: cplex_interface.cc

• GLPK (MIP) solver: glpk_interface.cc

• Xpress (MIP) solver: xpress_interface.cc

Wrappers Copy Chapter

• python: the SWIG code that makes the wrapper available in Python,
  and its unit tests.

• java: the SWIG code that makes the wrapper available in Java,
  and its unit tests.

• csharp: the SWIG code that makes the wrapper available in C#,
  and its unit tests.

Samples Copy Chapter

You can find some canonical examples in samples

Overview (`ortools/lp_data/README.md`) Copy Section

LP Data

This directory contains a rich collection of C++ libraries for handling Linear
Programming (LP) data structures.

It provides core components for representing, manipulating, and solving linear
programs, with a focus on efficient handling of sparse data and various utility
functions for pre-processing and analysis.

Core Data Structures Copy Chapter

This set of libraries provides the fundamental building blocks for representing
and working with linear programming problems.

• lp_types.h: Defines common types and constants used throughout
  the linear programming solver.
• lp_data.h: Provides the main LinearProgram class for storing
  the complete data of a linear program, including the objective function,
  constraint matrix, and variable bounds.
• lp_utils.h: Contains basic utility functions for operations on
  fractional numbers and row/column vectors.

Sparse Data Representation Copy Chapter

Given that large-scale linear programs are often sparse, this directory offers a
suite of libraries for efficient sparse data handling.

• sparse.h: Implements data structures for sparse matrices, based
  on well-established references in the field of direct methods for sparse
  matrices.
• sparse_vector.h: Provides classes to represent sparse
  vectors efficiently.
• sparse_column.h & sparse_row.h:
  Specializations of sparse vectors for column-oriented and row-oriented matrix
  storage schemes.
• scattered_vector.h: Implements vectors that offer a
  sparse interface to what is internally a dense storage, which can be useful
  for certain computations.

LP Solvers and Utilities Copy Chapter

A collection of tools for preprocessing, analyzing, and manipulating linear
programs.

• matrix_scaler.h: Provides the SparseMatrixScaler class,
  which scales a SparseMatrix to improve numerical stability during the
  solving process.
• lp_decomposer.h: Implements a tool to decompose a large
  LinearProgram into several smaller, independent subproblems by identifying
  disconnected components in the constraint matrix.
• permutation.h: Contains utilities for handling row and
  column permutations on LP data structures.

Parsers and I/O Utilities Copy Chapter

This group of libraries handles reading and writing LP data in various formats.

• lp_parser.h: A simple parser for creating a linear program
  from a string representation.
• mps_reader.h: A reader for the industry-standard MPS file
  format for mathematical programming problems.
• sol_reader.h: A reader for .sol files, which are used to
  specify solution values for a given model.
• proto_utils.h: Provides utilities to convert
  LinearProgram objects to and from the MPModelProto protobuf format.
• lp_print_utils.h: Contains utilities to display linear
  expressions in a human-readable way, including rational approximations.

Overview (`ortools/math_opt/README.md`) Copy Section

math_opt

The code in this directory provides a generic way of accessing mathematical
optimization solvers (sometimes called mathematical programming solvers), such
as GLOP, CP-SAT, SCIP and Gurobi. In particular, a single API is provided to
make these solvers largely interoperable.

New code should prefer MathOpt to MPSolver, as defined in
linear_solver.h
when possible.

MathOpt has client libraries in C++, Python, and Java that most users should use
to build and solve their models. A proto API is also provided, but this is not
recommended for most users.

See
parameters.proto
for the list of supported solvers.

Overview (`ortools/packing/README.md`) Copy Section

Packing

This folder contains utilities and solvers for several packing problems:
knapsack and bin packing, including generalizations. The solvers take as input a
problem description in ProtoBuf.

Knapsack Copy Chapter

A typical knapsack problem considers a single container (the knapsack) and many
items. The container has a maximum capacity, items have both a weight and a
value. The goal is to find the subset of items that respects the capacity
constraint and has the maximum value. There can be only one container. More
generally, the knapsack problem models resource allocation.

More information on Wikipedia.

Multi-dimensional knapsack solver:

• algorithms/knapsack_solver.h

Bin packing Copy Chapter

In an instance of the bin-packing problem, the goal is to use the minimum amount
of bins to fit a series of items of varying size. Vector bin packing (VBP)
considers several dimensions for item size and bin capacity.

More information on
Wikipedia.

Vector bin packing:

• Problem description: vector_bin_packing.proto
• Solver: arc_flow_solver.h
• VBP parser: vector_bin_packing_parser.h

2D bin packing:

• Problem description:
  multiple_dimensions_bin_packing.proto

Overview (`ortools/pdlp/README.md`) Copy Section

Primal-Dual Hybrid Gradient Solver (PDLP)

This directory contains PDLP, a library for solving linear programming (LP) and
quadratic programming (QP) problems using first-order methods.

The implementation is based on the Primal-Dual Hybrid Gradient (PDHG) algorithm,
which is preprocessed with scaling and optional presolving to improve
performance and numerical stability. See also
Mathematical background for PDLP.

Core C++ libraries: Copy Chapter

• primal_dual_hybrid_gradient.h: The main
  entry point PrimalDualHybridGradient() for the solver, which takes a
  QuadraticProgram and solver parameters.
• quadratic_program.h: Defines the QuadraticProgram
  struct to represent the optimization problem, including objective vectors,
  constraint matrices, and bounds.
• quadratic_program_io.h: Provides utilities to read
  quadratic programs from various file formats, including MPS and MPModelProto.
• sharded_quadratic_program.h and
  sharder.h: These provide the infrastructure for sharding
  problem data and performing parallel computations.
• scheduler.h: A thread scheduling interface that supports
  multiple backends (e.g. Eigen's thread pools).
• iteration_stats.h and
  termination.h: Contain logic for computing convergence and
  infeasibility statistics and checking termination criteria.

Configuration and Logging Copy Chapter

• solvers.proto: Defines the PrimalDualHybridGradientParams
  message for configuring the solver, including termination criteria,
  algorithmic choices like restart strategies, and linesearch rules.
• solve_log.proto: Defines messages for logging the
  solver's progress and final result, such as IterationStats and SolveLog.

Wrappers and Samples Copy Chapter

• python/: Contains the pybind11 wrapper to expose the C++ library
  to Python, along with its build definitions and tests.
• samples/: This directory provides example usage of the library.

Overview (`ortools/python/README.md`) Copy Section

Introduction

This is the documentation page for the Python 3.9+ wrapper of OR-Tools.

This project aim to explain how you build a Python native wheel package using
setup.py.

Table of Content Copy Chapter

• Requirement
• Directory Layout
• Build Process
  • Local Package
  • Building a native Package
• Appendices
  • Resources
• Misc

Requirement Copy Chapter

You'll need "Python >= 3.9" and few python modules ("wheel" and "absl-py").

Directory Layout Copy Chapter

• setup.py.in Setup.py template to build the python native
  project.

Build Process Copy Chapter

To Create a native dependent package which will contains two parts:

• A bunch of native libraries for the supported platform targeted.
• The Python code depending on it.

note: Since Pypi.org support multiple packages, we will
simply upload one package per supported platform.

Local Package Copy Section

The pipeline for linux-x86-64 should be as follow:
note: The pipeline will be similar for other architectures, don't hesitate to
look at the CI log!

Building local native Package

Thus we have the C++ shared library libortools.so and the SWIG generated
Python wrappers e.g. pywrapsat.py in the same package.

Here some dev-note concerning this setup.py.

• This package is a native package containing native libraries.

Then you can generate the package and install it locally using:

python3 setup.py bdist_wheel
python3 -m pip install --user --find-links=dist ortools

If everything good the package (located in /python/dist) should have
this layout:

{...}/dist/ortools-X.Y.9999-cp3Z-cp3Z-<platform>.whl:
\- ortools
   \- __init__.py
   \- .libs
      \- libortools.so
   \- constraint_solver
      \- __init__.py
      \- pywrapcp.py
      \- _pywrapcp.so
   \- ...
      \- __init__.py
      \- pywrap....py
      \- _pywrap....so
...

note: `` could be manylinux2014_x86_64, macosx_10_9_x86_64 or win-amd64.

tips: since wheel package are just zip archive you can use unzip -l .whl
to study their layout.

Appendices Copy Chapter

Few links on the subject...

Resources Copy Section

• Packaging Python Project
• PEP 513 -- A Platform Tag for Portable Linux Built Distributions
• PEP 571 -- The manylinux2010 Platform Tag
• PEP 600 Future 'manylinux' Platform Tags

Misc Copy Chapter

Image has been generated using plantuml:

plantuml -Tsvg docs/{file}.dot

So you can find the dot source files in docs.

Overview (`ortools/routing/README.md`) Copy Section

Routing

Vehicle Routing is a useful
extension that is implemented on top of the CP solver library.

Routing solver Copy Chapter

To begin, skim:

• ../constraint_solver/routing.h: The
  vehicle routing library lets one model and solve generic vehicle routing
  problems ranging from the Traveling Salesman Problem to more complex
  problems such as the Capacitated Vehicle Routing Problem with Time Windows.

Parameters Copy Section

• ../constraint_solver/routing_parameters.proto:
  The Vehicle Routing solver parameters.
• ../constraint_solver/routing_enums.proto:
  Enums used to define routing parameters.

Solution Copy Section

• ../constraint_solver/assignment.proto:
  Holds the solution of a Routing problem (as a special case of a CS problem).

Parsers Copy Chapter

Utilities for file formats are in the
parsers subfolder.

Overview (`ortools/sat/README.md`) Copy Section

CP-SAT

This directory contains a next-gen Constraint Programming (CP) solver with
clause learning. It is built on top of an efficient SAT/max-SAT solver whose
code is also in this directory.

The technology started in 2009. A complete presentation is available
here.

CP-SAT was described during the CPAIOR 2020 masterclass. The recording is
available here.

To begin, skim
cp_model.proto to
understand how optimization problems can be modeled using the solver. You can
then solve a model with the functions in
cp_model_solver.h.

Parameters Copy Chapter

• sat_parameters.proto:
  The SAT solver parameters. Also contains max-SAT and CP parameters.

Model Copy Chapter

The optimization model description and related utilities:

• cp_model.proto:
  Proto describing a general Constraint Programming model.
• cp_model_utils.h:
  Utilities to manipulate and create a cp_model.proto.
• cp_model_checker.h:
  Tools to validate cp_model.proto and test a solution feasibility.
• cp_model_solver.h:
  The solver API.
• cp_model_presolve.h:
  Presolve a cp_model.proto by applying simple rules to simplify a subsequent
  solve.

SAT solver Copy Chapter

Standalone SAT solver and related files. Note that this is more than a basic
SAT solver as it already includes non-clause constraints. However, these do not
work on the general integer problems that the CP solver handles.

Pure SAT solver:

• sat_base.h: SAT
  core classes.
• clause.h: SAT clause
  propagator with the two-watcher mechanism. Also contains propagators for
  binary clauses.
• sat_solver.h:
  The SatSolver code.
• simplification.h:
  SAT postsolver and presolver.
• symmetry.h:
  Dynamic symmetry breaking constraint in SAT. Not used by default.

Extension:

• pb_constraint.h:
  Implementation of a Pseudo-Boolean constraint propagator for SAT.
  Pseudo-Boolean constraints are simply another name used in the SAT community
  for linear constraints on Booleans.
• no_cycle.h:
  Implementation of a no-cycle constraint on a graph whose arc presences are
  controlled by Boolean. This is a SAT propagator, not used in CP.
• encoding.h: Basic
  algorithm to encode integer variables into a binary representation. This is
  not used by the CP solver, just by the max-SAT core based algorithm in
  optimization.h.

Input/output:

• drat_writer.h:
  Write UNSAT proof in the DRAT format. This allows to check the correctness
  of an UNSAT proof with the third party program DRAT-trim.
• opb_reader.h:
  Parser for the .opb format for Pseudo-Boolean optimization problems.
• sat_cnf_reader.h:
  Parser for the classic SAT .cnf format. Also parses max-SAT files.
• boolean_problem.proto:
  Deprecated by cp_model.proto.

CP solver Copy Chapter

CP solver built on top of the SAT solver:

• integer.h: The
  entry point, which defines the core of the solver.

Basic constraints: Copy Section

• all_different.h:
  Propagation algorithms for the AllDifferent constraint.
• integer_expr.h:
  Propagation algorithms for integer expression (linear, max, min, div, mod,
  ...).
• table.h: Propagation
  algorithms for the table and automaton constraints.
• precedences.h:
  Propagation algorithms for integer inequalities (integer difference logic
  theory).
• cp_constraints.h:
  Propagation algorithms for other classic CP constraints (XOR, circuit,
  non-overlapping rectangles, ...)
• linear_programming_constraint.h:
  Constraint that solves an LP relaxation of a set of constraints and uses the
  dual-ray to explain an eventual infeasibility. Also implements reduced-cost
  fixing.
• flow_costs.h:
  Deprecated. Network flow constraint. We use the generic
  linear_programming_constraint instead.

Scheduling constraints: Copy Section

• intervals.h:
  Definition and utility for manipulating "interval" variables (a.k.a. task or
  activities). This is the basic CP variable type used in scheduling problems.
• disjunctive.h:
  Propagation algorithms for the disjunctive scheduling constraint.
• cumulative.h,
  timetable.h,
  timetable_edgefinding.h:
  Propagation algorithms for the cumulative scheduling constraint.
• cumulative_energy.h:
  Propagation algorithms for a more general cumulative constraint.

Packing constraints Copy Section

• diffn.h: 2D
  no_overlap constraints (aka non overlapping rectangles). Note these use 2
  intervals, one for each dimension to represent a rectangle.
• diffn_util.h:
  rectangle utilities.

Linear relaxation Copy Section

• linear_constraint.h:
  Data structure to represent a linear constraint: lb <= sum (ai * xi) <= ub.
• linear_constraint_manager.h:
  Utility to manage a set of linear constraints (addition, removal,
  sorting...)
• linear_programming_constraint.h:
  Sat propagator that interact with the simplex. It propagates variables
  bounds from the SAT solver to the simplex, and extract dual information from
  the simplex to be used by the sat solver.
• linear_model.h:
  Represents a relaxed view of the model as a set of linear constraints.
• linear_relaxation.h:
  Builds the static (linear model) and the dynamic (cut generators) linear
  view of a cp_model.
• cuts.h: Data Data
  structures and cut generators for the integer constraints.
• routing_cuts.h:
  Data structures and cut generators for the routing constraints (circuit and
  routes).
• scheduling_cuts.h:
  Data structures and cut generators for the scheduling constraints
  (no_overlap and cumulative).
• diffn_cuts.h:
  Data structures and cut generators for the packing constraints
  (no_overlap_2d).

Other Copy Chapter

• model.h: Generic
  class that implements a basic dependency injection framework for singleton
  objects and manages the memory ownership of all the solver classes.
• optimization.h:
  Algorithms to solve an optimization problem using a satisfiability solver as
  an opaque-box.
• lp_utils.h:
  Utility to scale and convert a MIP model into CP.

Recipes Copy Chapter

You can find a set a code recipes in
the documentation directory.

Overview (`ortools/set_cover/README.md`) Copy Section

Set covering

An instance of set covering is composed of two entities: elements and sets; sets
cover a series of elements. The problem of set covering is about finding the
cheapest combination of sets that cover all the elements.

More information on Wikipedia.

• Solver: set_cover_heuristics.h.
• Instance representation: set_cover_model.h.
• Instance parser: set_cover_reader.h.

Create an instance:

// If the elements are integers, a subset can be a std::vector<int> (in a pair
// along its cost).
std::vector<std::pair<std::vector<int>, int>> subsets = ...;

SetCoverModel model;
for (const auto [subset, subset_cost] : subsets) {
  model.AddEmptySubset(subset_cost)
  for (const int element : subset) {
    model.AddElementToLastSubset(element);
  }
}
SetCoverLedger ledger(&model);

Solve it using a MIP solver (guarantees to yield the optimum solution if it has
enough time to run):

SetCoverMip mip(&ledger);
mip.SetTimeLimitInSeconds(10);
mip.NextSolution();
SubsetBoolVector best_choices = ledger.GetSolution();
LOG(INFO) << "Cost: " << ledger.cost();

A custom combination of heuristics (10,000 iterations of: clearing 10% of the
variables, running a Chvatal greedy descent, using steepest local search):

Cost best_cost = std::numeric_limits<Cost>::max();
SubsetBoolVector best_choices = ledger.GetSolution();
for (int i = 0; i < 10000; ++i) {
  ledger.LoadSolution(best_choices);
  ClearRandomSubsets(0.1 * model.num_subsets().value(), &ledger);

  GreedySolutionGenerator greedy(&ledger);
  CHECK(greedy.NextSolution());

  SteepestSearch steepest(&ledger);
  CHECK(steepest.NextSolution(10000));

  EXPECT_TRUE(ledger.CheckSolution());
  if (ledger.cost() < best_cost) {
    best_cost = ledger.cost();
    best_choices = ledger.GetSolution();
    LOG(INFO) << "Better cost: " << best_cost << " at iteration = " << i;
  }
}
ledger.LoadSolution(best_choices);
LOG(INFO) << "Best cost: " << ledger.cost();

Overview (`tools/docker/README.md`) Copy Section

CI: Makefile/Docker testing

To test the build on various distro, we are using docker containers and a
Makefile for orchestration.

pros:

• You are independent of third party CI runner config (e.g. github actions
  runners).
• You can run it locally on any unix system.
• Most CI provide runner with docker and Makefile installed.

cons:

• Only GNU/Linux distro supported.
• Could take few GiB (~50 GiB for all distro and all languages)
  • ~500MiB OS + C++/CMake tools,
  • ~150 MiB Python, wheel.

Usage Copy Chapter

To get the help simply type:

make

note: you can also use from top directory

make --directory=tools/docker

Example Copy Section

For example to test inside an Alpine container:

make alpine-edge_test

Docker layers Copy Chapter

Dockerfile is split in several stages.

Legend:

• ``: amd64, arm64, riscv64.
• <distro>: alpine-edge, archlinux, centos, debian, fedora, opensuse, ubuntu.
• <lang>: cpp, dotnet, java, python.

Docker `aarch64` on `x86_64` machine Copy Section

You can build and run aarch64 docker container on a x86_64 by enabling qemu
support:

docker run --rm --privileged multiarch/qemu-user-static --reset -p yes

To test:

docker run --platform linux/arm64 --rm --init -it ubuntu:latest bash -c "uname -a"

ref:

• https://github.com/docker-library/official-images#architectures-other-than-amd64
• https://github.com/multiarch/qemu-user-static#getting-started

Overview (`tools/testing/README.md`) Copy Section

Binary testing

This folder contains facilities to test executable files.
We offer two APIs:

• bintest: A simple scripting language to write simple tests such as
  checking execution success or asserting the presence of text or numbers
  within bounds,
• py_bintest: An extension of the unit testing framework that makes it easy
  to invoke the binary under test, extract values from its output, and check
  them within the unittest framework.

`bintest` Copy Chapter

It offers two commands RUN: and CHECK:.

• The RUN: command executes the binary and asserts it ran successfully.
  The passed arguments can use the $(<label>) construct to refer to binary
  or data files. These labels are initialized from the named_data attribute
  of the BUILD rule.
• The CHECK: command takes one or more matchers and asserts that they all
  match the binary output.
  If several matchers are passed to a single CHECK: command, they need to
  match in the specified order.
  Several CHECK: lines can be used after a call to RUN:, they are all
  independently checking the same output and must all succeed.

Empty lines or lines starting with # are not taken into account. Other command
will fail with an error message.

An example Copy Section

The print_args binary is used as an example.

// Snippet from tools/testing/print_args.cc
// This program prints a "Hello world!" message and its command-line arguments,
// one per line.
//
// It has a few options:
//  --fail: If present, the program will exit with a non-zero status code.
//  --stderr: This argument and the following ones are printed to stderr instead
//            of stdout.
//  --file=<file>: Prints the content of the file.
//
// Example usage:
//  print_args --fail --stderr arg1 arg2
//
// This will print:
//  Hello world!
//  --fail
// to stdout, and
//  --stderr
//  arg1
//  arg2
// to stderr, and exit with a non-zero status code.
int main(int argc, char** argv) {
  const std::string file_flag("--file=");
  puts("Hello world!");
  int return_code = EXIT_SUCCESS;
  FILE* out_file = stdout;
  for (int i = 1; i < argc; ++i) {
    const std::string arg = argv[i];
    std::string output = arg;
    if (arg == "--fail") {
      return_code = EXIT_FAILURE;
    } else if (arg == "--stderr") {
      out_file = stderr;
    } else if (arg.starts_with(file_flag)) {
      std::ifstream stream(arg.substr(file_flag.size()));
      std::stringstream buffer;
      buffer << stream.rdbuf();
      output = buffer.str();
    }
    fprintf(out_file, "%s\n", output.c_str());
  }
  return return_code;
}

Using the bintest rule we can test its behavior.

bintest(
    name = "print_args_bintest",
    srcs = ["print_args.bintest"],
    named_data = {
        "print_args": ":print_args",
        "data_file": ":print_args_data.txt",
    },
)

# Snippet from tools/testing/print_args.bintest
# Running the binary with no argument prints "Hello world!"
RUN: $(print_args)
CHECK: "Hello world!"

# Running the binary with arguments also prints the arguments verbatim.
RUN: $(print_args) --value=0.99999999
CHECK: "Hello world!" "--value=@num(1)"

RUN: $(print_args) a=1 b=54.7 c=12
CHECK: "a=@num(>0)" "b=@num(55~1)" "c=@num(>10, <15)"

# Passing a named variable should be expanded, here we pass the binary path to
# itself.
RUN: $(print_args) --input=$(print_args)
CHECK: "print_args"

# Passing quoted strings
RUN: $(print_args) "Double quoted" 'Single quoted'
CHECK: "Hello world!" "Double quoted" "Single quoted"

# Capturing stderr
RUN: $(print_args) --stderr "written to stderr" 2>&1
CHECK: "written to stderr"

# Expanding side data file
RUN: $(print_args) --file=$(data_file)
CHECK: "This file contains side data."

Matchers Copy Chapter

Matchers are single or double quoted strings passed to the CHECK: command.
They may contain @num() directives.

Here are a few examples:

NOTE: This framework is intentionally simple and does not support regex.
For more complex scenarios use py_bintest below.

`py_bintest` Copy Chapter

Using the py_bintest rule we can write Python tests that invoke the binary and
collect their output. The framework provides functions to match the output using
the same language as in the simple bintest scripts, and extract values out of
it. The extracted values can then be tested using the standard testing API.

Similarly to bintest above, text of the form $(<label>) in the command line
arguments is expanded using the named_data attribute of the
BUILD rule.

py_bintest(
    name = "print_args_test",
    srcs = ["print_args_test.py"],
    named_data = {
        "print_args": ":print_args",
        "data_file": ":print_args_data.txt",
    },
    deps = ["//testing/pybase"], # MOE:replace deps = [requirement("absl-py")],
)

Here is a usage example based on the same print_args binary.

/* Detailed source-code truncated for AI context efficiency. */

NOTE: Python already has all the infrastructure to test values and so the
extract command only accepts num@() as a placeholder. Contrary to bintest
above it will not accept numerical constraints.

Overview (`ortools/constraint_solver/docs/README.md`) Copy Section

Overview

You can find here the documentation for the two following OR-Tools components.

• CP Solver

  Constraint programming (CP) is the name given to identifying feasible
  solutions out of a very large set of candidates, where the problem can be
  modeled in terms of arbitrary constraints.

  note: We strongly recommend using the CP-SAT solver
  rather than the original CP solver.

• Routing Solver

  A specialized library for identifying best vehicle routes given constraints.

  This library extension is implemented on top of the CP Solver library.

Overview (`ortools/julia/ORTools.jl/README.md`) Copy Section

ORTools

This is the
MathOptInterface.jl Julia
wrapper for Google's
MathOpt.

Overview (`ortools/julia/ORToolsBinaries.jl/README.md`) Copy Section

ORToolsBinaries

This package, upon installation, downloads the latest OR-Tools binaries from
GitHub. This is especially useful on platforms like Windows or ARM64/Aarch64
because no JLL is available for them.

This package otherwise provides the same interface as
ORTools_jll.jl,
i.e. a global variable libortools that contains the path to the local copy
of OR-Tools.

Overview (`ortools/math_opt/elemental/README.md`) Copy Section

Elemental

See go/math-opt-elemental and g/math-opt-dev/c/0cgOO6qkoWM.

Overview (`ortools/routing/parsers/README.md`) Copy Section

Routing

This folder contains utilities for usual file formats useful in routing problems
and utilities directly related to these file formats.

solution_serializer.h contains a generic serializer for routing solutions for
many formats.

In the future, this folder will contain the whole routing solver.

Overview (`ortools/sat/colab/README.md`) Copy Section

CpModel Notebook

Below you'll find three examples of Google's CP-SAT solver.

• The first example solves a logic puzzle
• The second solves a simple job shop problem
• The third example solves a two machine scheduling problem with shared
  resources

Local instance Copy Chapter

Build and run locally:

bazel run -c opt ortools/python:ortools_notebook

This will open a jupyter notebook in your browser.

To use it as a server only, use the command

bazel run -c opt ortools/python:ortools_notebook -- --no-browser

And paste the resulting url in your favorite environment, like visual studio code.

Hidato Problem {#hidato} Copy Chapter

We model the Hidato problem (https://en.wikipedia.org/wiki/Hidato).

/* Detailed source-code truncated for AI context efficiency. */

Jobshop example {#jobshop} Copy Chapter

This example demonstrates jobshop scheduling
(https://en.wikipedia.org/wiki/Job_shop_scheduling)

/* Detailed source-code truncated for AI context efficiency. */

Two Machine Scheduling {#twomachine} Copy Chapter

We have a set of jobs to perform (duration, width). We have two parallel
machines that can perform this job. One machine can only perform one job at a
time. At any point in time, the sum of the width of the two active jobs cannot
exceed a max_width.

The objective is to minimize the max end time of all jobs.

/* Detailed source-code truncated for AI context efficiency. */

Overview (`ortools/sat/docs/README.md`) Copy Section

Using the CP-SAT solver

https://developers.google.com/optimization/cp/cp_solver

Documentation structure Copy Chapter

This document presents modeling recipes for the CP-SAT solver.

Code samples are given in C++, Python, Java, C#, and Go. Each language has
different requirements for the code samples.

Searching for one (optimal) solution of a CP-SAT model Copy Chapter

By default, searching for one solution will return the first solution found if
the model has no objective, or the optimal solution if the model has an
objective.

Python code samples Copy Section

The Python interface to the CP-SAT solver is implemented using two classes.

• The CpModel class proposes modeling methods that creates variables, or
  add constraints. This class completely hides the underlying CpModelProto
  used to store the model.
• The CpSolver class encapsulates the solve API and offers helpers to
  access the solution found by the solve.

# Snippet from ortools/sat/samples/simple_sat_program.py
"""Simple solve."""
from ortools.sat.python import cp_model


def simple_sat_program():
  """Minimal CP-SAT example to showcase calling the solver."""
  # Creates the model.
  model = cp_model.CpModel()

  # Creates the variables.
  num_vals = 3
  x = model.new_int_var(0, num_vals - 1, 'x')
  y = model.new_int_var(0, num_vals - 1, 'y')
  z = model.new_int_var(0, num_vals - 1, 'z')

  # Creates the constraints.
  model.add(x != y)

  # Creates a solver and solves the model.
  solver = cp_model.CpSolver()
  status = solver.solve(model)

  if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f'x = {solver.value(x)}')
    print(f'y = {solver.value(y)}')
    print(f'z = {solver.value(z)}')
  else:
    print('No solution found.')


simple_sat_program()

C++ code samples Copy Section

The interface to the C++ CP-SAT solver is implemented through the
CpModelBuilder class described in
ortools/sat/cp_model.h. This class is just a helper to
fill in the cp_model protobuf.

Calling Solve() method will return a CpSolverResponse protobuf that contains the
solve status, the values for each variable in the model if solve was successful,
and some metrics.

// Snippet from ortools/sat/samples/simple_sat_program.cc
#include <stdlib.h>

#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "absl/base/log_severity.h"
#include "absl/log/globals.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"
#include "ortools/util/sorted_interval_list.h"

namespace operations_research {
namespace sat {

void SimpleSatProgram() {
  CpModelBuilder cp_model;

  const Domain domain(0, 2);
  const IntVar x = cp_model.NewIntVar(domain).WithName("x");
  const IntVar y = cp_model.NewIntVar(domain).WithName("y");
  const IntVar z = cp_model.NewIntVar(domain).WithName("z");

  cp_model.AddNotEqual(x, y);

  // Solving part.
  const CpSolverResponse response = Solve(cp_model.Build());

  if (response.status() == CpSolverStatus::OPTIMAL ||
      response.status() == CpSolverStatus::FEASIBLE) {
    // Get the value of x in the solution.
    LOG(INFO) << "x = " << SolutionIntegerValue(response, x);
    LOG(INFO) << "y = " << SolutionIntegerValue(response, y);
    LOG(INFO) << "z = " << SolutionIntegerValue(response, z);
  } else {
    LOG(INFO) << "No solution found.";
  }
}

}  // namespace sat
}  // namespace operations_research

int main(int argc, char* argv[]) {
  InitGoogle(argv[0], &argc, &argv, true);
  absl::SetStderrThreshold(absl::LogSeverityAtLeast::kInfo);
  operations_research::sat::SimpleSatProgram();
  return EXIT_SUCCESS;
}

Java code samples Copy Section

The Java code implements the same interface as the Python code, with a
CpModel and a CpSolver class.

// Snippet from ortools/sat/samples/SimpleSatProgram.java
package com.google.ortools.sat.samples;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.IntVar;

/** Minimal CP-SAT example to showcase calling the solver. */
public final class SimpleSatProgram {
  public static void main(String[] args) throws Exception {
    Loader.loadNativeLibraries();
    // Create the model.
    CpModel model = new CpModel();

    // Create the variables.
    int numVals = 3;

    IntVar x = model.newIntVar(0, numVals - 1, "x");
    IntVar y = model.newIntVar(0, numVals - 1, "y");
    IntVar z = model.newIntVar(0, numVals - 1, "z");

    // Create the constraints.
    model.addDifferent(x, y);

    // Create a solver and solve the model.
    CpSolver solver = new CpSolver();
    CpSolverStatus status = solver.solve(model);

    if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
      System.out.println("x = " + solver.value(x));
      System.out.println("y = " + solver.value(y));
      System.out.println("z = " + solver.value(z));
    } else {
      System.out.println("No solution found.");
    }
  }

  private SimpleSatProgram() {}
}

C\# code samples Copy Section

The C# code implements the same interface as the Python code, with a
CpModel and a CpSolver class.

// Snippet from ortools/sat/samples/SimpleSatProgram.cs
using System;
using Google.OrTools.Sat;

public class SimpleSatProgram
{
    static void Main()
    {
        // Creates the model.
        CpModel model = new CpModel();

        // Creates the variables.
        int num_vals = 3;

        IntVar x = model.NewIntVar(0, num_vals - 1, "x");
        IntVar y = model.NewIntVar(0, num_vals - 1, "y");
        IntVar z = model.NewIntVar(0, num_vals - 1, "z");

        // Creates the constraints.
        model.Add(x != y);

        // Creates a solver and solves the model.
        CpSolver solver = new CpSolver();
        CpSolverStatus status = solver.Solve(model);

        if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
        {
            Console.WriteLine("x = " + solver.Value(x));
            Console.WriteLine("y = " + solver.Value(y));
            Console.WriteLine("z = " + solver.Value(z));
        }
        else
        {
            Console.WriteLine("No solution found.");
        }
    }
}

Go code samples Copy Section

The interface to the CP-SAT solver is implemented through the CpModelBuilder
described in the package cpmodel in
ortools/sat/go/cp_model.go. This class is a helper to fill
in the cp_model protobuf.

Also within the cpmodel package is
ortools/sat/go/cp_model.go which provides functions to
solve the model along with helpers to access the solution found by the solver.

// Snippet from ortools/sat/samples/simple_sat_program.go
// The simple_sat_program command is an example of a simple sat program.
package main

import (
	"fmt"

	log "github.com/golang/glog"
	"github.com/google/or-tools/ortools/sat/go/cpmodel"

	cmpb "github.com/google/or-tools/ortools/sat/proto/cpmodel"
)

func simpleSatProgram() error {
	model := cpmodel.NewCpModelBuilder()

	domain := cpmodel.NewDomain(0, 2)
	x := model.NewIntVarFromDomain(domain).WithName("x")
	y := model.NewIntVarFromDomain(domain).WithName("y")
	z := model.NewIntVarFromDomain(domain).WithName("z")

	model.AddNotEqual(x, y)

	m, err := model.Model()
	if err != nil {
		return fmt.Errorf("failed to instantiate the CP model: %w", err)
	}
	response, err := cpmodel.SolveCpModel(m)
	if err != nil {
		return fmt.Errorf("failed to solve the model: %w", err)
	}

	switch response.GetStatus() {
	case cmpb.CpSolverStatus_OPTIMAL, cmpb.CpSolverStatus_FEASIBLE:
		fmt.Printf("x = %d\n", cpmodel.SolutionIntegerValue(response, x))
		fmt.Printf("y = %d\n", cpmodel.SolutionIntegerValue(response, y))
		fmt.Printf("z = %d\n", cpmodel.SolutionIntegerValue(response, z))
	default:
		fmt.Println("No solution found.")
	}

	return nil
}

func main() {
	if err := simpleSatProgram(); err != nil {
		log.Exitf("simpleSatProgram returned with error: %v", err)
	}
}

Ortools Julia Docs Index (`ortools/julia/docs/index.md`) Copy Section

Julia wrappers

This folder contains the Julia wrappers for OR-Tools. They are not useable from
within Google3: they are intended for use by the open-source community only.

Note: the wrapper is being written and highly experimental.

For now, only MathOpt is accessible through
its C API.

TODO(user): how to run this on my machine?

TODO(user): generate the Julia files within CMake and export them manually
with Yggdrasil.

Packages Copy Chapter

The Julia wrapper is divided into three Julia packages:

• ORTools_jll
  contains the precompiled OR-Tools binaries.
• ORToolsGenerated.jl
  contains the generated part of the wrapper. For now, this package
  corresponds to Protocol Buffers files.
• ORTools.jl
  is the actual, high-level wrapper (more specifically, the
  MathOptInterface code for
  use through JuMP). It is not yet written.

Maintenance Copy Chapter

When releasing a new version of OR-Tools:

1. Update the binary dependencies in
   ORTools_jll:
   create a public PR on GitHub that edits build_tarballs.jl. At each
   version, you must update two fields:

   • version: to match the version of OR-Tools.
   • GitSource(): to match the Git commit that you want to build.

   Update the rest of the file as required. In particular, you must update the
   installation of the Protocol Buffers files and the list of exported Protocol
   Buffers files any time the new release has new Protocol Buffers files.

2. Update the generated files in
   ORToolsGenerated.jl.
   This step depends on the first one: the PR you wrote at the first step must
   be accepted and merged into the repository. Updating the generated files
   amounts to have a local Julia installation, adding the new version of
   ORTools_jll (within a Julia shell, ]add ORTools_jll the first time, then
   update the version with ]update), and calling the script
   update_package.jl.

3. Synchronize the results of the previous step with OR-Tools' repository: the
   updated files go into ortools/julia/ORToolsGenerated/ (an updated
   Project.toml, new files in src/gen*).

4. Trigger a release of ORToolsGenerated.jl using
   JuliaRegistrator. To
   this end:

   • Find the new commit you created at the previous step in GitHub.

   • Add the following comment to register the
     ortools/julia/ORToolsGenerated.jl as a Julia package:

     text Copy

     @JuliaRegistrator register subdir=ortools/julia/ORToolsGenerated.jl

     If registering from a nondefault branch like julia/dev:

     text Copy

     @JuliaRegistrator register subdir=ortools/julia/ORToolsGenerated.jl branch=julia/dev

   This operation starts an automated process that will publish a new version
   of the ORToolsGenerated.jl package to the
   official Julia package repository. The version
   number is taken from the contents of Project.toml at this Git commit.

5. In case the C API changes, you must update ORTools.jl accordingly: after
   the manual update, follow the steps 3 and 4, replacing ORToolsGenerated.jl
   by ORTools.jl. To register the new version, the command thus looks like:

   text Copy

   @JuliaRegistrator register subdir=ortools/julia/ORTools.jl branch=julia/dev

There is only one set-up action to perform: install Julia's Registrator bot into
OR-Tools' repository (which only needs read access) using
their one-click procedure.

Package folder structure Copy Section

This folder corresponds to the user-facing Julia packages. The goal is to have
it exported to the ortools/julia folder in the
GitHub repository, but it is not yet done.

A Julia package is made up of many files, here is a short description of the
ones in each package folder:

• Project.toml: description of the project and its dependencies. Update it
  when there is a new version.
  Official documentation.
• Manifest.toml: never commit this file.
  Official documentation.
• scripts: only in ORToolsGenerated.jl. Julia source code for code
  generation (Protocol Buffers and C API).
• src: Julia source code for the package. ORToolsGenerated.jl has the
  following subfolders:
  • src/genproto: generated Julia source code for the Protocol Buffers
    interface.
  • src/genc: generated Julia source code for the C API.
• test: automated test suite.

The ORToolsGenerated.jl and ORTools.jl packages do not include any binary
dependency; they are handled through ORTools_jll.

How to sync to Google3 changes? Copy Section

To update the underlying OR-Tools binary, look at
ORTools_jll
and the script
build_tarballs.jl
that build OR-Tools for Julia.

If there is an update in the C API, use scripts/TODO(user) to update the
generated code to call the C functions.

If there is an update in the MathOpt proto interface, use
ORToolsGenerated.jl/scripts/gen_pb.jl
to update the generated Protocol Buffers code. This script is automatically
called by
update_package.jl.

Design decisions Copy Chapter

Storing generated code Copy Section

The Julia package manager has
a build step
for all packages. However, this step is only called when first installing the
package or manually. Generating the code at the build step definitely possible,
but the generated code would not be up-to-date with the installed release of
OR-Tools, which defeats the purpose of having automatically generated code.

All other Julia packages that rely on generated code in the JuMP ecosystem rely
on stored generated code, at times storing several versions of the generated
code to accommodate various versions of the native dependency.

The package ORToolsGenerated.jl is supposed to correspond to exactly one
version of the native dependency.

Role of `update_package.jl` Copy Section

Bumping the version of ORToolsGenerated.jl requires two things:

• Updating the version of the package
  (following the usual rules for new releases of Julia packages,
  which means avoiding skipping versions).
• Updating the compatibility with ORTools_jll.

update_package.jl automates those two steps based on the version of
ORTools_jll.

Bazel Docs Ci (`bazel/docs/ci.md`) Copy Section

CI: Makefile/Docker testing

To test the build on various distro, I'm using docker containers and a Makefile
for orchestration.

pros:

• You are independent of third party CI runner VM images (e.g. github actions/virtual-environments).
• You can run it locally on any host having a linux docker image support.
• Most CI provide runner with docker and Makefile installed.

cons:

• Only GNU/Linux distro supported.
• Could take few GiB (~30 GiB for all distro and all languages)
  • ~500MiB OS + C++/CMake tools,

Usage Copy Chapter

To get the help simply type:

make

note: you can also use from top directory

make --directory=bazel

Example Copy Section

For example to test inside an Ubuntu container:

make ubuntu_test

Docker Layers Copy Chapter

Dockerfile is split in several stages.

Cmake Docs Ci (`cmake/docs/ci.md`) Copy Section

CI: Makefile/Docker/Vagrant testing

To test the build on various distro, I'm using docker containers and a Makefile
for orchestration.

pros:

• You are independent of third party CI runner VM images (e.g. github actions/virtual-environments).
• You can run it locally on any host having a linux docker image support.
• Most CI provide runner with docker and Makefile installed.

cons:

• Only GNU/Linux distro supported.
• Could take few GiB (~30 GiB for all distro and all languages)
  • ~500MiB OS + C++/CMake tools,
  • ~150 MiB Python,
  • ~400 MiB dotnet-sdk,
  • ~400 MiB java-jdk.

Usage Copy Chapter

To get the help simply type:

make

note: you can also use from top directory

make --directory=cmake

Example Copy Section

For example to test Python inside an Alpine container:

make alpine_python_test

Docker Copy Chapter

Docker is a set of platform
as a service products that use OS-level virtualization to deliver software in
packages called containers.

You can find official base image on the Docker registry Docker Hub

Layers Copy Section

Dockerfile is split in several stages.

Vagrant Copy Chapter

Vagrant is a tool for building and managing
virtual machine environments in a single workflow. It is currently used to test
FreeBSD inside a VirtualBox since we don't have any FreeBSD machine.
Vagrant call a base image a box.
Vagrant call a container a vagrant machine.

You can find official box on the Vagrant registry Vagrant Cloud

note: Currently only github MacOS runner provide virtualization support (i.e. VirtualBox).

Basic usage Copy Section

Once vagrant and VirtualBox are installed, all commands must be run where
the Vagrantfile is located.

Generate a Vagrantfile skeleton, e.g. using the box generic/freebsd12:

vagrant init generic/freebsd12

Build and run a new vagrant machine:

vagrant up

note: If you run virtualbox you should see it.

Connect to a vagrant machine:

vagrant ssh
[vagrant@freebsd12 ~]$ ...

Execute few commands:

vagrant ssh -c "pwd; ls project ..."

Stop and delete a vagrant machine:

vagrant destroy -f

Cmake Docs Cpp (`cmake/docs/cpp.md`) Copy Section

Linux	macOS	Windows

Introduction

For building OR-Tools as a CMake standalone project, you can read the following
instructions.

This project should run on GNU/Linux, MacOS and Windows.

C++ Project Build Copy Chapter

1. Get the source code and change to it.

   sh Copy

   git clone https://github.com/google/or-tools.git
   cd or-tools

2. Run CMake to configure the build tree.

   sh Copy

   cmake -S. -Bbuild -DCMAKE_BUILD_TYPE=Release -DBUILD_DEPS=ON

   note: To get the list of available generators (e.g. Visual Studio), use -G

3. Afterwards, generated files can be used to compile the project.

   sh Copy

   cmake --build build --config Release -v

4. Test the build software (optional).

   sh Copy

   cmake --build build --target test

5. Install the built files (optional).

   sh Copy

   cmake --build build --target install

Testing Copy Chapter

To list tests:

cd build
ctest -N

To only run C++ tests:

cd build
ctest -R "cxx_.*"

Technical Notes Copy Chapter

Managing RPATH Copy Section

Since we want to use the
CMAKE_BINARY_DIR
to generate the wrapper package (e.g. python wheel package) as well as be able
to test from the build directory.
We need to enable:

set(CMAKE_BUILD_WITH_INSTALL_RPATH TRUE)

And have a finely tailored rpath for each library.

Cmake Docs Dotnet (`cmake/docs/dotnet.md`) Copy Section

Linux	macOS	Windows

Introduction

Try to build a .NetStandard2.0 native (for win-x64, linux-x64 and osx-x64) nuget
multi package using dotnet/cli and the new
.csproj format.

Build the Binary Packages Copy Chapter

To build the .Net nuget packages, simply run:

cmake -S. -Bbuild -DBUILD_DOTNET=ON
cmake --build build --target dotnet_package -v

note: Since dotnet_package is in target all, you can also omit the
--target option.

Testing Copy Chapter

To list tests:

cd build
ctest -N

To only run .NET tests:

cd build
ctest -R "dotnet_.*"

Technical Notes Copy Chapter

First you should take a look at the
ortools/dotnet/README.md to understand the
layout.
Here I will only focus on the CMake/SWIG tips and tricks.

Build directory layout Copy Section

Since .Net use a .csproj project file to orchestrate everything we need to
generate them and have the following layout:

<CMAKE_BINARY_DIR>/dotnet
── Directory.Build.props
├── orLogo.png
├── ortools
│   ├── algorithms
│   │   ├── *.cs
│   │   ├── knapsack_solverCSHARP_wrap.cxx
│   │   ├── operations_research_algorithms.cs
│   │   └── operations_research_algorithmsPINVOKE.cs
│   ├── constraint_solver
│   │   ├── *.cs
│   │   ├── operations_research_constraint_solver.cs
│   │   ├── operations_research_constraint_solverPINVOKE.cs
│   │   ├── routingCSHARP_wrap.cxx
│   │   └── routingCSHARP_wrap.h
│   ├── graph
│   │   ├── *.cs
│   │   ├── graphCSHARP_wrap.cxx
│   │   ├── operations_research_graph.cs
│   │   └── operations_research_graphPINVOKE.cs
│   ├── linear_solver
│   │   ├── *.cs
│   │   ├── LinearSolver.pb.cs
│   │   ├── operations_research_linear_solver.cs
│   │   └── operations_research_linear_solverPINVOKE.cs
│   ├── sat
│   │   ├── *.cs
│   │   ├── BooleanProblem.pb.cs
│   │   ├── CpModel.pb.cs
│   │   ├── SatParameters.pb.cs
│   │   ├── operations_research_sat.cs
│   │   ├── operations_research_satPINVOKE.cs
│   │   ├── satCSHARP_wrap.cxx
│   │   └── satCSHARP_wrap.h
│   └── util
│       ├── *.cs
│       ├── operations_research_utilPINVOKE.cs
│       ├── sorted_interval_listCSHARP_wrap.cxx
│       └── sorted_interval_listCSHARP_wrap.h
├── Google.OrTools.runtime.linux-x64
│   └── Google.OrTools.runtime.linux-x64.csproj
├── Google.OrTools
│   └── Google.OrTools.csproj
├── replace.cmake
└── replace_runtime.cmake

src: tree build/dotnet --prune -I "obj|bin"

Cmake Docs Java (`cmake/docs/java.md`) Copy Section

Linux	macOS	Windows

Introduction

First, verify you have the JAVA_HOME environment variable set otherwise CMake
and Maven won't be able to find your Java SDK.

Build the Binary Package Copy Chapter

To build the java maven packages, simply run:

cmake -S. -Bbuild -DBUILD_JAVA=ON
cmake --build build --target java_package -v

note: Since java_package is in target all, you can also omit the
--target option.

Testing Copy Chapter

To list tests:

cd build
ctest -N

To only run Java tests:

cd build
ctest -R "java_.*"

Technical Notes Copy Chapter

First you should take a look at the
ortools/java/README.md to understand the layout.

Here I will only focus on the CMake/SWIG tips and tricks.

Build directory layout Copy Section

Since Java use the directory layout and we want to use the
CMAKE_BINARY_DIR
to generate the Java binary package.

We want this layout:

<CMAKE_BINARY_DIR>/java
├── ortools-linux-x86-64
│   ├── pom.xml
│   └── src/main/resources
│       └── linux-x86-64
│           ├── libjniortools.so
│           └── libortools.so
├── ortools-java
│   ├── pom.xml
│   └── src/main/java
│       └── com/google/ortools
│           ├── Loader.java
│           ├── linearsolver
│           │   ├── LinearSolver.java
│           │   └── ...
│           ├── constraintsolver
│           │   ├── ConstraintSolver.java
│           │   └── ...
│           ├── ...
│           └── sat
│               ├── CpModel.java
│               └── ...
├── constraint_solver
│   └── Tsp
│       ├── pom.xml
│       └── src/main/java
│           └── com/google/ortools
│               └── Tsp.java

src: tree build/java --prune -U -P "*.java|*.xml|*.so*" -I "target"

Managing SWIG generated files Copy Section

You can use CMAKE_SWIG_DIR to change the output directory for the .java file
e.g.:

set(CMAKE_SWIG_OUTDIR ${CMAKE_CURRENT_BINARY_DIR}/..)

And you can use CMAKE_LIBRARY_OUTPUT_DIRECTORY to change the output directory
for the .so file e.g.:

set(CMAKE_LIBRARY_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/..)

[optional]You can use SWIG_OUTFILE_DIR to change the output directory for the
.cxx file e.g.:

set(SWIG_OUTFILE_DIR ${CMAKE_CURRENT_BINARY_DIR}/..)

Then you only need to create a pom.xml file in build/java to be able to use
the build directory to generate the Java package.

Cmake Docs Python (`cmake/docs/python.md`) Copy Section

Linux	macOS	Windows

Introduction

To be compliant with
PEP513 a
python package should embbed all its C++ shared libraries.

Creating a Python native package containing all .py and .so (with good
rpath/loaderpath) is not so easy...

Build the Binary Package Copy Chapter

To build the Python wheel package, simply run:

cmake -S. -Bbuild -DBUILD_PYTHON=ON
cmake --build build --target python_package -v

note: Since python_package is in target all, you can also omit the
--target option.

Testing Copy Chapter

To list tests:

cd build
ctest -N

To only run Python tests:

cd build
ctest -R "python_.*"

Technical Notes Copy Chapter

First you should take a look at the
ortools/python/README.md to understand the
layout.
Here I will only focus on the CMake/SWIG tips and tricks.

Build directory layout Copy Section

Since Python use the directory name where __init__.py file is located and we
want to use the
CMAKE_BINARY_DIR
to generate the Python binary package.

We want this layout:

<CMAKE_BINARY_DIR>/python
├── setup.py
└── ortools
    ├── __init__.py
    ├── algorithms
    │   ├── __init__.py
    │   ├── _pywrap.so
    │   └── pywrap.py
    ├── graph
    │   ├── __init__.py
    │   ├── pywrapgraph.py
    │   └── _pywrapgraph.so
    ├── ...
    └── .libs
        ├── libXXX.so.1.0
        └── libXXX.so.1.0

src: tree build --prune -U -P "*.py|*.so*" -I "build"

note: On UNIX you always need $ORIGIN/../../${PROJECT_NAME}/.libs since
_pywrapXXX.so will depend on libortools.so.
note: On APPLE you always need
"@loader_path;@loader_path/../../${PROJECT_NAME}/.libs since _pywrapXXX.so
will depend on libortools.dylib.
note: on Windows since we are using static libraries we won't have the .libs
directory...

So we also need to create few __init__.py files to be able to use the build
directory to generate the Python package.

Why on APPLE lib must be .so Copy Section

Actually, the cpython code responsible for loading native libraries expect .so
on all UNIX platforms.

const char *_PyImport_DynLoadFiletab[] = {
#ifdef __CYGWIN__
    ".dll",
#else  /* !__CYGWIN__ */
    "." SOABI ".so",
#ifdef ALT_SOABI
    "." ALT_SOABI ".so",
#endif
    ".abi" PYTHON_ABI_STRING ".so",
    ".so",
#endif  /* __CYGWIN__ */
    NULL,
};

ref:
https://github.com/python/cpython/blob/main/Python/dynload_shlib.c#L37-L49

i.e. pywrapXXX -> _pywrapXXX.so -> libortools.dylib

Why setup.py has to be generated Copy Section

To avoid to put hardcoded path to SWIG .so/.dylib generated files, we could
use $<TARGET_FILE_NAME:tgt> to retrieve the file (and also deal with
Mac/Windows suffix, and target dependencies).
In order for setup.py to use
cmake generator expression
(e.g. $<TARGET_FILE_NAME:_pyFoo>). We need to generate it at build time (e.g.
using
add_custom_command()).

note: This will also add automatically a dependency between the command and the
TARGET !

todo(mizux): try to use
file(GENERATE ...)
instead.

Cmake Docs Swig (`cmake/docs/swig.md`) Copy Section

SWIG Wrapper Generation

Using swig to generate wrapper it's easy thanks
to the modern UseSWIG
module (CMake >= 3.14).

note: SWIG automatically put its target(s) in all, thus cmake --build build
will also call swig and generate _module.so.

Policy Copy Chapter

UseSWIG is impacted by two policies:

• CMP0078:UseSWIG
  generates standard target names (CMake 3.13+).
• CMP0086: UseSWIG
  honors SWIG_MODULE_NAME via -module flag (CMake 3.14+).

That's why I recommnend to use CMake >= 3.14 with both policies set to new for
SWIG development.

int64_t Management Copy Chapter

When working on a k8 (aka x86_64) architecture, you may face issue with
int64_t and uint64_t management.

First long long and long int are different types and int64_t is just a
typedef on one of them...

Linux Copy Section

On Linux we have:

sizeof(long long): 8
sizeof(long int): 8
sizeof(int64_t): 8

Gcc

First try to find where and how the compiler define int64_t and uint64_t.

grepc -rn "typedef.*int64_t;" /lib/gcc
/lib/gcc/x86_64-linux-gnu/9/include/stdint-gcc.h:43:typedef __INT64_TYPE__ int64_t;
/lib/gcc/x86_64-linux-gnu/9/include/stdint-gcc.h:55:typedef __UINT64_TYPE__ uint64_t;

So we need to find this compiler macro definition

gcc -dM -E -x c /dev/null | grep __INT64
#define __INT64_C(c) c ## L
#define __INT64_MAX__ 0x7fffffffffffffffL
#define __INT64_TYPE__ long int

gcc -dM -E -x c /dev/null | grep __UINT64
#define __UINT64_C(c) c ## UL
#define __UINT64_MAX__ 0xffffffffffffffffUL
#define __UINT64_TYPE__ long unsigned int

Clang

clang -dM -E -x c++ /dev/null | grep INT64_TYPE
#define __INT64_TYPE__ long int
#define __UINT64_TYPE__ long unsigned int

Clang, GNU compilers:
-dM dumps a list of macros.
-E prints results to stdout instead of a file.
-x c and -x c++ select the programming language when using a file without a
filename extension, such as /dev/null

Ref:
https://web.archive.org/web/20190803041507/http://nadeausoftware.com/articles/2011/12/c_c_tip_how_list_compiler_predefined_macros

MacOS Copy Section

On Catalina 10.15 we have:

sizeof(long long): 8
sizeof(long int): 8
sizeof(int64_t): 8

Clang

clang -dM -E -x c++ /dev/null | grep INT64_TYPE
#define __INT64_TYPE__ long long int
#define __UINT64_TYPE__ long long unsigned int

with: -dM dumps a list of macros.
-E prints results to stdout instead of a file.
-x c and -x c++ select the programming language when using a file without a
filename extension, such as /dev/null

Ref:
https://web.archive.org/web/20190803041507/http://nadeausoftware.com/articles/2011/12/c_c_tip_how_list_compiler_predefined_macros

Windows Copy Section

Contrary to macOS and Linux, Windows 64bits (x86_64) try hard to keep
compatibility, so we have:

sizeof(long int): 4
sizeof(long long): 8
sizeof(int64_t): 8

Visual Studio 2022

Thus, in stdint.h we have:

#if _VCRT_COMPILER_PREPROCESSOR

typedef signed char        int8_t;
typedef short              int16_t;
typedef int                int32_t;
typedef long long          int64_t;
typedef unsigned char      uint8_t;
typedef unsigned short     uint16_t;
typedef unsigned int       uint32_t;
typedef unsigned long long uint64_t;

SWIG int64_t management stuff Copy Section

First, take a look at
Swig stdint.i.
So, when targeting Linux you must use define SWIGWORDSIZE64 (i.e.
-DSWIGWORDSIZE64) while on macOS and Windows you must not define it.

Now the bad news, even if you can control the SWIG typedef using
SWIGWORDSIZE64,
SWIG Java
and
SWIG CSHARP
do not take it into account for typemaps...

So you may want to use this for Java:

#if defined(SWIGJAVA)
#if defined(SWIGWORDSIZE64)
%define PRIMITIVE_TYPEMAP(NEW_TYPE, TYPE)
%clear NEW_TYPE;
%clear NEW_TYPE *;
%clear NEW_TYPE &;
%clear const NEW_TYPE &;
%apply TYPE { NEW_TYPE };
%apply TYPE * { NEW_TYPE * };
%apply TYPE & { NEW_TYPE & };
%apply const TYPE & { const NEW_TYPE & };
%enddef // PRIMITIVE_TYPEMAP
PRIMITIVE_TYPEMAP(long int, long long);
PRIMITIVE_TYPEMAP(unsigned long int, long long);
#undef PRIMITIVE_TYPEMAP
#endif // defined(SWIGWORDSIZE64)
#endif // defined(SWIGJAVA)

and this for .Net:

#if defined(SWIGCSHARP)
#if defined(SWIGWORDSIZE64)
%define PRIMITIVE_TYPEMAP(NEW_TYPE, TYPE)
%clear NEW_TYPE;
%clear NEW_TYPE *;
%clear NEW_TYPE &;
%clear const NEW_TYPE &;
%apply TYPE { NEW_TYPE };
%apply TYPE * { NEW_TYPE * };
%apply TYPE & { NEW_TYPE & };
%apply const TYPE & { const NEW_TYPE & };
%enddef // PRIMITIVE_TYPEMAP
PRIMITIVE_TYPEMAP(long int, long long);
PRIMITIVE_TYPEMAP(unsigned long int, unsigned long long);
#undef PRIMITIVE_TYPEMAP
#endif // defined(SWIGWORDSIZE64)
#endif // defined(SWIGCSHARP)

So int64_t (i.e. long int in this case) will be correctly bind to Java/.Net
primitive type long.

swig_add_library() Copy Chapter

You can use OUTPUT_DIR to change the output directory for the .py file e.g.:

swig_add_library(pyFoo
  TYPE MODULE
  LANGUAGE python
  OUTPUT_DIR ${CMAKE_BINARY_DIR}/python/${PROJECT_NAME}/Foo
  SOURCES foo.i)

Doxygen Copy Chapter

Since swig 4.0, swig can now
extract doxygen comments from C++ to
inject it in Python and Java.

Csharp documentation Copy Section

note: Doxygen to csharp was
planned
but currently is not supported.

Makefiles Docs Ci (`makefiles/docs/ci.md`) Copy Section

CI: Makefile/Docker testing

To test the build on various distro, I'm using docker containers and a Makefile
for orchestration.

pros:

• You are independent of third party CI runner config (e.g. github actions
  runners or Travis-CI VM images).
• You can run it locally on your linux system.
• Most CI provide runner with docker and Makefile installed (e.g. tarvis-ci
  minimal images.

cons:

• Only GNU/Linux distro supported.
• Could take few GiB (~30 GiB for all distro and all languages)
  • ~500MiB OS + C++/CMake tools,
  • ~150 MiB Python,
  • ~400 MiB dotnet-sdk,
  • ~400 MiB java-jdk.

Usage Copy Chapter

To get the help simply type:

make

note: you can also use from top directory

make --directory=makefiles

Example Copy Section

For example to test Python inside an Alpine container:

make alpine_python_test

Docker layers Copy Chapter

Dockerfile is split in several stages.

Ortools Constraint Solver Docs CP (`ortools/constraint_solver/docs/CP.md`) Copy Section

Using the CP solver

https://developers.google.com/optimization/cp/

Documentation structure Copy Chapter

OR-Tools comes with lots of constraint programming samples given in C++, Python,
Java and .Net. Each language have different requirements for the code samples.

Basic example Copy Chapter

C++ code samples Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Python code samples Copy Section

#!/usr/bin/env python3
"""Simple Constraint optimization example."""

from ortools.constraint_solver import pywrapcp


def main():
    """Entry point of the program."""
    # Instantiate the solver.
    solver = pywrapcp.Solver("CPSimple")

    # Create the variables.
    num_vals = 3
    x = solver.IntVar(0, num_vals - 1, "x")
    y = solver.IntVar(0, num_vals - 1, "y")
    z = solver.IntVar(0, num_vals - 1, "z")

    # Constraint 0: x != y.
    solver.Add(x != y)
    print("Number of constraints: ", solver.Constraints())

    # Solve the problem.
    decision_builder = solver.Phase(
        [x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE
    )

    # Print solution on console.
    count = 0
    solver.NewSearch(decision_builder)
    while solver.NextSolution():
        count += 1
        solution = f"Solution {count}:\n"
        for var in [x, y, z]:
            solution += f" {var.Name()} = {var.Value()}"
        print(solution)
    solver.EndSearch()
    print(f"Number of solutions found: {count}")

    print("Advanced usage:")
    print(f"Problem solved in {solver.WallTime()}ms")
    print(f"Memory usage: {pywrapcp.Solver.MemoryUsage()}bytes")


if __name__ == "__main__":
    main()

Java code samples Copy Section

/* Detailed source-code truncated for AI context efficiency. */

.Net code samples Copy Section

using System;
using Google.OrTools.ConstraintSolver;

/// <summary>
///   This is a simple CP program.
/// </summary>
public class SimpleCpProgram
{
    public static void Main(String[] args)
    {
        // Instantiate the solver.
        Solver solver = new Solver("CpSimple");

        // Create the variables.
        const long numVals = 3;
        IntVar x = solver.MakeIntVar(0, numVals - 1, "x");
        IntVar y = solver.MakeIntVar(0, numVals - 1, "y");
        IntVar z = solver.MakeIntVar(0, numVals - 1, "z");

        // Constraint 0: x != y..
        solver.Add(solver.MakeAllDifferent(new IntVar[] { x, y }));
        Console.WriteLine($"Number of constraints: {solver.Constraints()}");

        // Solve the problem.
        DecisionBuilder db =
            solver.MakePhase(new IntVar[] { x, y, z }, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

        // Print solution on console.
        int count = 0;
        solver.NewSearch(db);
        while (solver.NextSolution())
        {
            ++count;
            Console.WriteLine($"Solution: {count}\n x={x.Value()} y={y.Value()} z={z.Value()}");
        }
        solver.EndSearch();
        Console.WriteLine($"Number of solutions found: {solver.Solutions()}");

        Console.WriteLine("Advanced usage:");
        Console.WriteLine($"Problem solved in {solver.WallTime()}ms");
        Console.WriteLine($"Memory usage: {Solver.MemoryUsage()}bytes");
    }
}

Ortools Constraint Solver Docs PDP (`ortools/constraint_solver/docs/PDP.md`) Copy Section

Pickup & Delivery routing Problem recipes for the Vehicle Routing solver.

Introduction Copy Chapter

The Vehicle Routing solver can be used to solve various PDP.

Pickup & Delivery Problem Copy Chapter

Data Problem:

Solution with the default Policy (ANY):

Samples:

• vrp_pickup_delivery.cc
• vrp_pickup_delivery.py
• VrpPickupDelivery.java
• VrpPickupDelivery.cs

FIFO Policy Copy Section

Solution with the FIFO Policy:

Samples:

• vrp_pickup_delivery_fifo.cc
• vrp_pickup_delivery_fifo.py
• VrpPickupDeliveryFifo.java
• VrpPickupDeliveryFifo.cs

LIFO Policy Copy Section

Solution with the LIFO Policy:

Samples:

• vrp_pickup_delivery_lifo.cc
• vrp_pickup_delivery_lifo.py
• VrpPickupDeliveryLifo.java
• VrpPickupDeliveryLifo.cs

Ortools Constraint Solver Docs ROUTING (`ortools/constraint_solver/docs/ROUTING.md`) Copy Section

Using the Vehicle Routing solver

https://developers.google.com/optimization/routing

Documentation structure Copy Chapter

This document presents modeling recipes for the Vehicle routing solver. These
are grouped by type:

• Travelling Salesman Problem
• Vehicle Routing Problem
• Pickup and Delivery Problem

OR-Tools comes with lots of vehicle routing samples given in C++, Python, Java
and .Net. Each language have different requirements for the code samples.

Basic example Copy Chapter

C++ code samples Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Python code samples Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Java code samples Copy Section

/* Detailed source-code truncated for AI context efficiency. */

.Net code samples Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Misc Copy Chapter

Images have been generated using routing_svg.py through bash
script generate_svg.sh.

Ortools Constraint Solver Docs TSP (`ortools/constraint_solver/docs/TSP.md`) Copy Section

Travelling Salesman Problem recipes for the Vehicle Routing solver.

Introduction Copy Chapter

The Vehicle Routing solver can be used to solve a Travelling Salesman Problem
(TSP).

Using Locations Copy Chapter

Data Problem:

Solution:

Samples:

• tsp.cc
• tsp.py
• Tsp.java
• Tsp.cs

Using Distance Matrix Copy Chapter

Data Problem:

Solution:

Samples:

• tsp_distance_matrix.cc
• tsp_distance_matrix.py
• TspDistanceMatrix.java
• TspDistanceMatrix.cs

Ortools Constraint Solver Docs VRP (`ortools/constraint_solver/docs/VRP.md`) Copy Section

Vehicle Routing Problem recipes for the Vehicle Routing solver.

Introduction Copy Chapter

The Vehicle Routing solver can be used to solve various VRP.

Vehicle Routing Problem Copy Chapter

Data Problem:

Solution:

Samples:

• vrp.cc
• vrp.py
• Vrp.java
• Vrp.cs

Global Span Constraints Copy Chapter

Data Problem:

Solution:

Samples:

• vrp_global_span.cc
• vrp_global_span.py
• VrpGlobalSpan.java
• VrpGlobalSpan.cs

Capacity Constraints Copy Chapter

Data Problem:

Solution:

Samples:

• vrp_capacity.cc
• vrp_capacity.py
• VrpCapacity.java
• VrpCapacity.cs

Drop Nodes Constraints Copy Chapter

Data Problem:

Solution:

Samples:

• vrp_drop_nodes.cc
• vrp_drop_nodes.py
• VrpDropNodes.java
• VrpDropNodes.cs

Multiple Starts Ends Copy Chapter

Data Problem:

Solution:

Samples:

• vrp_starts_ends.cc
• vrp_starts_ends.py
• VrpStartsEnds.java
• VrpStartsEnds.cs

Time Window Constraints Copy Chapter

Data Problem:

Solution:

Samples:

• vrp_time_windows.cc
• vrp_time_windows.py
• VrpTimeWindows.java
• VrpTimeWindows.cs

Resource Constraints Copy Chapter

Data Problem:

Solution:

Samples:

• vrp_resources.cc
• vrp_resources.py
• VrpResources.java
• VrpResources.cs

Ortools Sat Docs Boolean Logic (`ortools/sat/docs/boolean_logic.md`) Copy Section

Boolean logic recipes for the CP-SAT solver.

https://developers.google.com/optimization/

Introduction Copy Chapter

The CP-SAT solver can express Boolean variables and constraints. A Boolean
variable is an integer variable constrained to be either 0 or 1. A literal
is either a Boolean variable or its negation: 0 negated is 1, and 1 negated is
0. See
https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Basic_definitions_and_terminology.

Boolean variables and literals Copy Chapter

We can create a Boolean variable x and a literal not_x equal to the logical
negation of x.

Python code Copy Section

# Snippet from ortools/sat/samples/literal_sample_sat.py
"""Code sample to demonstrate Boolean variable and literals."""


from ortools.sat.python import cp_model


def literal_sample_sat():
  model = cp_model.CpModel()
  x = model.new_bool_var('x')
  not_x = ~x
  print(x)
  print(not_x)


literal_sample_sat()

C++ code Copy Section

// Snippet from ortools/sat/samples/literal_sample_sat.cc
#include <stdlib.h>

#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "absl/base/log_severity.h"
#include "absl/log/globals.h"
#include "ortools/sat/cp_model.h"

namespace operations_research {
namespace sat {

void LiteralSampleSat() {
  CpModelBuilder cp_model;

  const BoolVar x = cp_model.NewBoolVar().WithName("x");
  const BoolVar not_x = ~x;
  LOG(INFO) << "x = " << x << ", not(x) = " << not_x;
}

}  // namespace sat
}  // namespace operations_research

int main(int argc, char* argv[]) {
  InitGoogle(argv[0], &argc, &argv, true);
  absl::SetStderrThreshold(absl::LogSeverityAtLeast::kInfo);
  operations_research::sat::LiteralSampleSat();
  return EXIT_SUCCESS;
}

Java code Copy Section

// Snippet from ortools/sat/samples/LiteralSampleSat.java
package com.google.ortools.sat.samples;

import com.google.ortools.sat.BoolVar;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.Literal;
import com.google.ortools.Loader;

/** Code sample to demonstrate Boolean variable and literals. */
public class LiteralSampleSat {
  public static void main(String[] args) throws Exception {
    Loader.loadNativeLibraries();
    CpModel model = new CpModel();
    BoolVar x = model.newBoolVar("x");
    Literal notX = x.not();
    System.out.println(notX);
  }
}

C\# code Copy Section

// Snippet from ortools/sat/samples/LiteralSampleSat.cs
using System;
using Google.OrTools.Sat;

public class LiteralSampleSat
{
    static void Main()
    {
        CpModel model = new CpModel();
        BoolVar x = model.NewBoolVar("x");
        ILiteral not_x = x.Not();
    }
}

Go code Copy Section

// Snippet from ortools/sat/samples/literal_sample_sat.go
// The literal_sample_sat command is a simple example of literals.
package main

import (
	log "github.com/golang/glog"
	"github.com/google/or-tools/ortools/sat/go/cpmodel"
)

func literalSampleSat() {
	model := cpmodel.NewCpModelBuilder()

	x := model.NewBoolVar().WithName("x")
	notX := x.Not()

	log.Infof("x = %d, x.Not() = %d", x.Index(), notX.Index())
}

func main() {
	literalSampleSat()
}

Boolean constraints Copy Chapter

For Boolean variables x and y, the following are elementary Boolean constraints:

• or(x_1, .., x_n)
• and(x_1, .., x_n)
• xor(x_1, .., x_n)
• not(x)

More complicated constraints can be built up by combining these elementary
constraints. For instance, we can add a constraint Or(x, not(y)).

Python code Copy Section

# Snippet from ortools/sat/samples/bool_or_sample_sat.py
"""Code sample to demonstrates a simple Boolean constraint."""


from ortools.sat.python import cp_model


def bool_or_sample_sat():
  model = cp_model.CpModel()

  x = model.new_bool_var('x')
  y = model.new_bool_var('y')

  model.add_bool_or([x, y.negated()])
  # The [] is not mandatory.
  # ~y is equivalent to y.negated()
  model.add_bool_or(x, ~y)


bool_or_sample_sat()

C++ code Copy Section

// Snippet from ortools/sat/samples/bool_or_sample_sat.cc
#include <stdlib.h>

#include "ortools/base/init_google.h"
#include "absl/base/log_severity.h"
#include "absl/log/globals.h"
#include "absl/types/span.h"
#include "ortools/sat/cp_model.h"

namespace operations_research {
namespace sat {

void BoolOrSampleSat() {
  CpModelBuilder cp_model;

  const BoolVar x = cp_model.NewBoolVar();
  const BoolVar y = cp_model.NewBoolVar();
  cp_model.AddBoolOr({x, ~y});
  // You can also use the ~ operator.
  cp_model.AddBoolOr({x, ~y});
}

}  // namespace sat
}  // namespace operations_research

int main(int argc, char* argv[]) {
  InitGoogle(argv[0], &argc, &argv, true);
  absl::SetStderrThreshold(absl::LogSeverityAtLeast::kInfo);
  operations_research::sat::BoolOrSampleSat();
  return EXIT_SUCCESS;
}

Java code Copy Section

// Snippet from ortools/sat/samples/BoolOrSampleSat.java
package com.google.ortools.sat.samples;

import com.google.ortools.Loader;
import com.google.ortools.sat.BoolVar;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.Literal;

/** Code sample to demonstrates a simple Boolean constraint. */
public class BoolOrSampleSat {
  public static void main(String[] args) throws Exception {
    Loader.loadNativeLibraries();
    CpModel model = new CpModel();
    BoolVar x = model.newBoolVar("x");
    BoolVar y = model.newBoolVar("y");
    model.addBoolOr(new Literal[] {x, y.not()});
  }
}

C\# code Copy Section

// Snippet from ortools/sat/samples/BoolOrSampleSat.cs
using System;
using Google.OrTools.Sat;

public class BoolOrSampleSat
{
    static void Main()
    {
        CpModel model = new CpModel();

        BoolVar x = model.NewBoolVar("x");
        BoolVar y = model.NewBoolVar("y");

        model.AddBoolOr(new ILiteral[] { x, y.Not() });
    }
}

Go code Copy Section

// Snippet from ortools/sat/samples/bool_or_sample_sat.go
// The bool_or_sample_sat command is simple example of the BoolOr constraint.
package main

import (
	"github.com/google/or-tools/ortools/sat/go/cpmodel"
)

func boolOrSampleSat() {
	model := cpmodel.NewCpModelBuilder()

	x := model.NewBoolVar()
	y := model.NewBoolVar()

	model.AddBoolOr(x, y.Not())
}

func main() {
	boolOrSampleSat()
}

Reified constraints Copy Chapter

The CP-SAT solver supports half-reified constraints, also called
implications, which are of the form:

x implies constraint

where the constraint must hold if x is true.

Note that this is not an equivalence relation. The constraint can still be true
if x is false.

So we can write b => And(x, not y). That is, if b is true, then x is true and y
is false. Note that in this particular example, there are multiple ways to
express this constraint: you can also write (b => x) and (b => not y), which
then is written as Or(not b, x) and Or(not b, not y).

Python code Copy Section

# Snippet from ortools/sat/samples/reified_sample_sat.py
"""Simple model with a reified constraint."""

from ortools.sat.python import cp_model


def reified_sample_sat():
  """Showcase creating a reified constraint."""
  model = cp_model.CpModel()

  x = model.new_bool_var('x')
  y = model.new_bool_var('y')
  b = model.new_bool_var('b')

  # First version using a half-reified bool and.
  model.add_bool_and(x, ~y).only_enforce_if(b)

  # Second version using implications.
  model.add_implication(b, x)
  model.add_implication(b, ~y)

  # Third version using bool or.
  model.add_bool_or(~b, x)
  model.add_bool_or(~b, ~y)


reified_sample_sat()

C++ code Copy Section

// Snippet from ortools/sat/samples/reified_sample_sat.cc
#include <stdlib.h>

#include "ortools/base/init_google.h"
#include "absl/base/log_severity.h"
#include "absl/log/globals.h"
#include "absl/types/span.h"
#include "ortools/sat/cp_model.h"

namespace operations_research {
namespace sat {

void ReifiedSampleSat() {
  CpModelBuilder cp_model;

  const BoolVar x = cp_model.NewBoolVar();
  const BoolVar y = cp_model.NewBoolVar();
  const BoolVar b = cp_model.NewBoolVar();

  // First version using a half-reified bool and.
  cp_model.AddBoolAnd({x, ~y}).OnlyEnforceIf(b);

  // Second version using implications.
  cp_model.AddImplication(b, x);
  cp_model.AddImplication(b, ~y);

  // Third version using bool or.
  cp_model.AddBoolOr({~b, x});
  cp_model.AddBoolOr({~b, ~y});
}

}  // namespace sat
}  // namespace operations_research

int main(int argc, char* argv[]) {
  InitGoogle(argv[0], &argc, &argv, true);
  absl::SetStderrThreshold(absl::LogSeverityAtLeast::kInfo);
  operations_research::sat::ReifiedSampleSat();
  return EXIT_SUCCESS;
}

Java code Copy Section

// Snippet from ortools/sat/samples/ReifiedSampleSat.java
package com.google.ortools.sat.samples;

import com.google.ortools.Loader;
import com.google.ortools.sat.BoolVar;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.Literal;

/**
 * Reification is the action of associating a Boolean variable to a constraint. This boolean
 * enforces or prohibits the constraint according to the value the Boolean variable is fixed to.
 *
 * <p>Half-reification is defined as a simple implication: If the Boolean variable is true, then the
 * constraint holds, instead of an complete equivalence.
 *
 * <p>The SAT solver offers half-reification. To implement full reification, two half-reified
 * constraints must be used.
 */
public class ReifiedSampleSat {
  public static void main(String[] args) throws Exception {
    Loader.loadNativeLibraries();
    CpModel model = new CpModel();

    BoolVar x = model.newBoolVar("x");
    BoolVar y = model.newBoolVar("y");
    BoolVar b = model.newBoolVar("b");

    // Version 1: a half-reified boolean and.
    model.addBoolAnd(new Literal[] {x, y.not()}).onlyEnforceIf(b);

    // Version 2: implications.
    model.addImplication(b, x);
    model.addImplication(b, y.not());

    // Version 3: boolean or.
    model.addBoolOr(new Literal[] {b.not(), x});
    model.addBoolOr(new Literal[] {b.not(), y.not()});
  }
}

C\# code Copy Section

// Snippet from ortools/sat/samples/ReifiedSampleSat.cs
using System;
using Google.OrTools.Sat;

public class ReifiedSampleSat
{
    static void Main()
    {
        CpModel model = new CpModel();

        BoolVar x = model.NewBoolVar("x");
        BoolVar y = model.NewBoolVar("y");
        BoolVar b = model.NewBoolVar("b");

        //  First version using a half-reified bool and.
        model.AddBoolAnd(new ILiteral[] { x, y.Not() }).OnlyEnforceIf(b);

        // Second version using implications.
        model.AddImplication(b, x);
        model.AddImplication(b, y.Not());

        // Third version using bool or.
        model.AddBoolOr(new ILiteral[] { b.Not(), x });
        model.AddBoolOr(new ILiteral[] { b.Not(), y.Not() });
    }
}

Go code Copy Section

// Snippet from ortools/sat/samples/reified_sample_sat.go
// The reified_sample_sat command is a simple example of implication constraints.
package main

import (
	"github.com/google/or-tools/ortools/sat/go/cpmodel"
)

func reifiedSampleSat() {
	model := cpmodel.NewCpModelBuilder()

	x := model.NewBoolVar()
	y := model.NewBoolVar()
	b := model.NewBoolVar()

	// First version using a half-reified bool and.
	model.AddBoolAnd(x, y.Not()).OnlyEnforceIf(b)

	// Second version using implications.
	model.AddImplication(b, x)
	model.AddImplication(b, y.Not())

	// Third version using bool or.
	model.AddBoolOr(b.Not(), x)
	model.AddBoolOr(b.Not(), y.Not())
}

func main() {
	reifiedSampleSat()
}

Product of two Boolean Variables Copy Chapter

A useful construct is the product p of two Boolean variables x and y.

p == x * y

This is equivalent to the logical relation

p <=> x and y

This is encoded using one bool_or constraint and two implications. The following
code samples output this truth table:

x = 0   y = 0   p = 0
x = 1   y = 0   p = 0
x = 0   y = 1   p = 0
x = 1   y = 1   p = 1

Python code Copy Section

# Snippet from ortools/sat/samples/boolean_product_sample_sat.py
"""Code sample that encodes the product of two Boolean variables."""


from ortools.sat.python import cp_model


def boolean_product_sample_sat():
  """Encoding of the product of two Boolean variables.

  p == x * y, which is the same as p <=> x and y
  """
  model = cp_model.CpModel()
  x = model.new_bool_var('x')
  y = model.new_bool_var('y')
  p = model.new_bool_var('p')

  # x and y implies p, rewrite as not(x and y) or p.
  model.add_bool_or(~x, ~y, p)

  # p implies x and y, expanded into two implications.
  model.add_implication(p, x)
  model.add_implication(p, y)

  # Create a solver and solve.
  solver = cp_model.CpSolver()
  solution_printer = cp_model.VarArraySolutionPrinter([x, y, p])
  solver.parameters.enumerate_all_solutions = True
  solver.solve(model, solution_printer)


boolean_product_sample_sat()

Go code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Ortools Sat Docs Channeling (`ortools/sat/docs/channeling.md`) Copy Section

Channeling constraints

https://developers.google.com/optimization/

A channeling constraint links variables inside a model. They're used when you
want to express a complicated relationship between variables, such as "if this
variable satisfies a condition, force another variable to a particular value".

Channeling is usually implemented using half-reified linear constraints: one
constraint implies another (a → b), but not necessarily the other way
around (a ← b).

If-Then-Else expressions Copy Chapter

Let's say you want to implement the following: "If x is less than 5, set y
to 0. Otherwise, set y to 10-x". You can do this creating an intermediate
boolean variable b that is true if x is greater than or equal to 5, and
false otherwise:

b implies y == 10 - x

not(b) implies y == 0

These are implemented using the OnlyEnforceIf method as shown below.

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C++ code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Java code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C\# code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Go code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

This displays the following:

x=0 y=0 b=0
x=1 y=0 b=0
x=2 y=0 b=0
x=3 y=0 b=0
x=4 y=0 b=0
x=5 y=5 b=1
x=6 y=4 b=1
x=7 y=3 b=1
x=8 y=2 b=1
x=9 y=1 b=1
x=10 y=0 b=1

Computing the index of the first Boolean variable set to true Copy Chapter

A common request is to compute the index of the first Boolean variable set to
true. It can be encoded using a min_equality constraint. The index will be set
to the number of Boolean variables if they are all false.

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

This displays the following:

00000 -> 5
00001 -> 4
00010 -> 3
00011 -> 3
00100 -> 2
00101 -> 2
00110 -> 2
00111 -> 2
01000 -> 1
01001 -> 1
01010 -> 1
01011 -> 1
01100 -> 1
01101 -> 1
01110 -> 1
01111 -> 1
10000 -> 0
10001 -> 0
10010 -> 0
10011 -> 0
10100 -> 0
10101 -> 0
10110 -> 0
10111 -> 0
11000 -> 0
11001 -> 0
11010 -> 0
11011 -> 0
11100 -> 0
11101 -> 0
11110 -> 0
11111 -> 0

A bin-packing problem Copy Chapter

As another example of a channeling constraint, consider a bin packing problem in
which one part of the model computes the load of each bin, while another
maximizes the number of bins under a given threshold. To implement this, you can
channel the load of each bin into a set of boolean variables, each indicating
whether it's under the threshold.

To make this more concrete, let's say you have 10 bins of capacity 100, and
items to pack into the bins. You would like to maximize the number of bins that
can accept one emergency load of size 20.

To do this, you need to maximize the number of bins that have a load less than
80. In the code below, channeling is used to link the load and slack
variables together:

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C++ code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Java code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C\# code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Go code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Ortools Sat Docs Integer Arithmetic (`ortools/sat/docs/integer_arithmetic.md`) Copy Section

Integer arithmetic recipes for the CP-SAT solver.

https://developers.google.com/optimization/

Introduction Copy Chapter

The CP-SAT solver can express integer variables and constraints.

Integer variables Copy Chapter

Integer variables can take on 64-bit signed integer values. When creating them,
a domain must be provided.

Interval domain Copy Section

To create a single contiguous integer domain, just call the NewIntVar method
with the lower and upper bounds. For instance, to create a variable that can
take on any value between 0 and 10, inclusive:

• C++: IntVar x = model.NewIntVar({0, 10}).WithName("x");
• Python: x = model.NewIntVar(0, 10, 'x')
• Java: IntVar x = model.newIntVar(0, 10, "x");
• C#: IntVar x = model.NewIntVar(0, 10, "x");
• Go: x := model.NewIntVar(0, 10).WithName("x")

Non-contiguous domain Copy Section

An instance of the Domain class is needed to create variables with
non-contiguous domains. Here, the variable can be any of 1, 3, 4, or 6:

• C++: model.NewIntVar(Domain::FromValues({1, 3, 4, 6});
• Python: model.NewIntVarFromDomain(cp_model.Domain.FromValues([1, 3, 4, 6]), 'x')
• Java: model.newIntVarFromDomain(Domain.fromValues(new long[] {1, 3, 4, 6}), "x");
• C#: model.NewIntVarFromDomain(Domain.FromValues(new long[] {1, 3, 4, 6}), "x");
• Go: model.NewIntVarFromDomain(cpmodel.FromValues([]int64{1, 3, 4, 6})

Variables can also be created using a list of intervals. Below, the variable
created is constrained to be 1, 2, 4, 5, or 6:

• C++: model.NewIntVar(Domain::FromIntervals({{1, 2}, {4, 6}});
• Python: model.NewIntVarFromDomain(cp_model.Domain.FromIntervals([[1, 2], [4, 6]]), 'x')
• 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");
• Go: model.NewIntVarFromDomain(cpmodel.FromIntervals( []cpmodel.ClosedInterval{{1, 2}, {4, 6}}))

Boolean variables Copy Section

To create a Boolean variable, use the NewBoolVar method. Note that Boolean
variables are typed differently than integer variables, and that this type is
not uniform across languages.

• C++: BoolVar x = model.NewBoolVar().WithName("x");
• Python: x = model.NewBoolVar('x')
• Java: Literal x = model.newBoolVar("x");
• C#: ILiteral x = model.NewBoolVar("x");
• Go: x := model.NewBoolVar().WithName("x")

Other methods Copy Section

To exclude a single value, use ranges combined with int64min and int64max
values, e.g., [[int64min, -3], [-1, int64max]], or use the Complement
method.

To create a variable with a single value domain, use the NewConstant() API (or
newConstant() in Java).

Linear constraints Copy Chapter

C++, Java, and Go linear constraints and linear expressions Copy Section

C++, Java, and Go APIs do not use arithmetic operators (+, *, -,
<=...). Linear constraints are created using a method of the model factory, such
as cp_model.AddEquality(x, 3) in C++, cp_model.addGreaterOrEqual(x, 10) in
Java, or model.AddLessThan(x, cpmodel.NewConstant(5)) in Go.

Furthermore, helper methods can be used to create sums and scalar products like
LinearExpr::Sum({x, y, z}) in C++, LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {1, 2, 3}) in Java, and cpmodel.NewLinearExpr().AddSum(x, y, z) in Go.

Python and C\# linear constraints and linear expressions Copy Section

Python and C# CP-SAT APIs support general linear arithmetic (+, *, -,
==, >=, >, <, <=, !=). You need to use the Add method of the cp_model, as in
cp_model.Add(x + y != 3).

Generic linear constraint Copy Section

in all languages, the cp_model factory offers a generic method to constrain
a linear expression to be in a domain. This is used in the step function
examples below.

Limitations Copy Section

• Everything must be linear. Multiplying two variables is not supported with
  this API; instead, model.AddMultiplicationEquality() must be used.

• In C++, there is a typing issue when using an array of Boolean variables in
  a sum or a scalar product. Use the LinearExpr.BooleanSum() method instead.

• The Python construct sum() is supported, but min(), max() or any
  numpy constructs like np.unique() are not.

Rabbits and Pheasants examples Copy Chapter

Let's solve a simple children's puzzle: the Rabbits and Pheasants problem.

In a field of rabbits and pheasants, there are 20 heads and 56 legs. How many
rabbits and pheasants are there?

Python code Copy Section

# Snippet from ortools/sat/samples/rabbits_and_pheasants_sat.py
"""Rabbits and Pheasants quizz."""

from ortools.sat.python import cp_model


def rabbits_and_pheasants_sat():
  """Solves the rabbits + pheasants problem."""
  model = cp_model.CpModel()

  r = model.new_int_var(0, 100, 'r')
  p = model.new_int_var(0, 100, 'p')

  # 20 heads.
  model.add(r + p == 20)
  # 56 legs.
  model.add(4 * r + 2 * p == 56)

  # Solves and prints out the solution.
  solver = cp_model.CpSolver()
  status = solver.solve(model)

  if status == cp_model.OPTIMAL:
    print(f'{solver.value(r)} rabbits and {solver.value(p)} pheasants')


rabbits_and_pheasants_sat()

C++ code Copy Section

// Snippet from ortools/sat/samples/rabbits_and_pheasants_sat.cc
#include <stdlib.h>

#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "absl/base/log_severity.h"
#include "absl/log/globals.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"
#include "ortools/util/sorted_interval_list.h"

namespace operations_research {
namespace sat {

void RabbitsAndPheasantsSat() {
  CpModelBuilder cp_model;

  const Domain all_animals(0, 20);
  const IntVar rabbits = cp_model.NewIntVar(all_animals).WithName("rabbits");
  const IntVar pheasants =
      cp_model.NewIntVar(all_animals).WithName("pheasants");

  cp_model.AddEquality(rabbits + pheasants, 20);
  cp_model.AddEquality(4 * rabbits + 2 * pheasants, 56);

  const CpSolverResponse response = Solve(cp_model.Build());

  if (response.status() == CpSolverStatus::OPTIMAL) {
    // Get the value of x in the solution.
    LOG(INFO) << SolutionIntegerValue(response, rabbits) << " rabbits, and "
              << SolutionIntegerValue(response, pheasants) << " pheasants";
  }
}

}  // namespace sat
}  // namespace operations_research

int main(int argc, char* argv[]) {
  InitGoogle(argv[0], &argc, &argv, true);
  absl::SetStderrThreshold(absl::LogSeverityAtLeast::kInfo);
  operations_research::sat::RabbitsAndPheasantsSat();
  return EXIT_SUCCESS;
}

Java code Copy Section

// Snippet from ortools/sat/samples/RabbitsAndPheasantsSat.java
package com.google.ortools.sat.samples;

import com.google.ortools.Loader;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.LinearExpr;

/**
 * In a field of rabbits and pheasants, there are 20 heads and 56 legs. How many rabbits and
 * pheasants are there?
 */
public class RabbitsAndPheasantsSat {
  public static void main(String[] args) throws Exception {
    Loader.loadNativeLibraries();
    // Creates the model.
    CpModel model = new CpModel();
    // Creates the variables.
    IntVar r = model.newIntVar(0, 100, "r");
    IntVar p = model.newIntVar(0, 100, "p");
    // 20 heads.
    model.addEquality(LinearExpr.newBuilder().add(r).add(p), 20);
    // 56 legs.
    model.addEquality(LinearExpr.newBuilder().addTerm(r, 4).addTerm(p, 2), 56);

    // Creates a solver and solves the model.
    CpSolver solver = new CpSolver();
    CpSolverStatus status = solver.solve(model);

    if (status == CpSolverStatus.OPTIMAL) {
      System.out.println(solver.value(r) + " rabbits, and " + solver.value(p) + " pheasants");
    }
  }
}

C\# code Copy Section

// Snippet from ortools/sat/samples/RabbitsAndPheasantsSat.cs
using System;
using Google.OrTools.Sat;

public class RabbitsAndPheasantsSat
{
    static void Main()
    {
        // Creates the model.
        CpModel model = new CpModel();
        // Creates the variables.
        IntVar r = model.NewIntVar(0, 100, "r");
        IntVar p = model.NewIntVar(0, 100, "p");
        // 20 heads.
        model.Add(r + p == 20);
        // 56 legs.
        model.Add(4 * r + 2 * p == 56);

        // Creates a solver and solves the model.
        CpSolver solver = new CpSolver();
        CpSolverStatus status = solver.Solve(model);

        if (status == CpSolverStatus.Optimal)
        {
            Console.WriteLine(solver.Value(r) + " rabbits, and " + solver.Value(p) + " pheasants");
        }
    }
}

Go code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Earliness-Tardiness cost function. Copy Chapter

Let's encode a useful convex piecewise linear function that often appears in
scheduling. You want to encourage a delivery to happen during a time window. If
you deliver early, you pay a linear penalty on waiting time. If you deliver
late, you pay a linear penalty on the delay.

Because the function is convex, you can define all affine functions, and take
the max of them to define the piecewise linear function.

The following samples output:

x=0 expr=40
x=1 expr=32
x=2 expr=24
x=3 expr=16
x=4 expr=8
x=5 expr=0
x=6 expr=0
x=7 expr=0
x=8 expr=0
x=9 expr=0
x=10 expr=0
x=11 expr=0
x=12 expr=0
x=13 expr=0
x=14 expr=0
x=15 expr=0
x=16 expr=12
x=17 expr=24
x=18 expr=36
x=19 expr=48
x=20 expr=60

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C++ code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Java code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C\# code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Go code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Step function. Copy Chapter

Let's encode a step function. We will use one Boolean variable per step value,
and filter the admissible domain of the input variable with this variable.

The following samples output:

x=0 expr=2
x=1 expr=2
x=3 expr=2
x=4 expr=2
x=5 expr=0
x=6 expr=0
x=7 expr=3
x=8 expr=0
x=9 expr=0
x=10 expr=0
x=11 expr=2
x=12 expr=2
x=13 expr=2
x=14 expr=2
x=15 expr=2
x=16 expr=2
x=17 expr=2
x=18 expr=2
x=19 expr=2
x=20 expr=2

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C++ code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Java code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C\# code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Go code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Product of a Boolean variable and an integer variable Copy Chapter

This sample implements an helper function that will take two variables (Boolean
and integer), and will return a new integer variable that is constrained to be
equal to the product of the two variables.

The following samples output:

x=1 b=0 p=0
x=2 b=0 p=0
x=3 b=0 p=0
x=5 b=0 p=0
x=6 b=0 p=0
x=7 b=0 p=0
x=9 b=0 p=0
x=10 b=0 p=0
x=1 b=1 p=1
x=2 b=1 p=2
x=3 b=1 p=3
x=5 b=1 p=5
x=6 b=1 p=6
x=7 b=1 p=7
x=9 b=1 p=9
x=10 b=1 p=10

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Scanning the domain of variables. Copy Chapter

In this example, we will implement the all_different_except_0 constraint. This
constraint is useful as it expresses that 2 active assignment should be
different, but we do not care when they are inactive (represented by being
assigned a zero value).

To implement this constraint, we will collect all values in the initial domain
of all variables and attach Boolean variables for each of them. This requires
reading back the values from the model.

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Ortools Sat Docs Model (`ortools/sat/docs/model.md`) Copy Section

Model manipulation

https://developers.google.com/optimization/

Introduction Copy Chapter

In all languages, the CpModel class is a thin wrapper around a
protocol buffer object
cp_model.proto.

Some functionalities require using the cp_model protobuf directly. To write code
that manipulates this protobuf, one must understand how modeling objects
(variables, constraints) are mapped onto the protobuf.

The fundamental idea is that the cp_model protobuf object contains a list of
variables and a list of constraints. Constraints are built with variables and
reference them using their indices in the list of variables.

In all languages, the IntVar class has a method to query their index in the
model list of variables:

• C++: var.index()
• Python: var.Index()
• Java: var.getIndex()
• C#: var.Index or var.GetIndex()
• Go: var.Index()

The implementation of Boolean literals differs across languages.

• C++: The BoolVar class is a separate class from the IntVar class. A
  BoolVar object can implicitly be cast to an IntVar object. A BoolVar
  object has two important methods: index() and Not(). Not() returns
  another BoolVar with a different index: b.Not().index() = -b.index() - 1.
• Python: There is no BoolVar class. A Boolean variable is defined as an
  IntVar with a Boolean domain (0 or 1). The Not() method returns a
  different class. Both the IntVar class and the negation class implement
  Index() and Not().
• Java: There is no BoolVar class. A Boolean variable is defined as an
  IntVar with a Boolean domain (0 or 1). Boolean variables and their
  negation implement the Literal interface. This interface defines
  getIndex() and not() methods.
• C#: Boolean variables are defined as an IntVar with a Boolean domain
  (0 or 1). Boolean variables and their negations implement the ILiteral
  interface. This interface defines GetIndex() and Not() methods.
• Go: The BoolVar class is a separate class from the IntVar class. A
  BoolVar object has two important methods: Not() and Index(). Not()
  returned another BoolVar with a different index: b.Not.Index() = -b.Index() - 1

Solution hinting Copy Chapter

A solution is a partial assignment of variables to values that the search will
try to stick to. It is meant to guide the search with external knowledge towards
good solutions.

The CpModelProto message has a solution_hint field. This field is a
PartialVariableAssignment message that contains two parallel vectors (variable
indices and hint values).

Adding solution hinting to a model implies filling these two fields. This is
done by the addHint, AddHint, or SetHint methods.

Some remarks:

• A solution hint is not a hard constraint. The solver will try to use it in
  search for a while, and then gradually revert to its default search
  technique.
• It's OK to have an infeasible solution hint. It can still be helpful in some
  repair procedures, where one wants to identify a solution close to a
  previously violated state.
• Solution hints don't need to use all variables: partial solution hints are
  fine.

Python code Copy Section

# Snippet from ortools/sat/samples/solution_hinting_sample_sat.py
from ortools.sat.python import cp_model


def solution_hinting_sample_sat():
  """Showcases solution hinting."""
  # Creates the model.
  model = cp_model.CpModel()

  # Creates the variables.
  num_vals = 3
  x = model.new_int_var(0, num_vals - 1, 'x')
  y = model.new_int_var(0, num_vals - 1, 'y')
  z = model.new_int_var(0, num_vals - 1, 'z')

  # Creates the constraints.
  model.add(x != y)

  model.maximize(x + 2 * y + 3 * z)

  # Solution hinting: x <- 1, y <- 2
  model.add_hint(x, 1)
  model.add_hint(y, 2)

  # Creates a solver and solves.
  solver = cp_model.CpSolver()
  solution_printer = cp_model.VarArrayAndObjectiveSolutionPrinter([x, y, z])
  status = solver.solve(model, solution_printer)

  print(f'Status = {solver.status_name(status)}')
  print(f'Number of solutions found: {solution_printer.solution_count}')


solution_hinting_sample_sat()

C++ code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Java code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C\# code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Go code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Model copy Copy Chapter

The CpModel classes supports deep copy from a previous model. This is useful
to solve variations of a base model. The trick is to recover the copies of the
variables in the original model to be able to manipulate the new model. This is
illustrated in the following examples.

Python code Copy Section

The deep copy python mechanism relies on the
copy Python Standard Library.

# Snippet from ortools/sat/samples/clone_model_sample_sat.py
import copy

from ortools.sat.python import cp_model


def clone_model_sample_sat():
  """Showcases cloning a model."""
  # Creates the model.
  model = cp_model.CpModel()

  # Creates the variables.
  num_vals = 3
  x = model.new_int_var(0, num_vals - 1, 'x')
  y = model.new_int_var(0, num_vals - 1, 'y')
  z = model.new_int_var(0, num_vals - 1, 'z')

  # Creates the constraints.
  model.add(x != y)

  model.maximize(x + 2 * y + 3 * z)

  # Creates a solver and solves.
  solver = cp_model.CpSolver()
  status = solver.solve(model)

  if status == cp_model.OPTIMAL:
    print(
        'Optimal value of the original model: {}'.format(solver.objective_value)
    )

  # Creates a dictionary holding the model and the variables you want to use.
  to_clone = {
      'model': model,
      'x': x,
      'y': y,
      'z': z,
  }

  # Deep copy the dictionary.
  clone = copy.deepcopy(to_clone)

  # Retrieve the cloned model and variables.
  cloned_model: cp_model.CpModel = clone['model']
  cloned_x = clone['x']
  cloned_y = clone['y']
  cloned_model.add(cloned_x + cloned_y <= 1)

  status = solver.solve(cloned_model)

  if status == cp_model.OPTIMAL:
    print(
        'Optimal value of the modified model: {}'.format(solver.objective_value)
    )


clone_model_sample_sat()

C++ code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Java code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Ortools Sat Docs Scheduling (`ortools/sat/docs/scheduling.md`) Copy Section

Scheduling recipes for the CP-SAT solver.

https://developers.google.com/optimization/

Introduction Copy Chapter

Scheduling in Operations Research involves problems of tasks, resources and
times. In general, scheduling problems have the following features: fixed or
variable durations, alternate ways of performing the same task, mutual
exclusivity between tasks, and temporal relations between tasks.

Interval variables Copy Chapter

Intervals are constraints containing three constant of affine expressions
(start, size, and end). Creating an interval constraint will enforce that `start

• size == end`.

The more general API uses three expressions to define the interval. If the size
is fixed, a simpler API uses the start expression and the fixed size.

Creating these intervals is illustrated in the following code snippets.

Python code Copy Section

# Snippet from ortools/sat/samples/interval_sample_sat.py
"""Code sample to demonstrates how to build an interval."""


from ortools.sat.python import cp_model


def interval_sample_sat():
  """Showcases how to build interval variables."""
  model = cp_model.CpModel()
  horizon = 100

  # An interval can be created from three affine expressions.
  start_var = model.new_int_var(0, horizon, 'start')
  duration = 10  # Python cp/sat code accept integer variables or constants.
  end_var = model.new_int_var(0, horizon, 'end')
  interval_var = model.new_interval_var(
      start_var, duration, end_var + 2, 'interval'
  )

  print(f'interval = {repr(interval_var)}')

  # If the size is fixed, a simpler version uses the start expression and the
  # size.
  fixed_size_interval_var = model.new_fixed_size_interval_var(
      start_var, 10, 'fixed_size_interval_var'
  )
  print(f'fixed_size_interval_var = {repr(fixed_size_interval_var)}')

  # A fixed interval can be created using the same API.
  fixed_interval = model.new_fixed_size_interval_var(5, 10, 'fixed_interval')
  print(f'fixed_interval = {repr(fixed_interval)}')


interval_sample_sat()

C++ code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Java code Copy Section

// Snippet from ortools/sat/samples/IntervalSampleSat.java
package com.google.ortools.sat.samples;

import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.IntervalVar;
import com.google.ortools.sat.LinearExpr;

/** Code sample to demonstrates how to build an interval. */
public class IntervalSampleSat {
  public static void main(String[] args) throws Exception {
    Loader.loadNativeLibraries();
    CpModel model = new CpModel();
    int horizon = 100;

    // An interval can be created from three affine expressions.
    IntVar startVar = model.newIntVar(0, horizon, "start");
    IntVar endVar = model.newIntVar(0, horizon, "end");
    IntervalVar intervalVar =
        model.newIntervalVar(
            startVar,
            LinearExpr.constant(10),
            LinearExpr.newBuilder().add(endVar).add(2),
            "interval");
    System.out.println(intervalVar);

    // If the size is fixed, a simpler version uses the start expression and the size.
    IntervalVar fixedSizeIntervalVar =
        model.newFixedSizeIntervalVar(startVar, 10, "fixed_size_interval_var");
    System.out.println(fixedSizeIntervalVar);

    // A fixed interval can be created using another method.
    IntervalVar fixedInterval = model.newFixedInterval(5, 10, "fixed_interval");
    System.out.println(fixedInterval);
  }
}

C\# code Copy Section

// Snippet from ortools/sat/samples/IntervalSampleSat.cs
using System;
using Google.OrTools.Sat;

public class IntervalSampleSat
{
    static void Main()
    {
        CpModel model = new CpModel();
        int horizon = 100;

        // C# code supports constant of affine expressions.
        IntVar start_var = model.NewIntVar(0, horizon, "start");
        IntVar end_var = model.NewIntVar(0, horizon, "end");
        IntervalVar interval = model.NewIntervalVar(start_var, 10, end_var + 2, "interval");
        Console.WriteLine(interval);

        // If the size is fixed, a simpler version uses the start expression, the size and the
        // literal.
        IntervalVar fixedSizeIntervalVar = model.NewFixedSizeIntervalVar(start_var, 10, "fixed_size_interval_var");
        Console.WriteLine(fixedSizeIntervalVar);

        // A fixed interval can be created using the same API.
        IntervalVar fixedInterval = model.NewFixedSizeIntervalVar(5, 10, "fixed_interval");
        Console.WriteLine(fixedInterval);
    }
}

Go code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Optional intervals Copy Chapter

An interval can be marked as optional. The presence of this interval is
controlled by a literal. The no overlap and cumulative constraints
understand these presence literals, and correctly ignore inactive intervals.

Python code Copy Section

# Snippet from ortools/sat/samples/optional_interval_sample_sat.py
"""Code sample to demonstrates how to build an optional interval."""

from ortools.sat.python import cp_model


def optional_interval_sample_sat():
  """Showcases how to build optional interval variables."""
  model = cp_model.CpModel()
  horizon = 100

  # An interval can be created from three affine expressions.
  start_var = model.new_int_var(0, horizon, 'start')
  duration = 10  # Python cp/sat code accept integer variables or constants.
  end_var = model.new_int_var(0, horizon, 'end')
  presence_var = model.new_bool_var('presence')
  interval_var = model.new_optional_interval_var(
      start_var, duration, end_var + 2, presence_var, 'interval'
  )

  print(f'interval = {repr(interval_var)}')

  # If the size is fixed, a simpler version uses the start expression and the
  # size.
  fixed_size_interval_var = model.new_optional_fixed_size_interval_var(
      start_var, 10, presence_var, 'fixed_size_interval_var'
  )
  print(f'fixed_size_interval_var = {repr(fixed_size_interval_var)}')

  # A fixed interval can be created using the same API.
  fixed_interval = model.new_optional_fixed_size_interval_var(
      5, 10, presence_var, 'fixed_interval'
  )
  print(f'fixed_interval = {repr(fixed_interval)}')


optional_interval_sample_sat()

C++ code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Java code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C\# code Copy Section

// Snippet from ortools/sat/samples/OptionalIntervalSampleSat.cs
using System;
using Google.OrTools.Sat;

public class OptionalIntervalSampleSat
{
    static void Main()
    {
        CpModel model = new CpModel();
        int horizon = 100;

        // C# code supports constant of affine expressions.
        IntVar start_var = model.NewIntVar(0, horizon, "start");
        IntVar end_var = model.NewIntVar(0, horizon, "end");
        BoolVar presence_var = model.NewBoolVar("presence");
        IntervalVar interval = model.NewOptionalIntervalVar(start_var, 10, end_var + 2, presence_var, "interval");
        Console.WriteLine(interval);

        // If the size is fixed, a simpler version uses the start expression, the size and the
        // literal.
        IntervalVar fixedSizeIntervalVar =
            model.NewOptionalFixedSizeIntervalVar(start_var, 10, presence_var, "fixed_size_interval_var");
        Console.WriteLine(fixedSizeIntervalVar);

        // A fixed interval can be created using the same API.
        IntervalVar fixedInterval = model.NewOptionalFixedSizeIntervalVar(5, 10, presence_var, "fixed_interval");
        Console.WriteLine(fixedInterval);
    }
}

Go code Copy Section

// Snippet from ortools/sat/samples/optional_interval_sample_sat.go
// The optional_interval_sample_sat command is an example of an Interval variable that is
// marked as optional.
package main

import (
	"fmt"

	log "github.com/golang/glog"
	"github.com/google/or-tools/ortools/sat/go/cpmodel"
)

const horizon = 100

func optionalIntervalSampleSat() error {
	model := cpmodel.NewCpModelBuilder()
	domain := cpmodel.NewDomain(0, horizon)

	x := model.NewIntVarFromDomain(domain).WithName("x")
	y := model.NewIntVar(2, 4).WithName("y")
	z := model.NewIntVarFromDomain(domain).WithName("z")
	presenceVar := model.NewBoolVar().WithName("presence")

	// An optional interval can be created from three affine expressions and a BoolVar.
	intervalVar := model.NewOptionalIntervalVar(x, y, cpmodel.NewConstant(2).Add(z), presenceVar).WithName("interval")

	// If the size is fixed, a simpler version uses the start expression and the size.
	fixedSizeIntervalVar := model.NewOptionalFixedSizeIntervalVar(x, 10, presenceVar).WithName("fixedSizeInterval")

	m, err := model.Model()
	if err != nil {
		return fmt.Errorf("failed to instantiate the CP model: %w", err)
	}
	fmt.Printf("%v\n", m.GetConstraints()[intervalVar.Index()])
	fmt.Printf("%v\n", m.GetConstraints()[fixedSizeIntervalVar.Index()])

	return nil
}

func main() {
	if err := optionalIntervalSampleSat(); err != nil {
		log.Exitf("optionalIntervalSampleSat returned with error: %v", err)
	}
}

Time relations between intervals Copy Chapter

Temporal relations between intervals can be expressions using linear
inequalities involving the start and end expressions of the intervals.

As seen above, the factory methods on the model used to build intervals accept
1-var affine expression (a * var + b, a, b integer constants) as arguments to
the start, size, and end parameters.

Once the interval is build, these same expressions can be queries using
StartExpr(), SizeExpr() and EndExpr() in C++ and C#, start_expr(), size_expr(), and end_expr() in python, and getStartExpr(), getSizeExpr(), and getEndExpr() in Java.

If one or both intervals are optional, then these inequalities must be reified
by the presence literals of the optional intervals used.

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

NoOverlap constraint Copy Chapter

A no_overlap constraint simply states that all intervals are disjoint. It is
built with a list of interval variables. Fixed intervals are useful for
excluding part of the timeline.

In the following examples, you want to schedule 3 tasks on 3 weeks excluding
weekends, making the final day as early as possible.

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C++ code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Java code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C\# code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Go code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Cumulative constraint with min and max capacity profile. Copy Chapter

A cumulative constraint takes a list of intervals, and a list of demands, and a
capacity. It enforces that at any time point, the sum of demands of tasks active
at that time point is less than a given capacity.

Modeling a non constant max profile can be done using fixed (interval, demand)
to occupy the capacity between the actual profile and it max capacity.

Modeling a non zero min profile can be done using fixed (interval, demand) on
the complementary cumulative constraint.

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Alternative resources for one interval Copy Chapter

Ranking tasks in a disjunctive resource Copy Chapter

To rank intervals in a no_overlap constraint, you will count the number of
performed intervals that precede each interval.

This is slightly complicated if some interval variables are optional. To
implement it, you will create a matrix of precedences boolean variables.
precedences[i][j] is set to true if and only if interval i is performed,
interval j is performed, and if the start of i is before the start of j.

Furthermore, precedences[i][i] is set to be equal to presences[i]. This way,
you can define the rank of an interval i as sum over j(precedences[j][i]) - 1. If the interval is not performed, the rank computed as -1, if the interval
is performed, its presence variable negates the -1, and the formula counts the
number of other intervals that precede it.

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C++ code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Java code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C\# code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Go code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Ranking tasks in a disjunctive resource with a circuit constraint. Copy Chapter

To rank intervals in a no_overlap constraint, you will use a circuit constraint
to perform the transitive reduction from precedences to successors.

This is slightly complicated if some interval variables are optional, and you
need to take into account the case where no task is performed.

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Intervals spanning over breaks in the calendar Copy Chapter

Sometimes, a task can be interrupted by a break (overnight, lunch break). In
that context, although the processing time of the task is the same, the duration
can vary.

To implement this feature, you will have the duration of the task be a function
of the start of the task. This is implemented using channeling constraints.

The following code displays:

start=8 duration=3 across=0
start=9 duration=3 across=0
start=10 duration=3 across=0
start=11 duration=4 across=1
start=12 duration=4 across=1
start=14 duration=3 across=0
start=15 duration=3 across=0

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Detecting if two intervals overlap. Copy Chapter

You want a Boolean variable to be true if and only if two intervals overlap. To
enforce this, you will create 3 Boolean variables, link two of them to the
relative positions of the two intervals, and define the third one using the
other two Boolean variables.

There are two ways of linking the three Boolean variables. The first version
uses one clause and two implications. Propagation will be faster using this
version. The second version uses a sum(..) == 1 equation. It is more compact,
but assumes the length of the two intervals is > 0.

Note that you need to create the intervals to enforce start + size == end, but
you do not actually use them in this code sample.

The following code displays

start_a=0 start_b=0 a_overlaps_b=1
start_a=0 start_b=1 a_overlaps_b=1
start_a=0 start_b=2 a_overlaps_b=1
start_a=0 start_b=3 a_overlaps_b=0
start_a=0 start_b=4 a_overlaps_b=0
start_a=0 start_b=5 a_overlaps_b=0
start_a=1 start_b=0 a_overlaps_b=1
start_a=1 start_b=1 a_overlaps_b=1
start_a=1 start_b=2 a_overlaps_b=1
start_a=1 start_b=3 a_overlaps_b=1
start_a=1 start_b=4 a_overlaps_b=0
start_a=1 start_b=5 a_overlaps_b=0
...

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Transitions in a no_overlap constraint Copy Chapter

In some scheduling problems, switching between certain type of tasks on a
machine implies some penalty, and/or some delay. Implementing these
functionalities implies knowing which are the direct successors of each task.

The circuit constraint is used to perform the transitive reduction from
precedences to successors. Once this is done, it is straightforward to use the
successor literals to implement the penalties or the delays.

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Managing sequences in a no_overlap constraint Copy Chapter

In some scheduling problems, there can be constraints on sequence of tasks. For
instance, tasks of a given type may have limit on the min or max number of
contiguous tasks of the same type.

The circuit constraint is used to constraint the length of any sequence of tasks
of the same type. It uses counters attached to each task, and transition
literals to maintain these counters.

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Convex hull of a set of intervals Copy Chapter

Ortools Sat Docs Solver (`ortools/sat/docs/solver.md`) Copy Section

Solving a CP-SAT model

https://developers.google.com/optimization/

Changing the parameters of the solver Copy Chapter

The SatParameters protobuf encapsulates the set of parameters of a CP-SAT
solver. The most useful one is the time limit.

Specifying the time limit in Python Copy Section

# Snippet from ortools/sat/samples/solve_with_time_limit_sample_sat.py
"""Solves a problem with a time limit."""

from ortools.sat.python import cp_model


def solve_with_time_limit_sample_sat():
  """Minimal CP-SAT example to showcase calling the solver."""
  # Creates the model.
  model = cp_model.CpModel()
  # Creates the variables.
  num_vals = 3
  x = model.new_int_var(0, num_vals - 1, 'x')
  y = model.new_int_var(0, num_vals - 1, 'y')
  z = model.new_int_var(0, num_vals - 1, 'z')
  # Adds an all-different constraint.
  model.add(x != y)

  # Creates a solver and solves the model.
  solver = cp_model.CpSolver()

  # Sets a time limit of 10 seconds.
  solver.parameters.max_time_in_seconds = 10.0

  status = solver.solve(model)

  if status == cp_model.OPTIMAL:
    print(f'x = {solver.value(x)}')
    print(f'y = {solver.value(y)}')
    print(f'z = {solver.value(z)}')


solve_with_time_limit_sample_sat()

Specifying the time limit in C++ Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Specifying the time limit in Java Copy Section

// Snippet from ortools/sat/samples/SolveWithTimeLimitSampleSat.java
package com.google.ortools.sat.samples;

import com.google.ortools.Loader;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.IntVar;

/** Solves a problem with a time limit. */
public final class SolveWithTimeLimitSampleSat {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Create the model.
    CpModel model = new CpModel();
    // Create the variables.
    int numVals = 3;

    IntVar x = model.newIntVar(0, numVals - 1, "x");
    IntVar y = model.newIntVar(0, numVals - 1, "y");
    IntVar z = model.newIntVar(0, numVals - 1, "z");
    // Create the constraint.
    model.addDifferent(x, y);

    // Create a solver and solve the model.
    CpSolver solver = new CpSolver();
    solver.getParameters().setMaxTimeInSeconds(10.0);
    CpSolverStatus status = solver.solve(model);

    if (status == CpSolverStatus.OPTIMAL) {
      System.out.println("x = " + solver.value(x));
      System.out.println("y = " + solver.value(y));
      System.out.println("z = " + solver.value(z));
    }
  }

  private SolveWithTimeLimitSampleSat() {}
}

Specifying the time limit in C\#. Copy Section

Parameters must be passed as string to the solver.

// Snippet from ortools/sat/samples/SolveWithTimeLimitSampleSat.cs
using System;
using Google.OrTools.Sat;

public class SolveWithTimeLimitSampleSat
{
    static void Main()
    {
        // Creates the model.
        CpModel model = new CpModel();
        // Creates the variables.
        int num_vals = 3;

        IntVar x = model.NewIntVar(0, num_vals - 1, "x");
        IntVar y = model.NewIntVar(0, num_vals - 1, "y");
        IntVar z = model.NewIntVar(0, num_vals - 1, "z");
        // Adds a different constraint.
        model.Add(x != y);

        // Creates a solver and solves the model.
        CpSolver solver = new CpSolver();

        // Adds a time limit. Parameters are stored as strings in the solver.
        solver.StringParameters = "max_time_in_seconds:10.0";

        CpSolverStatus status = solver.Solve(model);

        if (status == CpSolverStatus.Optimal)
        {
            Console.WriteLine("x = " + solver.Value(x));
            Console.WriteLine("y = " + solver.Value(y));
            Console.WriteLine("z = " + solver.Value(z));
        }
    }
}

Specifying the time limit in Go Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Printing intermediate solutions Copy Chapter

In an optimization model, you can print intermediate solutions. For all
languages except Go, you need to register a callback on the solver that will be
called at each solution. For Go, callbacks are not implemented, but you can
still get the intermediate solutions in the response.

The exact implementation depends on the target language.

Python code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C++ code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Java code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

C\# code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Go code Copy Section

/* Detailed source-code truncated for AI context efficiency. */

Searching for all solutions in a satisfiability model Copy Chapter

In an non-optimization model, you can search for all solutions. For all
languages except Go, you need to register a callback on the solver that will be
called at each solution. For Go, callbacks are not implemented, but you can
still get the intermediate solutions in the response.

Note that it does not work in parallel (i. e. parameter num_workers > 1).

It also does not work if the model contains an objective.

The method will return the following:

• FEASIBLE if some solutions have been found
• INFEASIBLE if the solver has proved there are no solution
• OPTIMAL if all solutions have been found

The exact implementation depends on the target language.

Python code Copy Section

To search for all solutions, use the Solve() method after setting the correct
parameter.

# Snippet from ortools/sat/samples/search_for_all_solutions_sample_sat.py
from ortools.sat.python import cp_model


class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):
  """Print intermediate solutions."""

  def __init__(self, variables: list[cp_model.IntVar]):
    cp_model.CpSolverSolutionCallback.__init__(self)
    self.__variables = variables
    self.__solution_count = 0

  def on_solution_callback(self) -> None:
    self.__solution_count += 1
    for v in self.__variables:
      print(f'{v}={self.value(v)}', end=' ')
    print()

  @property
  def solution_count(self) -> int:
    return self.__solution_count


def search_for_all_solutions_sample_sat():
  """Showcases calling the solver to search for all solutions."""
  # Creates the model.
  model = cp_model.CpModel()

  # Creates the variables.
  num_vals = 3
  x = model.new_int_var(0, num_vals - 1, 'x')
  y = model.new_int_var(0, num_vals - 1, 'y')
  z = model.new_int_var(0, num_vals - 1, 'z')

  # Create the constraints.
  model.add(x != y)

  # Create a solver and solve.
  solver = cp_model.CpSolver()
  solution_printer = VarArraySolutionPrinter([x, y, z])
  # Enumerate all solutions.
  solver.parameters.enumerate_all_solutions = True
  # Solve.
  status = solver.solve(model, solution_printer)

  print(f'Status = {solver.status_name(status)}')
  print(f'Number of solutions found: {solution_printer.solution_count}')


search_for_all_solutions_sample_sat()

C++ code Copy Section

To search for all solutions, a parameter of the SAT solver must be changed.

/* Detailed source-code truncated for AI context efficiency. */

Java code Copy Section

As in Python, CpSolver.solve() must be called after setting the correct
parameter.

/* Detailed source-code truncated for AI context efficiency. */

C\# code Copy Section

As in Python, CpSolver.Solve() must be called after setting the correct string
parameter.

/* Detailed source-code truncated for AI context efficiency. */

Go code Copy Section

To search for all solutions, a parameter of the SAT solver must be changed.

/* Detailed source-code truncated for AI context efficiency. */

Stopping search early Copy Chapter

Sometimes, you might decide that the current solution is good enough. In this
section, we will enumerate all possible combinations of three variables, and
stop after the fifth combination found.

Python code Copy Section

You can stop the search by calling StopSearch() inside of
CpSolverSolutionCallback.OnSolutionCallback().

/* Detailed source-code truncated for AI context efficiency. */

C++ code Copy Section

Stopping search is done by registering an atomic bool on the model-owned time
limit, and setting that bool to true.

/* Detailed source-code truncated for AI context efficiency. */

Java code Copy Section

Stopping search is performed by calling stopSearch() inside of
CpSolverSolutionCallback.onSolutionCallback().

/* Detailed source-code truncated for AI context efficiency. */

C\# code Copy Section

Stopping search is performed by calling StopSearch() inside of
CpSolverSolutionCallback.OnSolutionCallback().

/* Detailed source-code truncated for AI context efficiency. */

Ortools Sat Docs Troubleshooting (`ortools/sat/docs/troubleshooting.md`) Copy Section

Troubleshooting

Enable logging Copy Chapter

CP-SAT supports extensive logging of its internals.

To enable it, just set the parameter log_search_progress to true.

A good explanation of the log can be found in the
cpsat-primer.

Exporting the model Copy Chapter

As seen in the model section, the model is stored as a protocol
buffer object. This protocol buffer can be exported using the command
model.ExportToFile(filename) and model.exportToFile(filename) in java.

if filename ends with .txt or .textproto, the model will be written using
the protocol buffer text format. Otherwise, the binary format will be used.

Note that the binary format is not human readable, but takes less space.

Improving performance with multiple workers Copy Chapter

CP-SAT is built with parallelism in mind. While you can achieve a good solution
with a single worker, you'll get the best results when using multiple workers.

There are several tiers of behavior:

• [8 workers] This is the minimum number of workers needed to trigger
  parallel search. It blends workers with different linear relaxations (none,
  default, maximal), core-based search if applicable, a quick_restart
  subsolver, a feasibility_jump first solution subsolver, and dedicated Large
  Neighborhood Search subsolvers to find improved solutions.
• [16 workers] Bumping to 16 workers adds a continuous probing subsolver,
  more first solution subsolvers (random search and feasibility_jump), two
  dual subsolvers dedicated to improving the lower bound of the objective
  (when minimizing), and more LNS subsolvers.
• [24 workers] Adds more dual subsolvers, no_lp and max_lp variations of
  previous subsolvers, more feasibility_jump first solution subsolvers, and
  more LNS subsolvers.
• [32 workers and more] Adds more LNS workers, and more first solution
  subsolvers.

Solve status Copy Chapter

Solving a problem yields the following possible status (CpSolverStatus):

• [UNKNOWN] The status of the model is still unknown. A search limit has
  been reached before any of the statuses below could be determined.
• [MODEL_INVALID] The given CpModelProto didn't pass the validation step.
  You can get a detailed error by calling ValidateCpModel(model_proto)in
  C++, or model.Validate() in other languages.
• [FEASIBLE] A feasible solution has been found. But the search was
  stopped before we could prove optimality or before we enumerated all
  solutions of a feasibility problem (if asked).
• [INFEASIBLE] The problem has been proven infeasible.
• [OPTIMAL] An optimal feasible solution has been found. More generally,
  this status represents a success. So we also return OPTIMAL if we find a
  solution for a pure feasibility problem or if a gap limit has been specified
  and we return a solution within this limit. In the case where we need to
  return all the feasible solution, this status will only be returned if
  solve() enumerated all of them; If we stopped earlier, we will return
  FEASIBLE.

Debugging infeasible models Copy Chapter