OR-Tools リリースノート

このページでは、新機能、バグの修正、コードとインストール手順の改善など、OR-Tools の変更点について説明します。

OR-Tools のインストールで問題が発生した場合は、OR-Tools のインストール手順のトラブルシューティングのセクションをご覧ください。問題がここに記載されていない場合は、GitHub の問題を確認するか、新しい問題をオープンしてください。サポートをいたします。

OR-Tools のリリースノートは次のとおりです（最新リリース以降）。

2024 年 5 月

OR-Tools v9.10 のリリースのお知らせ

OR-Tools v9.10 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

GitHub でリリースノートを入手できます。

2024 年 3 月

OR-Tools v9.9 のリリースのお知らせ

OR-Tools v9.9 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

GitHub でリリースノートを入手できます。

2023 年 11 月

OR-Tools v9.8 のリリースのお知らせ

OR-Tools v9.8 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

プラットフォームの変更点

• Python 3.12 を追加しました。
• Ubuntu 23.10 のサポートを追加する

線形ソルバー

• ポート ModelBuilder を .Net へ。
• SAT LogCallback との競合を回避するために、LogCallback の名前を MbLogCallback に変更しました。
• ModelBuilder API を拡張します。
  • インジケーターの制約を追加する。
  • ヒンティングのサポートを追加します。
  • モデルのクローンを作成する。

数学（最適化）

• 徹底的なやり直し。

ルーティング

• ROUTING_OPTIMAL ステータスを追加。
• RoutingModel をコピーまたは移動不可にしました。
• ローカル検索演算子の無限ループを修正。
• PickupDeliveryPosition 内部構造体を追加しました。
• IsPickup() メソッドと IsDelivery() メソッドを追加しました。

土

• 大規模モデルのメモリ使用量を削減する。
• スケジュール検索が改善されました。
• packing_precedences_lns を追加します
• 実現可能性のジャンプを最適化して修正します
• 線形事前解決と事前解決ロギングを改善します
• int_abs、int_mod、int_prod、lin_max の presolve を改善しました。
• Panda のサポートを改善する
• いくつかのバグを修正。

GitHub の変更ログ

2023 年 8 月

OR-Tools v9.7 のリリースのお知らせ

OR-Tools v9.7 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

プラットフォームの変更点

• Centos-8（EOL）をドロップします。
• Debian 10 を削除します。
• Fedora [33, 36]（EOL）をドロップします。
• Ubuntu 18.04 LTS（EOL）をドロップします。
• Python 3.7（EOL）を削除します。
• CMake で netcore3.1 のサポートを無効にする（EOL）。

モデルビルダー Python

• Pandas DataFrame と Series を使用して変数を作成できるようにします。
  • 課題を見る
  • bin_packing をご覧ください。
• 情報を入力する

PDLP

• 更新できます。

CP-SAT

• パフォーマンスの改善。（feasibility_jump、lin_max）
• カット管理の改善
• 目標の下限の改善専用の新しい requirements_shaving_search ワーカー（最小化時）
• Python の cp_model.py のアノテーションの入力
• cp_model.py での pandas の試験運用版の部分的なサポート
  • 課題を見る
  • bin_packing をご覧ください。
• 試験運用版のローカル検索違反ベースのワーカー:
  • 次のパラメータで有効: num_violation_ls:xxx
  • 線形モデル（linear、bool_or、bool_and、at_most_one、exactly_one）向けに最適化
  • lin_max、product、division が正しく動作する
  • no_overlap、累積、サーキット、ルートをサポート
  • no_overlap_2d で無効
  • 推奨される ls ワーカー数: num_workers -> num_violation_ls: (8, 1), (16, 2) (24, 3), (32, 4)

GitHub の変更ログ

2023 年 3 月

OR-Tools v9.6 のリリースのお知らせ

OR-Tools v9.6 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

プラットフォームの変更点

• Fedora 37、38 のサポートを追加しました。
• Python 3.6 を削除します（protobuf ではサポートされていません）。
• macOS に Python 3.7 をドロップします（scipy ではサポートされていません）。
• CMake に net7.0 サポートを追加（-DUSE_DOTNET_7=ON を使用）
• Nuget .org パッケージに netcore3.1 をドロップ

依存関係

• SCIP v801 -> v803（注: 現在、SCIP では OSI 互換ライセンスが使用されます）
• 横方向 20220623.1 -> 20230105.0
• プロトコル バッファ v21.5 -> v21.12
• SWIG 4.1.1
• Java JNA 5.11.0 -> 5.12.1

Bazel

• pybind11 のサポートを追加しました。
• Java ラッパーのサポートを追加しました。

ソルバー

• PDLP: dd Python ラッパー
• CP-SAT: パフォーマンスの改善。
• GLOP: 事前解決を調整。
• ModelBuilder: Python: numpy のサポートを改善しました。
• ルーティング: パフォーマンスの改善（ローカル検索）

既知の問題:

• CP-SAT: pseudo_costs サブソルバーを無視すると、無効なパラメータが返される（#3706 を参照）。

2022 年 11 月

OR-Tools v9.5 のリリースのお知らせ

OR-Tools v9.5 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

プラットフォームの変更点

• Debian Sid のサポートを追加しました。
• Fedora 35、36 のサポートを追加しました。
• Ubuntu 22.10 のサポートを追加しました。
• macOS に Python 3.6 を削除します。
• Python 3.11 のサポートを追加しました。

依存関係の更新

• Protobuf v19.4 -> v21.5。
• SCIP ソルバー v800 -> v801。

CP-SAT

• 改善された機能: max(array)、ブール値制約、線形制約。
• インターリーブ検索は並列で確定的でなければなりません。
• 線形カット: 正方形と int_prod のカットをクリーンアップし、カット パイプラインを書き換えます。
• 指紋の入力モデルとソリューション（ログに表示）。
• スケジュール設定の改善。
• 通常のバグ修正（事前解決中のクラッシュ、カットでのクラッシュ、実行不可能なソリューション、LNS でモデルを実行できない）

GLOP

• 線形代数とピボット選択ルールを書き換えて、スピードアップしましょう。

線形ソルバー

• knapsack_interface.cc 個追加します。
• model_builder API を linear_solver ディレクトリ（ヘッダーとサンプル）の下に移動します。
• Gurobi 10 のサポートを追加しました。

ルーティング

• さまざまなルーティングの課題に対して、いくつかのパーサーを解放。

2022 年 8 月

OR-Tools v9.4 のリリースのお知らせ

OR-Tools v9.4 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

プラットフォーム

• Debian-10 のサポートを追加しました（#3029 を参照）。
• Ubuntu 22.04 LTS のサポートを追加しました（#3276 を参照）。注: .Net 3.1 はサポートされていません（dotnet/core#7038 を参照）。
• Ubuntu 21.10 のサポートを削除しました。

その他

• 言語ごとにアーカイブを分割し、CMake 設定を C++ 言語に追加しました（#3200）。

グラフ

ortools.graph.pywrapgraph の分割:

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

これにより、numpy を使用して問題のセットアップを迅速化できます。

CP-SAT

以下の点が改善されました。

• スケジューリング（伝播、カット、下限）が含まれます。
• MaxSAT（事前解決、コアベースのヒューリスティック）。
• MIP パフォーマンス（事前解決、カット）。

2022 年 3 月

OR-Tools v9.3 のリリースのお知らせ

OR-Tools v9.3 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

プラットフォームの変更点

• Debian-10 のサポートを終了しました。
• Ubuntu-16.04 のサポートを終了しました。
• .NET Framework 4.5.2 を削除します。

依存関係の更新

• 固有名 3.4.0 を追加しました。
• Google re2 2021-11-01 を追加します。
• Protobuf 3.19.1 -> 3.19.4。
• SCIP 7.0.1 -> v800。

Python

• pybind11 を追加しました。

機能

• PDLP を試験運用版として追加します。
• MathOpt を試験運用版として追加しました。

CP-SAT

• 整合性を保つため、いくつかの API の名前を変更（例: LinearExpr.ScalProd. から LinearExpr.WeightedSum.）。
• AddAtLeastOne/AddAtMostOne/AddExactlyOne メソッドを追加。
• すべての言語で AddMultiplicationConstraint(z, x, y) を追加します。
• すべての言語で AddMultipleCircuit() を追加します。

