以降のセクションでは、C++ で OR-Tools を使用する方法を説明します。
最適化問題とは
最適化の目標は、考えられる大規模なソリューション セットから問題に対する最適なソリューションを見つけることです。（実現可能な解決策が見つかって満足する場合もありますが、OR-Tools を使用して解決できる場合もあります）。
典型的な最適化の問題は、ある運送業者がトラックを使用して顧客に荷物を配達しているとします。同社は毎日、荷物をトラックに割り当て、トラックごとに荷物を配達するルートを選択する必要があります。パッケージとルートの可能な割り当てごとに、トラックの総移動距離や、場合によっては他の要因に基づくコストがかかります。問題は、費用が最も低いパッケージとルートの割り当てを選択することです。
すべての最適化問題と同様に、この問題には次のような要素があります。
目標 - 最適化する数量。上記の例では、費用を最小限に抑えることが目標です。最適化の問題を設定するには、考えられる解決策の目標の値を計算する関数を定義する必要があります。これは目標関数と呼ばれます。上記の例では、目的関数はパッケージとルートの割り当ての合計費用を計算します。
最適解とは、目的関数の値が最適である解です。（「最良」は最高値でも最小でもかまいません）。
制約 - 問題の特定の要件に基づいて、考えられるソリューションのセットを制限します。たとえば、運送会社が特定の重量を超える荷物をトラックに割り当てることができない場合、ソリューションに制約が課されます。
実現可能なソリューションとは、問題に対して与えられた制約をすべて満たすソリューションです。最適であるとは限りません。
最適化の問題を解決する最初のステップは、目標と制約を特定することです。
C++ での最適化問題を解決する
次に、最適化の問題の例を示し、C++ で問題をセットアップして解決する方法を説明します。
線形最適化の例
最も古く、最も広く使用されている最適化領域の一つが線形最適化（または線形計画）です。ここでは、目的関数と制約を線形式として記述できます。この種の問題の簡単な例を挙げます
次の制約に従い、3x + y を最大化します。
- 0 ≤
x≤ 1 - 0 ～
y～ 2 x + y≤ 2
この例の目的関数は 3x + y です。目的関数と制約の両方が一次式で与えられるため、これは線形問題になります。
問題を解決するための主な手順
各言語では、問題をセットアップして解決するための基本的な手順は同じです。
- 必要なライブラリをインポートする
- ソルバーを宣言する
- 変数を作成し、
- 制約を定義し、
- 目的関数を定義する
- ソルバーを呼び出して、
- 結果を表示します。
C++ プログラム
このセクションでは、問題をセットアップして解決する C++ プログラムについて説明します。
手順は次のとおりです。
- 必要なライブラリをインポートします。
#include <cstdlib> #include <memory> #include "absl/flags/flag.h" #include "absl/log/flags.h" #include "ortools/base/init_google.h" #include "ortools/base/logging.h" #include "ortools/init/init.h" #include "ortools/linear_solver/linear_solver.h"
- ソルバーを宣言します。
// Create the linear solver with the GLOP backend. std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP")); if (!solver) { LOG(WARNING) << "Could not create solver GLOP"; return; }MPSolverは、線形計画法や混合整数計画法の問題を解決するラッパーです。 - 変数を作成します。
// Create the variables x and y. MPVariable* const x = solver->MakeNumVar(0.0, 1, "x"); MPVariable* const y = solver->MakeNumVar(0.0, 2, "y"); LOG(INFO) << "Number of variables = " << solver->NumVariables();
- 制約を定義します。最初の 2 つの制約
0≤x≤1と0≤y≤2は、変数の定義によってすでに設定されています。次のコードでは、制約x + y≤2を定義しています。// Create a linear constraint, x + y <= 2. const double infinity = solver->infinity(); MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct"); ct->SetCoefficient(x, 1); ct->SetCoefficient(y, 1); LOG(INFO) << "Number of constraints = " << solver->NumConstraints();
SetCoefficientメソッドは、制約の式にxとyの係数を設定します。 - 目的関数を定義します。
// Create the objective function, 3 * x + y. MPObjective* const objective = solver->MutableObjective(); objective->SetCoefficient(x, 3); objective->SetCoefficient(y, 1); objective->SetMaximization();
SetMaximizationメソッドは、これが最大化問題であると宣言しています。 - ソルバーを呼び出し、結果を表示します。
LOG(INFO) << "Solving with " << solver->SolverVersion(); const MPSolver::ResultStatus result_status = solver->Solve(); // Check that the problem has an optimal solution. LOG(INFO) << "Status: " << result_status; if (result_status != MPSolver::OPTIMAL) { LOG(INFO) << "The problem does not have an optimal solution!"; if (result_status == MPSolver::FEASIBLE) { LOG(INFO) << "A potentially suboptimal solution was found"; } else { LOG(WARNING) << "The solver could not solve the problem."; return; } } LOG(INFO) << "Solution:"; LOG(INFO) << "Objective value = " << objective->Value(); LOG(INFO) << "x = " << x->solution_value(); LOG(INFO) << "y = " << y->solution_value();
プログラムを完了
プログラム全体を以下に示します。
// Minimal example to call the GLOP solver.
#include <cstdlib>
#include <memory>
#include "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/init/init.h"
#include "ortools/linear_solver/linear_solver.h"
namespace operations_research {
void BasicExample() {
LOG(INFO) << "Google OR-Tools version : " << OrToolsVersion::VersionString();
// Create the linear solver with the GLOP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
if (!solver) {
LOG(WARNING) << "Could not create solver GLOP";
return;
}
// Create the variables x and y.
MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");
LOG(INFO) << "Number of variables = " << solver->NumVariables();
// Create a linear constraint, x + y <= 2.
const double infinity = solver->infinity();
MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
ct->SetCoefficient(x, 1);
ct->SetCoefficient(y, 1);
LOG(INFO) << "Number of constraints = " << solver->NumConstraints();
// Create the objective function, 3 * x + y.
MPObjective* const objective = solver->MutableObjective();
objective->SetCoefficient(x, 3);
objective->SetCoefficient(y, 1);
objective->SetMaximization();
LOG(INFO) << "Solving with " << solver->SolverVersion();
const MPSolver::ResultStatus result_status = solver->Solve();
// Check that the problem has an optimal solution.
LOG(INFO) << "Status: " << result_status;
if (result_status != MPSolver::OPTIMAL) {
LOG(INFO) << "The problem does not have an optimal solution!";
if (result_status == MPSolver::FEASIBLE) {
LOG(INFO) << "A potentially suboptimal solution was found";
} else {
LOG(WARNING) << "The solver could not solve the problem.";
return;
}
}
LOG(INFO) << "Solution:";
LOG(INFO) << "Objective value = " << objective->Value();
LOG(INFO) << "x = " << x->solution_value();
LOG(INFO) << "y = " << y->solution_value();
LOG(INFO) << "Advanced usage:";
LOG(INFO) << "Problem solved in " << solver->wall_time() << " milliseconds";
LOG(INFO) << "Problem solved in " << solver->iterations() << " iterations";
}
} // namespace operations_research
int main(int argc, char* argv[]) {
InitGoogle(argv[0], &argc, &argv, true);
absl::SetFlag(&FLAGS_stderrthreshold, 0);
operations_research::BasicExample();
return EXIT_SUCCESS;
}
C++ プログラムの実行
上記のプログラムは次のように実行できます。
- 上のコードをコピーして新しいファイルに貼り付け、
program.ccという名前で保存します。 - OR-Tools をインストールしたディレクトリの最上位でコマンド ウィンドウを開き、次のように入力します。
make run SOURCE=relative/path/to/program.cc
ここで、relative/path/to/はプログラムを保存したディレクトリのパスです。
プログラムは、目的関数を最大化する x と y の値を返します。
Solution:
x = 1.0
y = 1.0
プログラムを実行せずにコンパイルするには、次のコマンドを入力します。
make build SOURCE=relative/path/to/program.cc
最適化モードでのコンパイル
O3 モードでコンパイルするには:
make DEBUG='-O3' all
C++ 実行可能ファイルを実行する
make を使用して OR-Tools の C++ プログラムをコンパイルすると、実行可能ファイルが bin ディレクトリに作成されます。サンプル プログラムの実行可能ファイルは次のように実行できます。
cd bin && ./program
プログラムに変更を加えた場合は、上記のように再コンパイルする必要があります。
その他の C++ の例
最適化に関するさまざまな問題の解決法を示した C++ のその他の例については、例をご覧ください。
解決したい問題のタイプを特定する
世界には、さまざまな種類の最適化の問題があります。問題のタイプごとに、最適なソリューションを見つけるためのさまざまなアプローチとアルゴリズムがあります。
最適化問題を解くプログラムの作成を開始する前に、対処する問題のタイプを特定し、適切なソルバー（最適な解を見つけるためのアルゴリズム）を選択する必要があります。
以下に、OR-Tools で解決できる問題の種類の概要と、各問題の種類を解決する方法を説明するこのガイドのセクションへのリンクを示します。
線形最適化
前のセクションで学習したように、線形最適化問題とは、目的関数と制約が変数の線形式である問題です。
このタイプの問題に対する OR-Tools の主な解法は、線形最適化ソルバーです。実際には、線形最適化と混合整数最適化のための複数のライブラリ（サードパーティ ライブラリを含む）のラッパーです。
帯分整数最適化
混合整数最適化の問題は、一部またはすべての変数を整数にする必要があります。たとえば、ワーカーのグループを一連のタスクに割り当てる割り当て問題があります。ワーカーとタスクごとに、指定されたワーカーが特定のタスクに割り当てられている場合は値が 1、それ以外の場合は 0 の値を持つ変数を定義します。この場合、変数は値 0 または 1 のみを取ることができます。
制約の最適化
制約の最適化、または制約プログラミング（CP）は、非常に大規模な候補セットから実行可能な解決策を特定し、任意の制約の観点から問題をモデル化できます。CP は、最適化（最適なソリューションを見つける）ではなく実現可能性（実現可能なソリューションを見つける）に基づいており、目的関数ではなく制約と変数に重点を置きます。ただし、CP を使用すると、すべての実現可能なソリューションの目的関数の値を比較するだけで、最適化の問題を解決できます。
職務
割り当ての問題では、エージェントのグループ（ワーカーやマシンなど）を一連のタスクに割り当てる際に、各エージェントを特定のタスクに割り当てるための固定料金が課されます。問題は合計費用が最も低い割り当てを見つけることです割り当ての問題は、実際にはネットワーク フローの問題の特殊なケースです。
包装
ビンパッキングとは、サイズの異なる一連のオブジェクトを異なる容量のコンテナにパッキングする問題です。目標は、コンテナの容量に応じて、できるだけ多くのオブジェクトをパッキングすることです。この特殊なケースは Knapsack の問題です。この問題では、コンテナが 1 つしかありません。
スケジュール設定
スケジューリングの問題では、特定の時間に一連のタスクを実行するリソースを割り当てます。重要な例として、複数のジョブが複数のマシンで処理されるジョブショップ問題があります。各ジョブは一連のタスクで構成され、これらのタスクは指定された順序で実行され、各タスクは特定のマシンで処理される必要があります。問題は、すべてのジョブが可能な限り短い間隔で完了するようにスケジュールを割り当てることです。
ルーティング
ルーティングの問題には、有向グラフで定義された、ネットワークを通過する車両群の最適なルートを見つけることが含まれます。最適化の問題とはで説明されているように、荷物を配達トラックに割り当てる問題は、ルーティングの問題の一例です。もう 1 つは巡回セールスパーソンの問題です。
ネットワーク フロー
最適化の問題の多くは、ノードとノード間の有向弧からなる有向グラフで表すことができます。たとえば、鉄道網を横断して商品を出荷する輸送問題は、円弧が線路、ノードが配送センターであるグラフで表現できます。
最大フロー問題では、各アークには、アーク全体で転送できる最大容量があります。問題は、輸送される合計数量ができるだけ多くなるように、各アークに配送する商品の数量を割り当てることです。