OR-Tools for Java を使ってみる

以下のセクションでは、OR-Tools for Java の使い方を説明します。

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

最適化問題とは

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

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

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

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

  最適解とは、目的関数の値が最適である解です。（「最良」は最高値でも最小でもかまいません）。

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

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

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

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

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

線形最適化の例

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

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

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

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

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

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

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

Java プログラム

このセクションでは、問題をセットアップして解決する Java プログラムについて説明します。

注: 完全な Java プログラムとその実行手順は、このセクションの最後に記載されています。

手順は次のとおりです。

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

  import com.google.ortools.Loader;
  import com.google.ortools.init.OrToolsVersion;
  import com.google.ortools.linearsolver.MPConstraint;
  import com.google.ortools.linearsolver.MPObjective;
  import com.google.ortools.linearsolver.MPSolver;
  import com.google.ortools.linearsolver.MPVariable;

• ソルバーを宣言します。

  // Create the linear solver with the GLOP backend.
  MPSolver solver = MPSolver.createSolver("GLOP");
  if (solver == null) {
    System.out.println("Could not create solver GLOP");
    return;
  }

  MPSolver は、線形計画法や混合整数計画法の問題を解決するラッパーです。
• 変数を作成します。

  // Create the variables x and y.
  MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
  MPVariable y = solver.makeNumVar(0.0, 2.0, "y");
  
  System.out.println("Number of variables = " + solver.numVariables());

• 制約を定義します。最初の 2 つの制約 0 ≤ x ≤ 1 と 0 ≤ y ≤ 2 は、変数の定義によってすでに設定されています。次のコードでは、制約 x + y ≤ 2 を定義しています。

  double infinity = Double.POSITIVE_INFINITY;
  // Create a linear constraint, x + y <= 2.
  MPConstraint ct = solver.makeConstraint(-infinity, 2.0, "ct");
  ct.setCoefficient(x, 1);
  ct.setCoefficient(y, 1);
  
  System.out.println("Number of constraints = " + solver.numConstraints());

  setCoefficient メソッドは、制約の式に x と y の係数を設定します。
• 目的関数を定義します。

  // Create the objective function, 3 * x + y.
  MPObjective objective = solver.objective();
  objective.setCoefficient(x, 3);
  objective.setCoefficient(y, 1);
  objective.setMaximization();

  setMaximization メソッドは、これが最大化問題であると宣言しています。
• ソルバーを呼び出し、結果を表示します。

  System.out.println("Solving with " + solver.solverVersion());
  final MPSolver.ResultStatus resultStatus = solver.solve();
  System.out.println("Status: " + resultStatus);
  if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
    System.out.println("The problem does not have an optimal solution!");
    if (resultStatus == MPSolver.ResultStatus.FEASIBLE) {
      System.out.println("A potentially suboptimal solution was found");
    } else {
      System.out.println("The solver could not solve the problem.");
      return;
    }
  }
  
  System.out.println("Solution:");
  System.out.println("Objective value = " + objective.value());
  System.out.println("x = " + x.solutionValue());
  System.out.println("y = " + y.solutionValue());

プログラムを完了

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

package com.google.ortools.linearsolver.samples;

import com.google.ortools.Loader;
import com.google.ortools.init.OrToolsVersion;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** Minimal Linear Programming example to showcase calling the solver. */
public final class BasicExample {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();

    System.out.println("Google OR-Tools version: " + OrToolsVersion.getVersionString());

    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");
    if (solver == null) {
      System.out.println("Could not create solver GLOP");
      return;
    }

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

    System.out.println("Number of variables = " + solver.numVariables());

    double infinity = Double.POSITIVE_INFINITY;
    // Create a linear constraint, x + y <= 2.
    MPConstraint ct = solver.makeConstraint(-infinity, 2.0, "ct");
    ct.setCoefficient(x, 1);
    ct.setCoefficient(y, 1);

    System.out.println("Number of constraints = " + solver.numConstraints());

    // Create the objective function, 3 * x + y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 3);
    objective.setCoefficient(y, 1);
    objective.setMaximization();

    System.out.println("Solving with " + solver.solverVersion());
    final MPSolver.ResultStatus resultStatus = solver.solve();

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

    System.out.println("Solution:");
    System.out.println("Objective value = " + objective.value());
    System.out.println("x = " + x.solutionValue());
    System.out.println("y = " + y.solutionValue());

    System.out.println("Advanced usage:");
    System.out.println("Problem solved in " + solver.wallTime() + " milliseconds");
    System.out.println("Problem solved in " + solver.iterations() + " iterations");
  }

  private BasicExample() {}
}

Java プログラムの実行

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

1. 上のコードをコピーして新しいファイルに貼り付け、my_program.java という名前で保存します。
2. OR-Tools をインストールしたディレクトリの最上位でコマンド ウィンドウを開き、次のように入力します。

   make run SOURCE=relative/path/to/my_program.java

   ここで、relative/path/to/ はプログラムを保存したディレクトリのパスです。

注: 上記のコマンドは、OR-Tools をインストールしたディレクトリ（Makefile がある場所）の最上位から実行する必要があります。

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

Solution:
x =  1.0
y =  1.0

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

make build SOURCE=relative/path/to/my_program.java

その他の Java の例

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

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

世界には、さまざまな種類の最適化の問題があります。問題のタイプごとに、最適なソリューションを見つけるためのさまざまなアプローチとアルゴリズムがあります。

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

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

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

線形最適化

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

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

線形最適化の詳細

帯分整数最適化

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

混合整数最適化の詳細

制約の最適化

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

制約の最適化の詳細

職務

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

割り当ての詳細

包装

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

ビンパッキングの詳細

スケジュール設定

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

スケジュール設定の詳細

ルーティング

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

ルーティングの詳細

ネットワーク フロー

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

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

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