C++

• 明示的な ctor IntVar(BoolVar)。
• LinearExpr::Add* を削除し、演算子（例: LinearExpr +=）に置き換えました。
• 一次式に算術演算子を追加します。
• LinearExpr::BooleanSum/BooleanScalProd を削除しました。Sum/WeightedSum を使用してください。
• 変数のドメインを 1 つの値に上書きする CpModelBuilder::FixVariable() を追加します。

Java

• LinearExpr を書き換え、増分ビルダークラス LinearExpr.newBuilder().add(x).addSum(<array of variables>).build() を追加します。
• C++ API に準拠: Circuit、MultipleCircuit、Cumulative、Reservoir、AllowedAssignment、ForbiddenAssignment は、新しい変数、項、要求を追加するための増分 API を含む特殊なクラスを返すようになりました。

C

• すべてのメソッドを文書化します。
• C++ API に準拠: Circuit、MultipleCircuit、Cumulative、Reservoir、AllowedAssignment、ForbiddenAssignment は、新しい変数、項、要求を追加するための増分 API を含む特殊なクラスを返すようになりました。
• 式を段階的に作成できるように LinearExprBuilder クラスを追加しました。

ビルドシステム

CMake

• CMake が 3.18 以降であることが必要です。

製造元

• CMake ベースのビルドを内部で使用するようになりました。

2021 年 12 月

OR-Tools v9.2 のリリースのお知らせ

OR-Tools v9.2 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

プラットフォームの変更点

• Ubuntu 21:10（最後のローリング リリース）のサポートを追加しました。

依存関係の更新

• .Net TFM 更新 net5.0 -> net6.0（.Net SDK 6.0 LTS と .Net SDK 3.1 LTS が必要）。
• abseil-cpp 20210324.2 -> 20211102.0。
• Protobuf 3.18.0 -> 3.19.1。
• Googletest 1.10.0 から 1.11.0 へ。
• Python: numpy >= 1.13.3 を追加します。
• MacOS では、ランナーでのクラッシュを回避するために、-O1 で Coin-OR をコンパイルします。

ルーティング

• フィルタの改善。
• 最初のソリューションのヒューリスティックを改善します。
• 休憩の配置を改善する。

CP-SAT

破壊的変更

• 基になるプロトコル バッファは以前のバージョンと互換性がありません。保存されたプロトコル バッファは、更新されたビルダー API（C++、Python、Java、.NET）を使用して再生成する必要があります。
• 特に、インターバル protobuf は、古いフィールド（start、size、end）を削除し、削除されたフィールドの名前を使用するように新しいフィールドの名前を変更（_view を使用）したため、すっきりしました。

新しい機能と特長

• all_different、reservoir、modulo、multiplication、division 制約は、整数の変数を必要とするすべての場所でアフィン式（a * var + b）を受け入れます。
• 目的には、浮動小数点係数を使用できます（C++/Java/.NET の DoubleLinearExpr クラスをご覧ください。Python の knapsack_2d_sat.py の例をご覧ください）。
• no_overlap_2d 制約では、省略可能な間隔がサポートされています。
• C++ API は、+ 演算子と * 演算子を実装して式を作成します。

改善内容

• presolve コードを改善しました。
• 厳密なモデル チェッカー。
• リザーバの制約を再構築。
• no_overlap_2d 制約にエネルギッシュなカットを追加。
• エンコードの制約（literal implies var == value）の線形緩和が改善されました。

非推奨および削除されたメソッド

• C++ の BooleanSum と BooleanScalProd が非推奨になりました。 Sum と ScalProd のみを使用します。
• C++ の AddLinMinEquality と AddLinMaxEquality を削除しました。 AddMinEquality と AddMaxEquality のみを使用します。

今後の非互換性

• 将来的に、Java モデリング レイヤを C++ レイヤに近くなるように書き換えます。
• C++ モデリング レイヤで、IntVar(BoolVar var) ctor を明示的に指定します。
• Python API を PEP 8 準拠にすることを検討しています（snake_case 名を使用）。そのような場合は、コードを移植するための sed ファイルが提供されます。

ビルドシステム

Bazel

• Windows ビルドを修正。

CMake

• FETCH_PYTHON_DEPS オプションを追加（デフォルト: ON）。
• GPLK ソルバーのオプションのサポートを追加しました（デフォルト -DUSE_GLPK=OFF）。

Python

• ほとんどの CP-SAT API で numpy 整数をサポートします。
• __version__ の欠落を修正。

2021 年 9 月

OR-Tools v9.1 のリリースのお知らせ

OR-Tools v9.1 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

プラットフォームの変更点

• Python: manylinux2014 イメージを使用します（PEP 599 を参照）。
• Python: manylinux2014_aarch64 イメージを使用して aarch64 Linux のサポートを追加
• .Net: .Net 5.0 のサポートを追加します。

依存関係の更新

• abseil-cpp 20210324.1 -> 20210324.2。
• Protobuf 3.15.8 -> 3.18.0。
• SCIP 7.0.1 -> マスター。
• Googletest 1.8.0 -> 1.10.0。
• python: cp_model.py で warning を使用（#2530 を参照）。
• python: absl-py 0.11 -> 0.13。

CMake

• バンプの最小バージョンには 3.14 から 3.15 が必要（#2528 を参照）。
• Python: バンプの最小要件バージョン 3.14 -> 3.18（#2774 を参照）。

製造元

Make ベースのビルドは非推奨となりました。ソースからビルドするには、CMake または Bazel に移行してください。

Java

• ネイティブ ライブラリ ローダーの堅牢性を改善しました（#2742 を参照）。
• ルーティング モデルまたは制約ソルバーが破棄されたときに JVM ガベージ コレクタがクラッシュする問題を修正しました（#2091 を参照）（#2466 を参照）。
• 複数のワーカーを使用した場合の CP-SAT ロギング コールバックのクラッシュを修正しました（#2775 を参照）。

CP-SAT

• LNS コードの堅牢性を改善しました（#2525 を参照）。
• スケジューリング コードの改善: 固定サイズ間隔を作成するための新しいファクトリ メソッド、新しい検索ヒューリスティック、presolve の改善、新しい線形カット。
• ルーティング コードの改善: 新しい専用 LNS。
• モデル チェッカーを改善します。特に、潜在的なオーバーフローに関して、より細やかになりました。
• MIP コードの改善: MIP モデルと CP モデルの線形緩和に対する事前解決と複数の改善を行いました。
• 検索の多様性を改善します。12 個を超えるワーカーを使用する場合は、目標の下限を改善する専用のワーカーを追加します。
• 並列処理コードの変更: デフォルトでは、ソルバーは使用可能なすべてのコアを使用するようになりました。num_search_parameters を使用して、並列処理のレベルを指定します。
• SearchAllSolutions と SolveWithSolutionCallback のサポートが終了しました。
• Python API: model.Add() 呼び出しの外部で var == ... または var != ... を使用する場合の詳細なチェック。

2021 年 4 月

OR-Tools v9.0 のリリースのお知らせ

OR-Tools v9.0 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

依存関係の更新

• Abseil-cpp 20200923.3 を 20210324.1 LTS に更新しました。
• Protobuf 3.15.3 を 3.15.8 に更新しました。
• Java: jna-platform 5.5.0 を 5.8.0 に更新

Java

• OR-Tools が Maven Central で利用できるようになりました（com.google.ortools:ortools-java をご覧ください）。

バグの修正

• CP-SAT ソルバー使用時のマルチスレッドを改善しました（#1588 を参照）。
• std::vector&ltstd::string&gt の Python ラッパーのサポートを修正しました（#2453 を参照）。
• CPLEX サポートを再構築しました（#2470 を参照）。

既知の互換性を破る変更

• Python、Java、.Net でロガーのアクセス権を追加します（#2245 を参照）。
• すべてのカスタムの Google 型を cstdint で指定された型に置き換えます。

CP-SAT

