OR-Tools for .Net を使ってみる

以下のセクションでは、OR-Tools for .Net の使用方法について説明します。

最適化問題とは

最適化の目標は、多数の解決策の中から最適な解決策を見つけることです。（現実的な解決策が見つかって満足できる場合もありますが、OR-Tools を使用しても同様の結果が得られます）。

以下に、一般的な最適化の問題を示します。ある運送会社がトラックを使用して顧客に荷物を配達しているとします。同社は毎日、荷物をトラックに割り当て、トラックごとに荷物を配達するためのルートを選択する必要があります。可能なパッケージとルートの割り当てには、トラックの総移動距離やその他の要因に基づく費用が発生します。問題は、費用が最も少ないパッケージとルートの割り当てを選択することです。

他の最適化問題と同様に、この問題には次の要素があります。

  • 目標 - 最適化する数量。上記の例では、費用を最小限に抑えることが目標です。最適化の問題を設定するには、考えられる解決策の目標の値を計算する関数を定義する必要があります。これは目標関数と呼ばれます。上記の例では、目的関数を使用してパッケージとルートの割り当てにかかる合計費用を計算します。

    最適解とは、目的関数の値が最も優れた解です。（「最良」は最大値または最小値のいずれかです）。

  • 制約 - 問題の特定の要件に基づいて、考えられる解決策のセットを制限します。たとえば、運送会社が所定の重量を超える荷物をトラックに割り当てることができない場合、ソリューションに制約が課されます。

    実現可能な解決策とは、問題に対して与えられた制約をすべて満たすソリューションです。最適であるとは限りません。

最適化の問題を解決する最初のステップは、目標と制約を特定することです。

.Net での最適化問題を解く

次に、最適化の問題の例を示し、.Net で最適化問題を解く方法を示します。

線形最適化の例

最も古く最も広く使用されている最適化分野の一つに線形最適化（または線形計画法）があります。ここでは、目的関数と制約を線形式として記述できます。この種の問題の簡単な例を見てみましょう

次の制約に従って 3x + y を最大化します。

  1. 0 ～x～ 1
  2. 0 ～y～ 2
  3. x + y～ 2

この例の目的関数は 3x + y です。目的関数と制約はどちらも一次式で与えられるため、これは線形問題になります。

問題を解決するための主な手順

各言語で問題をセットアップして解決するための基本的な手順は、同じです。

  1. 必要なライブラリをインポートし、
  2. ソルバーを宣言する
  3. 変数を作成し、
  4. 制約を定義する
  5. 目的関数を定義する
  6. ソルバーを呼び出し、
  7. 結果を表示します。

.Net プログラム

このセクションでは、問題を設定し解決する .Net プログラムについて説明します。

手順は次のとおりです。

  • 必要なライブラリをインポートします。 
    using System;
using Google.OrTools.LinearSolver;
  • ソルバーを宣言します。 
    // Create the linear solver with the GLOP backend.
Solver solver = Solver.CreateSolver("GLOP");
if (solver is null)
{
    return;
}
    MPSolver は、線形計画法または混合整数計画法の問題を解決するラッパーです。
  • 変数を作成します。 
    // Create the variables x and y.
Variable x = solver.MakeNumVar(0.0, 1.0, "x");
Variable y = solver.MakeNumVar(0.0, 2.0, "y");

Console.WriteLine("Number of variables = " + solver.NumVariables());
  • 制約を定義します。最初の 2 つの制約 0 ≤ x ≤ 1 と 0 ≤ y ≤ 2 は、変数の定義によってすでに設定されています。次のコードでは制約 x + y ≤ 2 が定義されています。 
    // Create a linear constraint, 0 <= x + y <= 2.
Constraint ct = solver.MakeConstraint(0.0, 2.0, "ct");
ct.SetCoefficient(x, 1);
ct.SetCoefficient(y, 1);

Console.WriteLine("Number of constraints = " + solver.NumConstraints());
    SetCoefficient メソッドは、制約の式で x と y の係数を設定します。
  • 目的関数を定義します。 
    // Create the objective function, 3 * x + y.
