このページは Cloud Translation API によって翻訳されました。

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

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

最適化問題とは
.Net での最適化の問題を解決する
.Net のその他の例
解決したい問題のタイプを特定する

最適化問題とは

最適化の目標は、考えられる大規模なソリューションセットから問題に対する最適なソリューションを見つけることです。（実現可能な解決策が見つかって満足する場合もありますが、OR-Tools を使用して解決できる場合もあります）。

典型的な最適化の問題は、ある運送業者がトラックを使用して顧客に荷物を配達しているとします。同社は毎日、荷物をトラックに割り当て、トラックごとに荷物を配達するルートを選択する必要があります。パッケージとルートの可能な割り当てごとに、トラックの総移動距離や、場合によっては他の要因に基づくコストがかかります。問題は、費用が最も低いパッケージとルートの割り当てを選択することです。

すべての最適化問題と同様に、この問題には次のような要素があります。

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

最適解とは、目的関数の値が最適である解です。（「最良」は最高値でも最小でもかまいません）。
制約 - 問題の特定の要件に基づいて、考えられるソリューションのセットを制限します。たとえば、運送会社が特定の重量を超える荷物をトラックに割り当てることができない場合、ソリューションに制約が課されます。

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

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

.Net での最適化問題を解決する

次に、最適化問題の例を示し、.Net でその問題を設定し解決する方法を説明します。

線形最適化の例

最も古く、最も広く使用されている最適化領域の一つが線形最適化（または線形計画）です。ここでは、目的関数と制約を線形式として記述できます。この種の問題の簡単な例を挙げます

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

0 ≤ x ≤ 1
0 ～y～ 2
x + y ≤ 2

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

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

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

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

.Net プログラム

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

手順は次のとおりです。

必要なライブラリをインポートします。

using System;
using Google.OrTools.Init;
using Google.OrTools.LinearSolver;

ソルバーを宣言します。

// Create the linear solver with the GLOP backend.
Solver solver = Solver.CreateSolver("GLOP");
if (solver is null)
{
    Console.WriteLine("Could not create solver GLOP");
    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 &leq; x ≤ 1 と 0 &leq; y ≤ 2 は、変数の定義によってすでに設定されています。次のコードでは、制約 x + y &leq; 2 を定義しています。
```
// Create a linear constraint, x + y <= 2.
Constraint constraint = solver.MakeConstraint(double.NegativeInfinity, 2.0, "constraint");
constraint.SetCoefficient(x, 1);
constraint.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 です）。

ソルバーを呼び出し、結果を表示します。

Console.WriteLine("Solving with " + solver.SolverVersion());
Solver.ResultStatus resultStatus = solver.Solve();
Console.WriteLine("Status: " + resultStatus);
if (resultStatus != Solver.ResultStatus.OPTIMAL)
{
    Console.WriteLine("The problem does not have an optimal solution!");
    if (resultStatus == Solver.ResultStatus.FEASIBLE)
    {
        Console.WriteLine("A potentially suboptimal solution was found");
    }
    else
    {
        Console.WriteLine("The solver could not solve the problem.");
        return;
    }
}

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.Init;
using Google.OrTools.LinearSolver;

public class BasicExample
{
    static void Main()
    {
        Console.WriteLine("Google.OrTools version: " + OrToolsVersion.VersionString());

        // Create the linear solver with the GLOP backend.
        Solver solver = Solver.CreateSolver("GLOP");
        if (solver is null)
        {
            Console.WriteLine("Could not create solver GLOP");
            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, x + y <= 2.
        Constraint constraint = solver.MakeConstraint(double.NegativeInfinity, 2.0, "constraint");
        constraint.SetCoefficient(x, 1);
        constraint.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();

        Console.WriteLine("Solving with " + solver.SolverVersion());
        Solver.ResultStatus resultStatus = solver.Solve();

        Console.WriteLine("Status: " + resultStatus);
        if (resultStatus != Solver.ResultStatus.OPTIMAL)
        {
            Console.WriteLine("The problem does not have an optimal solution!");
            if (resultStatus == Solver.ResultStatus.FEASIBLE)
            {
                Console.WriteLine("A potentially suboptimal solution was found");
            }
            else
            {
                Console.WriteLine("The solver could not solve the problem.");
                return;
            }
        }

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

        Console.WriteLine("Advanced usage:");
        Console.WriteLine("Problem solved in " + solver.WallTime() + " milliseconds");
        Console.WriteLine("Problem solved in " + solver.Iterations() + " iterations");
    }
}

.Net プログラムの実行

上記のプログラムは次のように実行できます。

上記のコードをコピーして新しいファイルに貼り付け、BasicExample.cs という名前で保存します。OR-Tools をインストールしたディレクトリのサブディレクトリ examples/dotnet にあります。

同じディレクトリに新しいファイル 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>

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 で解決できる問題の種類の概要と、各問題の種類を解決する方法を説明するこのガイドのセクションへのリンクを示します。

線形最適化
制約の最適化
混合整数の最適化
Assignment
Scheduling
梱包
ルーティング
ネットワークフロー

線形最適化

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

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

線形最適化の詳細

帯分整数最適化

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

混合整数最適化の詳細

制約の最適化

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

制約の最適化の詳細

職務

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

割り当ての詳細

包装

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

ビンパッキングの詳細

スケジュール設定

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

スケジュール設定の詳細

ルーティング

ルーティングの問題には、有向グラフで定義された、ネットワークを通過する車両群の最適なルートを見つけることが含まれます。最適化の問題とはで説明されているように、荷物を配達トラックに割り当てる問題は、ルーティングの問題の一例です。もう 1 つは巡回セールスパーソンの問題です。

ルーティングの詳細

ネットワークフロー

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

最大フロー問題では、各アークには、アーク全体で転送できる最大容量があります。問題は、輸送される合計数量ができるだけ多くなるように、各アークに配送する商品の数量を割り当てることです。

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