• メソッド SearchForAllSolutions()、SearchAllSolutions()、SolveWithSolutionCallback() のサポートが終了しました。代わりに Solve() を使用してください。
• Python 標準演算子のサポートを改善しました。これにより、間違った既存のコードが破損する可能性があります。

2021 年 3 月

OR-Tools v8.2 のリリースのお知らせ

OR-Tools v8.2 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

依存関係の更新

• Abseil-cpp 20200923.2 を 20200923.3 LTS に更新しました。
• Protobuf を 3.14.0 を 3.15.3 に更新しました。

ルーティング

• RoutingModel.RegisterTransitMatrix() と RoutingModel.RegisterUnaryTransitVector() を追加しました。
• RoutingModel.AddVectorDimension() と RoutingModel.AddMatrixDimension() の戻り値を std::pair&ltint, bool&gt に変更します。int は交通機関エバリュエータ ID です。

2020 年 12 月

OR-Tools v8.1 のリリースのお知らせ

OR-Tools v8.1 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

依存関係の更新

• Abseil-cpp 20200923 を 20200923.2 LTS に更新しました。
• Protobuf を 3.13.0 を 3.14 に更新しました。
• Gurobi 9.1.0 のサポートを追加する
• GLog の依存関係を削除（abseil-cpp フラグに応じてカスタム実装に置き換え）
• GFlag の依存関係を削除（abseil-cpp フラグ コンポーネントに変更）

バグの修正

• Gurobi のフローティング ライセンスが二重にカウントされる問題を修正しました（#2227 を参照）。
• Windows ビルドを修正しました（#2200 を参照）。

2020 年 10 月

OR-Tools v8.0 のリリースのお知らせ

OR-Tools v8.0 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

プラットフォームの変更点

• Python 3.9 のサポートを追加しました（#2187）
• Python 3.5 のサポートを終了しました（#2186） <!-- Microsoft dotnet-sdk のサポートを待機していますが、リリース後にエラーが生成される可能性があります...
  • Ubuntu 20.10 のサポートを追加しました（#2188）-->
• Ubuntu 16.04 LTS のサポートを終了しました（#2188）
• Ubuntu 19.10 のサポートを終了しました（#2188）

依存関係の更新

• Abseil-cpp 20200225.2 を 20200923 LTS に更新しました。
• Protobuf 3.12.2 を 3.13.0 に更新しました。

既知の互換性を破る変更

• 現在、ルーティングと CP-SAT のソースコードは一部の C++17 機能を使用しています。警告: 独自のバージョンの abseil-cpp を提供する場合は、C++17 に対してもビルドされていることを確認してください。
• MPSolver::CreateSolver 署名が変更されました。モデル名の引数は削除されました。

CMake

• -DUSE_SCIP=OFF 使用時の SCIP サポートの無効化を修正しました（#2129 を参照）。
• サンプルと例を CMake ビルドシステムに統合します。注: -DBUILD_SAMPLES=OFF と -DBUILD_EXAMPLES=OFF を使用して無効にできます。注: 特定の言語に対して無効にするには、-DBUILD_<LANG>_SAMPLES=OFF または -DBUILD_<LANG>_EXAMPLES=OFF を使用します。
  • <LANG> を含む:
  • CXX,
  • PYTHON,
  • JAVA、
  • DOTNET.

製造元

• Make >= 4.3 が必要です（Make eval 関数を使用）。
• CMake >= 3.14 が必要です（CMake の --verbose オプションを使用）。
• -DUSE_SCIP=OFF を使用して SCIP サポートを無効にするオプションを追加しました（#2134 を参照）。
• -DUSE_COINOR=OFF を使用して CLP と CBC のサポートを無効にするオプションを追加。

Java

• OR-Tools で Maven パッケージを生成するようになりました（#202 を参照）。

バグの修正

• FreeBSD での C++ と Python のビルドを修正しました（#2126 を参照）。
• Windows でのデバッグでのビルドを修正しました（#2077 を参照）。
• Windows の CP-SAT における長時間にわたるクラッシュを並行して修正しました（#2001、#2019 を参照）。

2020 年 7 月

OR-Tools v7.8 のリリースのお知らせ

OR-Tools v7.8 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

依存関係の更新

• Gurobi 9.0.2 は、ビルド済みバイナリに事前統合されています。MAC OS X と Windows の Gurobi インストーラのデフォルトのインストール パス、または GUROBI_HOME ディレクトリで、gurobi 90 共有ライブラリを検索します。
• SCIP 7.0.1 がビルド済みのバイナリに統合されました。使用する前に、SCIP ライセンスに準拠していることを確認してください。
• オプションの Xpress Solver 8.9.0 のサポートを追加しました。

線形ソルバー

• 統合された線形ソルバー バックエンドのサポートの確認を簡素化するために、静的 LinearSolver::CreateSolver() メソッドを追加しました。すべての言語に対応しています。

バグの修正

• FreeBSD に基づく CMake ベースのビルドを修正しました。
• 累積カット生成における CP-SAT の並べ替えを修正しました。
• .Net ラッパーでの線形ソルバーのメモリリークを修正しました。

2020 年 6 月

OR-Tools v7.7 のリリースのお知らせ

OR-Tools v7.7 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

依存関係の更新

• Abseil-cpp b832dce を c51510d（LTS 20200225.2）に更新しました。
• Protobuf を 3.11.4 を 3.12.2 に更新しました。

新機能と改善点

• CP-SAT ソルバーは、充足可能性モデル（目標なし）で Feasible ではなく Optimal を返すようになりました。
• MIP コミュニティによる実現可能性ポンプのヒューリスティックを追加しました。

バグの修正

CP-SAT マルチスレッディングのクラッシュを修正しました（#2005 を参照）。

2020 年 4 月

OR-Tools v7.6 のリリースのお知らせ

OR-Tools v7.6 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

CP-SAT の新機能

CP-SAT ソルバーに以下の新機能を追加しました。

• LP の機材の管理を改善。
• デバッグツール。

依存関係の更新

Abseil-cpp 8ba96a8 を b832dce（LTS 20200225）に更新しました。

バグの修正

• presolve の CP-SAT UNSAT バグを修正しました（#1908 を参照）。
• swigwin.exe URL を修正しました。
• Java と .Net の SWIG タイプマップ管理を修正しました。

2020 年 1 月

OR-Tools v7.5 のリリースのお知らせ

OR-Tools v7.5 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

プラットフォームの変更点

• Python 3.8 のサポートを追加しました（#1719）
• Visual Studio 2017 で、ソースからのサポート コンパイルを廃止しました（#1852）。
• Centos 7 から Centos 8 にサポートを更新しました（#1827）。

依存関係の更新

• protobuf v3.10.0 を v3.11.2 に更新しました（#1829）。

バグの修正

以下の問題は OR-Tools v7.5 で修正されています（完全なリストについては、Milestone v7.5 をご覧ください）。

具体的には、次のとおりです。

• アセンブリの読み込みを修正しました。#1421 をご覧ください。
• RouteIndexManager の GetStartIndex() メソッドと GetEndIndex() メソッドを公開しました（#1843）。
• 破損したメソッドを削除するように SWIG を修正しました（#1838、#1276）。

2019 年 10 月

OR-Tools v7.4 のリリースのお知らせ

OR-Tools v7.4 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

新機能と改善点

• CP-SAT ソルバーで、適用リテラルをサポートしていない制約を確認するようになりました。このような制約に適用リテラルがある場合、モデル チェッカーは解決前にエラーを返します。
• ルーティング ライブラリのローカル検索の改善と高速化。
• 線形ソルバーがサードパーティ ソフトウェア Xpress-MP をサポートするようになりました。このツールを使用するには、ソースから OR-Tools を再ビルドする必要があります。
• NuGet パッケージのアーキテクチャが完全に書き換えられました。特に、Windows プラットフォーム上の .NET Framework 4.5.2 以降をサポートするようになりました。

サポートが終了したプラットフォーム

2019 年 7 月のリリースノートでお知らせしたように、OR-Tools は Python 2.7 のサポートを終了しました。

依存関係の更新

Protobuf 3.9.0 が 3.10.0 に更新されました。

2019 年 8 月

OR-Tools v7.3 のリリースのお知らせ

OR-Tools v7.3 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