Objective objective = solver.Objective();
objective.SetCoefficient(x, 3);
objective.SetCoefficient(y, 1);
objective.SetMaximization();
    メソッド setMaximization は、これを最大化問題として宣言しています。（基盤となる C++ メソッドは SetMaximization です）。
  • ソルバーを呼び出し、結果を表示します。 
    solver.Solve();
Console.WriteLine("Solution:");
Console.WriteLine("Objective value = " + solver.Objective().Value());
Console.WriteLine("x = " + x.SolutionValue());
Console.WriteLine("y = " + y.SolutionValue());

プログラムを完了する

プログラム全体を以下に示します。

using System;
using Google.OrTools.LinearSolver;

public class BasicExample
{
    static void Main()
    {
        // Create the linear solver with the GLOP backend.
        Solver solver = Solver.CreateSolver("GLOP");
        if (solver is null)
        {
            return;
        }

        // Create the variables x and y.
        Variable x = solver.MakeNumVar(0.0, 1.0, "x");
        Variable y = solver.MakeNumVar(0.0, 2.0, "y");

        Console.WriteLine("Number of variables = " + solver.NumVariables());

        // Create a linear constraint, 0 <= x + y <= 2.
        Constraint ct = solver.MakeConstraint(0.0, 2.0, "ct");
        ct.SetCoefficient(x, 1);
        ct.SetCoefficient(y, 1);

        Console.WriteLine("Number of constraints = " + solver.NumConstraints());

        // Create the objective function, 3 * x + y.
        Objective objective = solver.Objective();
        objective.SetCoefficient(x, 3);
        objective.SetCoefficient(y, 1);
        objective.SetMaximization();

        solver.Solve();

        Console.WriteLine("Solution:");
        Console.WriteLine("Objective value = " + solver.Objective().Value());
        Console.WriteLine("x = " + x.SolutionValue());
        Console.WriteLine("y = " + y.SolutionValue());
    }
}

.Net プログラムの実行

次のようにして、上のプログラムを実行します。

  1. 上記のコードをコピーして新しいファイルに貼り付け、BasicExample.cs という名前で保存します。OR-Tools をインストールしたディレクトリのサブディレクトリ examples/dotnet にあります。
  2. 同じディレクトリに新しいファイル BasicExample.csproj を作成し、次のコードを追加します。 
    <Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <LangVersion>7.3</LangVersion>
    <TargetFramework>netcoreapp3.1</TargetFramework>
    <EnableDefaultItems>false</EnableDefaultItems>
    <!-- see https://github.com/dotnet/docs/issues/12237 -->
    <RollForward>LatestMajor</RollForward>
    <RestoreSources>../../../temp_dotnet/packages;$(RestoreSources);https://api.nuget.org/v3/index.json</RestoreSources>
    <AssemblyName>Google.OrTools.BasicExample</AssemblyName>
    <IsPackable>true</IsPackable>
  </PropertyGroup>

  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
    <DebugType>full</DebugType>
    <Optimize>true</Optimize>
    <GenerateTailCalls>true</GenerateTailCalls>
  </PropertyGroup>

  <ItemGroup>
    <Compile Include="BasicExample.cs" />
    <PackageReference Include="Google.OrTools" Version="9.1.*" />
  </ItemGroup>
</Project>
  3. OR-Tools をインストールしたディレクトリの最上位で、コマンド ウィンドウを開いて次のように入力します。 
    make run SOURCE=examples/dotnet/BasicExample.cs

.Net プログラムを examples/dotnet/ とは別のディレクトリに保存して実行することもできますが、少し複雑です。 上記の csproj ファイルの次の行を変更して、packages ディレクトリへの正しいパスを指定します。 

../../../packages;$(RestoreSources);https://api.nuget.org/v3/index.json

最も簡単な方法は、.Net プログラムを examples/dotnet/ ディレクトリに配置することです。

プログラムは、目的関数を最大化する x と y の値を返します。

Solution:
x =  1.0
y =  1.0

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

make build SOURCE=relative/path/to/SimpleProgram.cs