サポートが終了したプラットフォーム

Google の Python 3 への移行に合わせて、Python 2.7 のサポートを終了します。これは、Python 2.7 をサポートする OR-Tools の最後のリリースです。

依存関係の更新

Protobuf 3.8.0 が 3.9.0 に更新されました。

バグの修正

以下の問題は OR-Tools v7.3 で修正されています。（完全なリストについては、Kanban v7.3 をご覧ください）。

具体的には、次のとおりです。

• Java での init/int64 キャストの問題を修正しました（#1448）、
• 空の累積制約を処理するときの presolve チェックを修正しました。

2019 年 7 月

OR-Tools v7.2 のリリースのお知らせ

OR-Tools v7.2 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

プラットフォームの変更点

• Google の Python 3 への移行に合わせて、Python 2.7 のサポートを終了します。Python 2.7 をサポートする OR-Tools のリリースは、あと 1 つだけです。
• Ubuntu 18.10 を Ubuntu 19.04 に更新しました。
• Visual Studio 2019 でのソースからのコンパイルのサポートを追加しました。
• Windows では Python 3.5 がサポートされなくなりました。Python 3.6 以降を使用してください。

依存関係の更新

• CBC 2.10.3 をターゲットとするようになりました。
• Protobuf 3.8.0 をターゲットとするようになりました。

CP-SAT

• Google では、検索、並列処理、線形リラクゼーションに関して複数の改善を行いました。
• Python の LinearExpr.Sum() API と LinearExpr.ScalProd() API を追加しました。
• C# の IntVar[].Sum() API と IntVar[].ScalProd() API が非推奨になりました。
• C++: SolveCpModel() と重複していたため、SolveWithModel() を削除しました。
• Java API に CpModel.addGreaterThan() メソッドと CpModel.addLessThan() メソッドを追加しました。

線形ソルバー

• Python、Java、C# 用の MPSolver.SetHint() を追加しました（SCIP と Gurobi でサポート）。
• Python、Java、C# 用の MPSolver.SetNumThreads() を追加しました（CBC、Gurobi、SCIP でサポート）。
• SCIP 6.0.1 のサポートを書き換えました。

リファレンス ドキュメント

• すべての言語とツール（アルゴリズム、ルーティング、グラフ、linear_solver、CP-SAT）向けに、doxygen と pdoc3 ベースのリファレンス マニュアルを追加しました。OR-Tools リファレンス マニュアルをご覧ください。
• C++（すべてのプロダクト）と CP-SAT（C++、Python、Java）のリファレンス ドキュメントが充実しています。
• Google では現在、すべての C++ ドキュメントを Python と Java にエクスポートする作業を進めています。
• .NET のドキュメントは不足しており、これを改善する解決策は予測できません。使用可能な API が表示されているため、そのままにしておきます。

2019 年 5 月

OR-Tools v7.1 のリリースのお知らせ

OR-Tools v7.1 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

必要な依存関係に対する変更

OR-Tools v7.1 には、次の新しい依存関係と更新された依存関係があります。

• glog v0.3.5 を v0.4.0 に更新しました。
• protobuf v3.6.1 を v3.7.1 に更新
• Cbc 2.9.9 を 2.10.1 に更新しました
• Cgl 0.59.10 を 0.60.1 に更新しました
• Clp 1.16.11 を 1.77.1 に更新しました
• Osi 0.107.9 を 0.108.1 に更新しました。
• CoinUtils 2.10.14 を 2.11.1 に更新しました。

CP-SAT API の変更点

以下のセクションでは、OR-Tools 7.1 での CP-SAT API の変更点について説明します。

• ドメインを使用して変数を作成する。
• 一次式でドメインを使用する。
• 一次式ヘルパーを使用する。

Domain を使用して変数を作成する

次の例は、連続していないドメインを持つ整数変数の作成方法を示しています。これは、削除されたメソッド NewEnumeratedIntVar() に代わるものです。ここで、変数 x は 1、3、4、6 のいずれかになります。

Python

model.NewIntVarFromDomain(cp_model.Domain.FromValues([1, 3, 4, 6]), 'x')

C++

model.NewIntVar(Domain::FromValues({1, 3, 4, 6}));

Java

model.newIntVarFromDomain(Domain.fromValues(new long[] {1, 3, 4, 6}), "x");

C#

model.NewIntVarFromDomain(Domain.FromValues(new long[] {1, 3, 4, 6}), "x");

間隔のリストを使用して変数を作成することもできます。以下の例では、変数 x は 1、2、4、5、6 に制約されています。

Python

model.NewIntVarFromDomain(cp_model.Domain.FromIntervals([[1, 2], [4, 6]]), 'x')

C++

model.NewIntVar(Domain::FromIntervals({ {1, 2}, {4, 6} }));

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");

一次式でドメインを使用する

次の例は、連続していないドメインで線形式を制限する方法を示しています。ここで、線形式 linear_expr は 5、6、8、9、10 に定義されています。

Python

model.AddLinearExpressionInDomain(linear_expr, cp_model.Domain.FromIntervals([(5, 6), (8, 10)]))

C++

model.AddLinearConstraint(linear_expr, Domain::FromIntervals({ {5, 6}, {8, 10} }))

Java

model.addLinearExpressionInDomain(linear_expr, Domain.fromIntervals(new long[][] { {5, 6}, {8, 10} }))

.Net

model.AddLinearExpressionInDomain(linear_expr, Domain.FromIntervals(new long[][] {new long[] {5, 6}, new long[] {8, 10} }));

一次式ヘルパーの使用

次の例は、ヘルパー メソッドを使用して合計とスカラー積を作成する方法を示しています。x + y == 20 と 4 * x + 2 * y = 56 が必要な例を次に示します。

Python

model.Add(x + y == 20)
model.Add(4 * x + 2 * y == 56)

C++

cp_model.AddEquality(LinearExpr::Sum({x, y}), 20);
cp_model.AddEquality(LinearExpr::ScalProd({x, y}, {4, 2}), 56);

Java

model.addEquality(LinearExpr.sum(new IntVar[] {x, y}), 20);
model.addEquality(LinearExpr.scalProd(new IntVar[] {x, y}, new long[] {4, 2}), 56);

.Net

model.Add(x + y == 20);
model.Add(4 * x + 2 * y == 56);

2019 年 3 月

OR-Tools v7.0 のリリースのお知らせ

OR-Tools v7.0 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

対応プラットフォームの変更

OR-Tools v7.0 では、次のプラットフォームがサポートされなくなりました。

• Visual C++ 2015
• Ubuntu 14.04
• Linux 上の Python 3.4

これらのプラットフォームを使用している場合は、OR-Tools v6.10 をインストールできます。

必要な依存関係に対する変更

OR-Tools v7.0 には、次の新しい依存関係と更新された依存関係があります。

• 新規: Abseil-cpp
• gflags 2.2.1 を 2.2.2 に更新しました。

以下のセクションでは、OR-Tools 7.0 の新機能と改善点について説明します。

• ルーティング プログラムの新しいインデックス マネージャー
• 集荷と配達を伴う VRP のサポート
• Java と C#でのラムダ関数のサポート

ルーティング プログラムの新しいインデックス マネージャー

OR-Tools v7.0 では、車両ルーティング プログラムで新しい RoutingIndexManager を使用する必要があります。これにより、位置の標準インデックスとソルバーで使用される内部インデックスの整合性が確保され、コード内のエラーを防止できます。

注: 標準的なロケーション インデックスは 0 ～ N-1 で、N はロケーション（デポを含む）の数です。技術的な理由から、ソルバーの内部ロケーション インデックスはその範囲外になることがあります。

新しい RoutingIndexManager では、ルーティング プログラムに軽微な変更が必要です。これについては、次のセクションで説明します。

• C++ と Java で RoutingIndexManager をインクルードまたはインポートします。
• RoutingIndexManager を宣言する
• RoutingIndexManager をディメンション コールバックに追加します。
• RoutingIndexManager を使用して解答を出力します。

RoutingIndexManager を追加/インポート

OR-Tools 7.0 では、次の例に示すように、C++ および Java のルーティング プログラムに RoutingIndexManager を含めるかインポートする必要があります。

C++

#include "ortools/constraint_solver/routing_index_manager.h"

Java

import com.google.ortools.constraintsolver.RoutingIndexManager;

Python と C# のインポートは変更されません。

RoutingIndexManager を宣言する

OR-Tools v7.0 では、次の例に示すように、ルーティング プログラムが RoutingIndexManager を宣言し、ルーティング モデルを作成する必要があります。

Python

manager = pywrapcp.RoutingIndexManager(num_locations, num_vehicles, depot)
routing = pywrapcp.RoutingModel(manager)

C++

RoutingIndexManager manager(num_locations, num_vehicles, depot);
RoutingModel routing(manager);

Java

RoutingIndexManager manager = new RoutingIndexManager(numLocations, numVehicles, depot);
RoutingModel routing = new RoutingModel(manager);

.Net

RoutingIndexManager manager = new RoutingIndexManager(numLocations, numVehicles, depot);
RoutingModel routing = new RoutingModel(manager);

RoutingIndexManager の引数は次のとおりです。

• ロケーションの数
• 車両の台数
• 車両基地のインデックス（すべての車両の始点と終点）

注: 以前のバージョンでは、これらの引数は RoutingIndexManager ではなく、RoutingModel に直接渡されていました。

コールバック

OR-Tools v7.0 では、RoutingIndexManager を使用して距離コールバックなどのコールバックを作成し、それをソルバーに渡す必要があります。次の例は、距離コールバックの作成方法を示しています。

Python

    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["distance_matrix"][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

C++

  const int transit_callback_index = routing.RegisterTransitCallback(
      [&data, &manager](const int64_t from_index,
                        const int64_t to_index) -> int64_t {
        // Convert from routing variable Index to distance matrix NodeIndex.
        const int from_node = manager.IndexToNode(from_index).value();
        const int to_node = manager.IndexToNode(to_index).value();
        return data.distance_matrix[from_node][to_node];
      });
  routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

Java

    final int transitCallbackIndex =
        routing.registerTransitCallback((long fromIndex, long toIndex) -> {
          // Convert from routing variable Index to user NodeIndex.
          int fromNode = manager.indexToNode(fromIndex);
          int toNode = manager.indexToNode(toIndex);
          return data.distanceMatrix[fromNode][toNode];
        });
    routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

.Net

        int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
                                                                   {
                                                                       // Convert from routing variable Index to
                                                                       // distance matrix NodeIndex.
                                                                       var fromNode = manager.IndexToNode(fromIndex);
                                                                       var toNode = manager.IndexToNode(toIndex);
                                                                       return data.DistanceMatrix[fromNode, toNode];
                                                                   });
        routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

IndexToNode メソッドは、ソルバーで使用される内部位置インデックスを距離行列の標準インデックスに変換します。

v7.0 では、以前のバージョンのようにソルバーに直接コールバックを渡すのではなく、まずコールバックへの参照である transit callback index を作成してから、それをソルバーに渡します（この場合は SetArcCostEvaluatorOfAllVehicles を使用）。

ディメンション

次の例は、キャパシティー付き車両ルーティングの問題の解答に使用する、需要とキャパシティのディメンションを作成する方法を示しています。

Python

    def demand_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data["demands"][from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        data["vehicle_capacities"],  # vehicle maximum capacities
        True,  # start cumul to zero
        "Capacity",
    )

C++

  const int demand_callback_index = routing.RegisterUnaryTransitCallback(
      [&data, &manager](const int64_t from_index) -> int64_t {
        // Convert from routing variable Index to demand NodeIndex.
        const int from_node = manager.IndexToNode(from_index).value();
        return data.demands[from_node];
      });
  routing.AddDimensionWithVehicleCapacity(
      demand_callback_index,    // transit callback index
      int64_t{0},               // null capacity slack
      data.vehicle_capacities,  // vehicle maximum capacities
      true,                     // start cumul to zero
      "Capacity");

Java

    final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> {
      // Convert from routing variable Index to user NodeIndex.
      int fromNode = manager.indexToNode(fromIndex);
      return data.demands[fromNode];
    });
    routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
        data.vehicleCapacities, // vehicle maximum capacities
        true, // start cumul to zero
        "Capacity");

.Net

        int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) =>
                                                                       {
                                                                           // Convert from routing variable Index to
                                                                           // demand NodeIndex.
                                                                           var fromNode =
                                                                               manager.IndexToNode(fromIndex);
                                                                           return data.Demands[fromNode];
                                                                       });
        routing.AddDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
                                                data.VehicleCapacities, // vehicle maximum capacities
                                                true,                   // start cumul to zero
                                                "Capacity");

印刷ソリューション

OR-Tools v7.0 では、ソリューションに車両ルートを表示するには、RoutingIndexManager を使用する必要があります。次の例は、サポートされているすべての言語でソリューションを出力する方法を示しています。

Python

def print_solution(manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    index = routing.Start(0)
    plan_output = "Route for vehicle 0:\n"
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += f" {manager.IndexToNode(index)} ->"
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += f" {manager.IndexToNode(index)}\n"
    plan_output += f"Distance of the route: {route_distance}m\n"
    print(plan_output)

C++

//! @brief Print the solution
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const RoutingIndexManager& manager,
                   const RoutingModel& routing, const Assignment& solution) {
  LOG(INFO) << "Objective: " << solution.ObjectiveValue();
  // Inspect solution.
  int64_t index = routing.Start(0);
  LOG(INFO) << "Route for Vehicle 0:";
  int64_t distance{0};
  std::stringstream route;
  while (!routing.IsEnd(index)) {
    route << manager.IndexToNode(index).value() << " -> ";
    const int64_t previous_index = index;
    index = solution.Value(routing.NextVar(index));
    distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{0});
  }
  LOG(INFO) << route.str() << manager.IndexToNode(index).value();
  LOG(INFO) << "Distance of the route: " << distance << "m";
  LOG(INFO) << "";
  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}

Java

  /// @brief Print the solution.
  static void printSolution(
      DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
    // Solution cost.
    logger.info("Objective : " + solution.objectiveValue());
    // Inspect solution.
    logger.info("Route for Vehicle 0:");
    long routeDistance = 0;
    String route = "";
    long index = routing.start(0);
    while (!routing.isEnd(index)) {
      route += manager.indexToNode(index) + " -> ";
      long previousIndex = index;
      index = solution.value(routing.nextVar(index));
      routeDistance += routing.getArcCostForVehicle(previousIndex, index, 0);
    }
    route += manager.indexToNode(routing.end(0));
    logger.info(route);
    logger.info("Distance of the route: " + routeDistance + "m");
  }

.Net

    /// <summary>
    ///   Print the solution.
    /// </summary>
    static void PrintSolution(in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution)
    {
        Console.WriteLine("Objective: {0}", solution.ObjectiveValue());
        // Inspect solution.
        Console.WriteLine("Route for Vehicle 0:");
        long routeDistance = 0;
        var index = routing.Start(0);
        while (routing.IsEnd(index) == false)
        {
            Console.Write("{0} -> ", manager.IndexToNode((int)index));
            var previousIndex = index;
            index = solution.Value(routing.NextVar(index));
            routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
        }
        Console.WriteLine("{0}", manager.IndexToNode((int)index));
        Console.WriteLine("Distance of the route: {0}m", routeDistance);
    }

集荷と配達を伴う VRP のサポート

OR-Tools v7.0 は、集荷と配達に関する車両ルーティング問題（VRP）の解決をサポートしています。これは、さまざまな場所でアイテムを受け取り、配達する車両フリートの最短ルートを見つけることを目的としています。問題は標準の VRP と同様にセットアップしますが、アイテムごとに場所のペア (i, j) を指定します。ここで、i は乗車場所、j は降車場所です。ルーティング ソルバーは、各ペアの (i, j)、i、j が同じ経路上にあり、車両が j より前に i を訪問するように、車両ルートを返します。

この種の問題を解決する例については、ピックアップと配達を伴う車両ルーティングをご覧ください。

ラムダ関数のサポート