プログラムに変更を加えた場合は、上記のように再コンパイルする必要があります。

.Net のその他の例

最適化に関するさまざまな種類の問題を解決する方法を示す .Net のその他の例については、例をご覧ください。

解決したい問題のタイプを特定する

最適化に関する問題は世界中に多種多様です。問題の種類ごとに、最適な解決策を見つけるためのさまざまなアプローチとアルゴリズムがあります。

最適化の問題を解決するプログラムの作成を始める前に、扱う問題のタイプを特定し、適切なソルバー（最適な解を見つけるためのアルゴリズム）を選択する必要があります。

以下では、OR-Tools で解決する問題の種類の概要と、各問題の種類の解決方法を説明するこのガイドのセクションへのリンクを示します。

線形最適化

前のセクションで学習したように、線形最適化の問題は、目的関数と制約が変数の線形式である問題です。

OR-Tools でこの種の問題に対する主な解法は、線形最適化ソルバーです。これは実際には、線形最適化と混合整数最適化のための複数のライブラリ（サードパーティ ライブラリを含む）のラッパーです。

線形最適化の詳細

帯分数最適化

混合整数最適化の問題とは、一部またはすべての変数を整数にする必要がある問題です。たとえば、ワーカーのグループを一連のタスクに割り当てる割り当て問題があります。ワーカーとタスクごとに、特定のワーカーが特定のタスクに割り当てられている場合は値が 1、それ以外の場合は 0 の変数を定義します。この場合、変数は値 0 または 1 のみを取ることができます。

帯分数最適化の詳細

制約の最適化

制約の最適化または制約プログラミング（CP）では、非常に大規模な候補セットから実行可能な解決策を特定し、任意の制約に関して問題をモデル化できます。CP は、最適化（最適なソリューションを見つけること）ではなく実現可能性（実現可能なソリューションを見つけること）に基づいており、目的関数よりも制約と変数に注目します。ただし、CP を使用すると、すべての可能な解の目的関数の値を比較するだけで、最適化の問題を解決できます。

制約の最適化の詳細

職務

割り当ての問題では、エージェントのグループ（ワーカーやマシンなど）を一連のタスクに割り当てることができます。各エージェントを特定のタスクに割り当てるための固定コストがあります。問題は総費用が最小の課題を見つけることです。割り当ての問題は、実際にはネットワーク フローの問題の特殊なケースです。

割り当ての詳細

包装

ビンパッキングは、さまざまなサイズのオブジェクトを異なる容量のコンテナにパッキングする問題です。目標は、コンテナの容量に応じて、可能な限り多くのオブジェクトをパッキングすることです。この特殊なケースとして、コンテナが 1 つしかない Knapsack 問題があります。

ビンパッキングの詳細

スケジュール設定中

スケジューリングの問題では、特定の時間に一連のタスクを実行するためにリソースを割り当てます。重要な例は、複数のジョブが複数のマシンで処理されるジョブショップ問題です。各ジョブは一連のタスクで構成され、これらのタスクは特定の順序で実行する必要があります。また、各タスクは特定のマシンで処理する必要があります。問題は、すべてのジョブができるだけ短い間隔で完了するようにスケジュールを割り当てることです。

スケジュールの詳細

ルーティング

ルーティングの問題では、有向グラフで定義されるネットワークを車両群が通過するための最適なルートを見つけます。最適化問題とはで説明されている配送トラックへの荷物の割り当てに関する問題は、ルーティングの問題の一例です。もう 1 つは、出張販売担当者の問題です。

ルーティングの詳細

ネットワーク フロー

最適化の問題の多くは、ノードとノード間の有向アークで構成される有向グラフで表すことができます。たとえば、商品が鉄道網を横断して出荷される輸送問題は、円弧が鉄道路線、ノードが配送センターであるグラフで表すことができます。

最大フローの問題では、各アークには、その全体で転送できる最大容量があります。問題は、輸送される総量が可能な限り多くなるように、各アークに出荷する商品の数量を割り当てることです。

ネットワーク フローの詳細