OR-Tools v7.0 では、すでにサポートされていた C++ と Python に加えて、C# と Java のラムダ関数がサポートされるようになりました。ラムダ関数を使用すると、ルーティング プログラムでコールバックを簡単に定義できます。ただし、コードが読みやすくなると思われる場合は、標準関数を使用してコールバックを定義できます。

上記の C# と Java のコールバックの例は、ラムダ関数を使用してコールバックを定義する方法を示しています。

2018 年 11 月

バージョン v6.10 のリリースのお知らせ

OR-Tools バージョン 6.10 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

以下のセクションでは、バージョン 6.10 の新機能と改善点について説明します。

プログラムをビルドして実行するための簡素化されたコマンド

バージョン 6.10 では、

make run SOURCE=relative/path/to/program.cc

のようなコマンドを入力することで、プログラムをビルドして実行できます。ここで、<var>relative/path/to</var> はプログラムを含むディレクトリのパスです。

注: プログラムを実行するために Makefile を編集する必要はなくなりました。

プログラムを実行せずにビルドするには、次のように入力します。

make build SOURCE=relative/path/to/program.cc

言語別にプログラムを実行する具体的な手順については、OR-Tools を使ってみるをご覧ください。

SCIP 6.0.0 のサポート

OR-Tools が SCIP 6.0.0 をサポートするようになりました。

バイナリ

バイナリ ディストリビューションは、Java JDK 8（Ubuntu 14.04 の場合は JDK 7）を使用して構築されています。

CP-SAT ソルバー

API を更新する

• C++ CP-SAT CpModelBuilder API を追加しました。

例

一部の例を移動しました。

• コミュニティの例を examples/contrib に移動します。
• いくつかの例を ortools/<var>component</var>/samples に移動（例: ortools/linear_solver/samples/simple_program.java）

2018 年 9 月

バージョン v6.9 のリリースのお知らせ

OR-Tools バージョン 6.9 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

更新された依存関係

• Protobuf 3.5.1 -> 3.6.1。
• SCIP 4.0 -> 6.0。

CP-SAT ソルバー

• API の互換性を破る変更 - 詳しくは、こちらをご覧ください。
• Python で SolveWithSolutionObserver の名前を SolveWithSolutionCallback に変更します。

• Python で、クラス CpSolverSolutionCallback の NewSolution の名前を OnSolutionCallback に変更します。次の例は、Python で解答コールバックを作成する新しい方法を示しています。

  class MySolutionCallback(cp_model.CpSolverSolutionCallback):
  def init(self):
  cpmodel.CpSolverSolutionCallback.init(self)
  self._solution_count = 0
  
  
  def OnSolutionCallback(self):
  print('Solution {}, time = {}s, objective = {}, makespan = {}'.format(
    self.solution_count,
    self.WallTime(),
    self.ObjectiveValue(),
    self.Value(makespan)))
  self.solution_count += 1

• Python、Java、C# の解答コールバックで StopSearch を公開。ドキュメントはこちらをご覧ください。

• Python、Java、C# で ModelStats と CpSolverResponseStats を公開します。

• Python docstring のドキュメントを改善しました。ドキュメントはこちらをご覧ください。

• ソルバー インターフェースとクックブックの Java 実装の更新。

• 剰余を実装します。

• reservoir の実装の変更: ブール値の API を追加して、オプションのドレイン/充填イベントを指定します。

線形ソルバー

• Java と C# で InterruptSolve を公開します。

CP ソルバー

• C# で SolutionCollector ディレクターを公開します。

Python

• Python 3.7 のサポートを追加しました。
• ソースからコンパイルする場合: Python を検出するときに、python2 よりも python3 を優先します。

.NET

• .NET レイヤの完全な書き換え。
• ランタイム IDentifier win-x64、linux-x64、osx-x64 と互換性のある Google.OrTools NetStandard 2.0 Nuget パッケージを提供します。
• Google.OrTools.FSharp Nuget パッケージを提供します。
• すべての .NET サンプルのプロジェクト ファイルを追加します。
• すべての F# スクリプトの例（.fsx）を通常の F# プロジェクト（.fs）に更新します。
• こちらに、.NET パッケージのビルド生成に関するドキュメントを追加します。

フラット亜鉛

• flatzinc でのセットのサポートを追加しました（nosets.mzn を使用）。

投稿

• Binder のサポートを追加。Kevin Mader に感謝いたします。
• Java バインディングで DecisionVisitor を Director 型にしました。Jeremy Apthorp 氏に感謝いたします。

2018 年 7 月

バージョン v6.8 のリリースのお知らせ

OR-Tools バージョン 6.8 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

CP-SAT ソルバーに関するお知らせ

CP-SAT ソルバーは、制約プログラミングの新しいソルバーです。CP-SAT ソルバーは元の CP ソルバーよりも高速であるため、CP の問題に適しています。

CP-SAT ソルバーを使用する例については、GitHub の examples ディレクトリで、名前に _sat を含むファイルを探してください。

元の CP ソルバーは既存のコードをサポートするため一定期間保持されますが、非推奨になりました。

CP-SAT ソルバーの新しいオプション

このリリースでは、CP-SAT ソルバーに以下のオプションが追加されました。

• ローカル周辺検索（LNS）: SatParameters.use_lns オプションを使用して LNS を有効にします。
• 並列検索: SatParameters.num_search_workers オプションを使用すると、検索中に複数のスレッドを有効にできます。各スレッドは、異なるパラメータと異なるランダムシードを持つことができます。これにより、多様性が最大化され、少なくとも 1 つのスレッドが解を見つける確率が最大化されます。

解法のパフォーマンスを改善

CP-SAT ソルバーと Glop ソルバーのパフォーマンスを改善しました。

2018 年 3 月

バージョン v6.7 のリリースのお知らせ

OR-Tools バージョン 6.7 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

必要な依存関係の更新

• Protobuf 3.5.0 -> 3.5.1。

その他

• ベースをリファクタリングして abseil-cpp 統合を準備します。
• Travis CI と Appveyor の継続的インテグレーション（CI）サービスの使用。

土

• パフォーマンスの向上。
• Python API が改善されました。
• C# API（CpSolver.cs（試験運用版））を追加しました。

グロップ

• コードのリファクタリング。
• パフォーマンスの向上。

CMake のサポート（試験運用版）

• C++ OR-Tools の CMake サポートを追加しました。
• OR-Tools をスタンドアロンの CMake プロジェクトとしてビルドできる。
• 既存の CMake プロジェクトに OR-Tools を組み込むことができる。
• Python OR-Tools CMake ベースのビルドを追加します。
• CMake を使用して Python パッケージ（wheel）を生成します。

投稿

• Windows での winsock2.h の再定義を修正。Florent Tollin de Rivarol 氏に感謝いたします。
• F# サポートを追加（試験運用版）。ありがとう、Matthew Moore。 注: Makefile ビルダーでのみ使用できます。
• .NET スタンダード サポートを追加（試験運用版）。Ziad El Malki に感謝いたします。 注: Makefile ビルダーでのみ使用できます。

2017 年 11 月

バージョン v6.6 のリリースのお知らせ

OR-Tools バージョン 6.6 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

必要な依存関係の更新

• Protobuf を 3.3.0 -> 3.5.0 に更新。
• gflags を 2.2.0 -> 2.2.1 に変更しました。
• CBC 2.9.8 -> 2.9.9。
• Python の必要な依存関係として Python モジュール 6（1.10）を追加します。

バグの修正

• pull リクエスト #494 名前のリファクタリング。一部のエディタでの IntelliSense へのコメントの追加。ありがとう、Matthew Moore。
• pull リクエスト #516 F# スタンドアロン バイナリの指示。ありがとう、Matthew Moore。
• Glop の精度を高めます。

SAT ソルバー

• 内部 SAT ソルバーを改善し、さまざまなバグを修正。
• SAT ソルバーに VRP 制約を追加し、LP ソルバーにリンクします。
• SAT ソルバーの解オブザーバーを変更して、パラメータとして CpSolverResponse を受け取るようにします。
• SAT ソルバーでの Glop の使用を改善。
• SAT-LP 接続を高速化。
• Reservoir の制約を SAT cp_model protobuf 形式に追加。

SAT/Python

• Python での SAT API の紹介。
• ortools/sat/python/cp_model.py でコーディングします。
• examples/python/ に例を追加します。
• assignment_sat.py
• assignment_with_constraints_sat.py
• code_samples_sat.py
• cp_is_fun_sat.py
• gate_scheduling_sat.py
• hidato_sat.py
• jobshop_ft06_sat.py
• nqueens_sat.py
• nurses_sat.py
• rcpsp_sat.py
• steel_mill_slab_sat.py
• worker_schedule_sat.py
• IPython ノートブックのサポートを追加します。
• Python の例はノートブックにエクスポートされ、examples/notebook で参照できます。

例

• ProtoBuf 形式を使用して問題を格納するように rcpsp_parser を書き換えます。
• RCPSP パーサーを改善しました。

2017 年 10 月

バージョン v6.5 のリリースのお知らせ

OR-Tools バージョン 6.5 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

プラットフォームの変化

• pypi モジュール py3-ortools が ortools モジュールに統合されました。モジュールは「ortools」のみになりました。
• これらの Python モジュールの主な形式は、wheel ファイルになりました。pypi から Python 用 OR-Tools をインストールするには、pip install ortools を実行します。最新バージョンの pip がインストールされている必要があります（9.0.1 以降）。これにより、最新リリース（v6.5）が pull されます。

バグが修正されました

protobuf jar ファイルが、コンパイルされたクラスで正しくビルドされるようになりました。

新しい例

• さらに多くの F# の例が examples/fsharp ディレクトリに投稿されました（Matthew Moore に感謝します）。
• Java MIP の例も投稿されています（ありがとう Darian）。

2017 年 9 月

バージョン v6.4 のリリースのお知らせ

OR-Tools バージョン 6.4 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

プラットフォームの変化

• Linux プラットフォームの Pypi モジュールが、manylinux1 タグを使用して wheel ファイルとして提供されるようになりました。協力: Federico Ficarelli。 この変更に伴い、2017 年 7 月のリリースで導入された Linux ごとのモジュールをバックトラックしました。

新しい機能と特長

• GLOP 内で使用されるスケーリング方法を改善しました。
• C# ルーティング ライブラリ内のエバリュエータのラップを修正しました。DevNamedZed に感謝します。
• 大規模モデルの flatzinc 事前解決のパフォーマンスを改善しました。
• デフォルトでは、flatzinc に対応した SAT を使用します。
• sat ソルバーに対するコアベースのアプローチのパフォーマンスを改善。
• 線形割り当てアルゴリズムが誤って失敗するバグを修正。
• ortools/examples/fsharp に F# の例を追加しました。
• ルーティング ライブラリからポジティブ ペナルティのチェックを削除。

2017 年 8 月

バージョン v6.3 のリリースのお知らせ

OR-Tools バージョン 6.3 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

新しいダウンロード ファイル

Linux 用の Python wheel ファイルは、OR-Tools のリリースページで、すべてのダウンロードの最新バージョンとともにダウンロードできるようになりました。

Minizinc ソルバー

このバージョンには、 Minzinc 2017 チャレンジ用に送信された最終的な sat と flatzinc のコードが含まれています。

2017 年 7 月

バージョン v6.2 のリリースのお知らせ

OR-Tools バージョン 6.2 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

プラットフォームの変化

• 複数の Linux バイナリ ディストリビューション（Ubuntu 14.04、16.04、17.04、CentOS 7、Debian 9）がサポートされるようになりました。
• Linux プラットフォームの Pypi モジュールに、ディストリビューション（ubuntu-14.04、ubuntu-16.04、ubuntu-17.04、centos-7、debian-9）を記述するタグが追加されました。

新しい機能と特長

Docker で Linux アーティファクトをビルドするためのサポートを追加しました。or-tools/tools/docker に移動し、Makefile を見て、可能なターゲット（make archive、make pypi、make pypi3）を確認します。

これらのコマンドにより、export サブディレクトリが作成され、そこにバイナリ アーティファクトが追加されます。

2017 年 6 月

バージョン v6.1 のリリースのお知らせ

OR-Tools バージョン 6.1 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

プラットフォームの変化

• Visual Studio 2017 はサポートされており、Visual Studio 2013 のサポートは終了しました。
• macOS バージョン 10.9 以降がサポートされています。

新機能

CP-SAT ソルバー用に新しい protobuf 形式を追加しました。モデルの定義については ortools/sat/cp_model.proto を、問題の解決については ortools/sat/cp_model_solver.h をご覧ください。

バグの修正

問題 #420: すべてのプラットフォームの Python pypi モジュールで欠落していた __version__ 属性を修正しました。

2017 年 5 月

バージョン v6.0 のリリースのお知らせ

OR-Tools バージョン 6.0 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

C++ の新しいディレクトリ構造

C++ 使用時の OR-Tools のソース/インクルード構造を変更しました。これは、C++ インクルード ファイルのカプセル化を改善することを目的としています。また、C++ と Python のディレクトリ構造を揃えるという利点もあります。

• src/ の名前が ortools/ に変更されました。
• C++ ファイル内のすべての #include コマンドに接頭辞 ortools が追加されました。 #include "constraint/constraint_solver.h" は #include "ortools/constraint/constraint_solver.h" になりました。

新しい機能と特長

• Bazel のサポート。 Google のビルドツールである bazel を使用して、OR-Tools をビルドできるようになりました。Linux と Mac OS X で動作します。Bazel バージョン 0.4.5 以降をダウンロードしたら、ディレクトリを or-tools に変更し、サンプル（bazel build examples/cpp/...）をビルドします。

ルーティング

ルーティング ライブラリに休憩機能（ドライバーが昼食を食べることによる車両のダウンタイムなど）のサポートが実装されました。この機能を cvrptw_with_breaks.cc の例に示します。

SCIP サポート

線形ソルバーのラッパーが SCIP 4.0 をサポートするようになりました。まず SCIP をビルドし、次に SCIP を使用することをツールに伝える必要があります。手順については、こちらをご覧ください。

GLPK サポート

また、GLPK を使用したビルドの方法も変更しました。詳しくは、Wi-Fi 経由のメッセージ機能やチャット機能をオンにするをご覧ください。

クリーンアップ

• サポートが終了したため、C++ コードベースでの hash_map と hash_set の使用がすべて削除されました。STL の unordered_map と unordered_set に置き換えられました。
• Michael Powell 氏のご厚意による、C# makefile のクリーンアップ。

2017 年 1 月

バージョン v5.1 のリリースのお知らせ

OR-Tools バージョン 5.1 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

新機能

インストール

• バイナリ ディストリビューションまたはソースコードから OR-Tools をインストールする簡単な手順を導入しました。詳細については、バイナリから OR-Tools をインストールするまたはソースから OR-Tools をインストールするをご覧ください。

ルーティング

対称的な巡回営業担当者の問題の Held-Karp の下限を計算するアルゴリズムを実装しました。これにより、最適ではない可能性があるソリューションのコストと最適なソリューションのコストとのギャップの上限を計算できます。

• 車両ルーティング ライブラリに新しいメソッド RoutingModel::SetBreakIntervalsOfVehicle を追加しました。これにより、ブレーク間隔break（車両がタスク（移動やノードへのアクセスなど）を実行できない期間）を追加できます。このオプションを使用する例については、cvrptw_with_breaks.cc をご覧ください。

スケジュール設定

• Project Scheduling Library のパーサーに、より多くのデータ形式のサポートを追加しました。

衛星の解法

• SAT ソルバーの累積制約で、NewOptionalInterval メソッドで作成されたオプションの間隔が受け入れられるようになりました。例については、https://github.com/google/or-tools/blob/master/examples/cpp/rcpsp_sat.cc をご覧ください。
• リテラルの加重合計として目標を指定することで、Max-SAT（最大充足可能性の問題）を解くことができるようになりました。中間整数変数を作成する必要はなくなりました。

パフォーマンスの改善

• SAT ソルバー - 特に累積制約に関して、Sat ソルバーのパフォーマンスが向上しました。
• Glop ソルバー - Glop ソルバーの数値堅牢性を改善し、難解な数値問題に対してより正確な解を返すようになりました。
• Flatzinc の解法
• flatzinc インタープリタの Sat バックエンドのパフォーマンスが大幅に向上しました。
• C# Flatzinc インターフェースを簡素化しました。新しいインターフェースの例については、https://github.com/google/or-tools/blob/master/examples/csharp/csfz.cs をご覧ください。

バグの修正

• 1 台の車両と側部制約を含むルーティング モデルで PathCheapestArc ヒューリスティックを使用すると、ソルバーの実行時間が過度に長くなる場合があります。これは、サイド制約を適切に考慮することで修正されました。
• Java では、車両のルーティングの問題を解決するときに、ルーティング ソルバーがクラッシュすることがありました。この問題は最新リリースで修正されています。

2016 年 11 月

バージョン v5.0 のリリースのお知らせ

OR-Tools バージョン 5.0 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

実行中の例

• プログラムを簡単にコンパイルして実行できるようにする言語固有のターゲットと、OR-Tools に付属する例を導入しました。

土

• 制約プログラミングのサポートを追加しました。
• diffn、累積 、回路とサブ回路の制約が実装されました。
• 離散累積制約の最大エネルギー フィルタリング アルゴリズムに基づいてオーバーロード チェッカーを実装しました。
• AllDifferent 制約の伝播の改善を実装するすべての異なるバインド整合性プロパゲータを実装しました。

FlatZinc

• FlatZinc の問題用に SAT 解法を実装しました。

制約ソルバー

• 次の制約を実装 :
• atMost: 指定された値に等しい変数の数に上限を設定します。
• MakePathPrecedenceConstraint と MakePathTransitPrecedenceConstraint: 一連のペアに優先順位の制約を実装します。

ルーティング

• 検索で解決策が見つかるたびに呼び出されるコールバックである AddAtSolutionCallback を実装しました。
• RoutingModel デポのないコンストラクタを削除しました。ルーティング モデルで少なくとも 1 つのデポを指定することが必須になりました。

2016 年 9 月

バージョン v4.4 のリリースのお知らせ

OR-Tools バージョン 4.4 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

土

• 拡張スケジューリング API と、それを使用するための変更された例（weighted_tardiness_sat、jobshop_sat）。

グラフ

• Graph クラスにイテレータ トレイトを追加しました。

OR-Tools ディストリビューション

• Nuget パッケージが再びサポートされるようになりました。

2016 年 8 月

バージョン v4.3 のリリースのお知らせ

OR-Tools バージョン 4.3 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

制約ソルバー

• 変数が特定の間隔外になるように制約する NotBetween メソッドを実装しました。

ルーティングなし

• この例に示すように、既存の NotMember 制約をチェックし、ローカル検索フィルタで使用するモデルの解析を追加しました。
• ローカル検索のプロファイリングを追加しました。
• ローカル移動を修正しました。

線形ソルバー

• SCIP ステータスの報告を修正しました。

土

• SAT 事前解決ツールの使用を簡素化するために、SolveWithPresolve メソッドを実装しました。
• src/sat/util.h|cc 内の検索ユーティリティを再グループ化しました。
• SMT（遅延句生成）スケジューリング制約が実装されています。jobshop_sat.cc と weighted_tardiness_sat.cc をご覧ください。

グロップ

• より多くの計算ステージでスパース性を利用してパフォーマンスを改善しました。

フラット亜鉛

• minizinc チャレンジで見つかったバグを修正しました。

Lp_data

• イテレータでのテンプレートの簡素化が継続されます。

OR-Tools ディストリビューション

• C# アセンブリはデフォルトで厳密に命名されるようになりました。
• Protobuf3.0.0 にアップグレードしました。
• OR-Tools アーカイブの依存関係をチェックする Python スクリプトを追加しました。

2016 年 7 月

バージョン v4.2 のリリースのお知らせ

OR-Tools バージョン 4.2 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

制約ソルバー（ルーティング）

• 分離はカーディナリティ（この分離内でアクティブにできるノードの最大数）で定義できるようになりました。たとえば、n 個のノードと k のカーディナリティの分離を追加すると、n 個のノードのうち k 個のノードがアクティブになります。これを行うには、AddDisjunction の新しい定義を使用します。
• ノードごとに複数の分離のサポートを追加しました。たとえば、ノード N1 を多くの分離（D1..Dm）に追加できるようになりました。これにより、いずれかの要素内でアクティブになる可能性が高まります。分離時間ウィンドウに関連する問題用の高速なルーティング検索アルゴリズムを導入しました。
• ルーティング モデル パラメータに制約ソルバー パラメータを追加し、ルーティング検索パラメータに log_search を追加しました。
• ローカル検索アルゴリズムでは、互いに素な時間ウィンドウの問題を解決できるため、時間が短縮されます。詳しくは、cvrp_disjoint_tw.cc の例をご覧ください。

Glop（線形最適化）

• 高速のシンプレックス アルゴリズムを導入しました。

OR-Tools ディストリビューション

• C++、Java、.Net ごとに個別のアーカイブではなく、プラットフォームごとに 1 つのアーカイブを作成します。Python アーカイブは引き続き pypi でホストされます。
• pypi では、Mac OS X と Windows の wheel（.whl）モジュールに切り替えました。MAJOR.MINOR 番号付けスキーマを導入しました。これらの番号は、アーカイブ名、Mac OS X 共有ライブラリ、Python モジュール、.NET アセンブリに保存されているバージョンに使用されます。このスキーマを使用した最初のバージョンは v4.2 です。

2016 年 6 月

バージョン v2016-06 のリリースのお知らせ

OR-Tools バージョン v2016-06 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

制約ソルバー

• CP ライブラリからコールバックのほとんどのインスタンス（src/base/callback.h）を削除しました。
• NotMemberCt を追加しました（変数は一連の間隔に含めることはできません）。

ルーティング ライブラリ

• 互換性のない変更: AddDimensionWithVehicleCapacity で車両のキャパシティを指定するには、コールバックではなく配列（c++ のベクトル）を渡すことが必要になりました。

GLOP

• スパース マトリックスの内部表現を変更します。
• パフォーマンスの改善。

グラフ

• Dijkstra アルゴリズムと Bellman-Ford アルゴリズムを書き換え、コールバックを std::function（C++）で置き換えました。
• 円弧とノードを反復処理する際の異なるグラフ実装の API を変更しました。

土

• 使用されていないコアメソッド（解決ノード）を削除。
• 不満足性の証明を確認するドラフト ライターを追加しました。
• プリプロセッサを追加します。

バップ

• 新しい周辺地域を追加します。

例

• c++: サンプルのファイルラインリーダーをなくす
• 単一マシンのスケジューリングの問題を追加する。

ドキュメント

• 新しい ドキュメントをご確認ください。

2016 年 4 月

バージョン v2016-04 のリリースのお知らせ

OR-Tools バージョン v2016-04 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

更新された依存関係

• 制約プログラミング ライブラリとルーティング ライブラリでは、フラグの代わりに protobuf を使用します。詳しくは、http://or-tools.blogspot.fr/2016/02/heads-up-upcoming-incompatibility-in.html をご覧ください。

2015 年 12 月

バージョン v2015-12 のリリースのお知らせ

OR-Tools バージョン v2015-12 をリリースしました。バージョンを更新するには、OR-Tools のインストールの該当するセクションをご覧ください。

制約ソルバー

• CP ソルバーの大規模近傍検索の互換性を破っていました（新しい API を確認するには、examples/cpp/ls_api.cc、examples/python/pyls_api.py、examples/csharp/csls_api.cs、examples/com/google/ortools/sample/LsApi.java をご覧ください）。
• Python のラッピングをクリーンアップしました。CP ソルバーでカスタム決定をサポートします（API の動作を確認するには、examples/test/test_cp_api.py をご覧ください）。
• さまざまな機能の改善とバグの修正を行いました。

2015 年 9 月

GitHub で初回リリースを発表。

今後、ファイルは Google Cloud に保存されます。

フラット亜鉛

• flatzinc インタープリタのバイナリ アーカイブを追加しました（www.minizinc.org を参照）。
• チャレンジで使用したバージョンのいくつかの修正が含まれています。