Gurobi Optimizationの使い方

Gurobi Optimizationとは

Gurobi Optimization（以下、Gurobi）は、数理最適化問題、特に線形計画問題（LP）や混合整数計画問題（MIP）を解くための、業界では世界最速とされる商用ソルバーです。

主な特徴

• 計算速度: オープンソースのソルバーと比較して、数倍〜数千倍の速度が出ることも珍しくありません。
• 堅牢性: 何百万もの変数を持つ大規模な問題でも安定して動作します。
• 多様なインターフェース: Python, C++, Java, MATLAB, Rなど、主要なプログラミング言語から利用可能です。

活用事例

• 物流: 配送ルートの最適化、トラックの積載率向上
• 製造: 生産スケジュールの立案、在庫管理の最適化
• エネルギー: 発電計画の最適化、電力網の需給調整
• 金融: ポートフォリオの最適化、リスク管理

アルゴリズム

Gurobiが問題を解くプロセスは、単に計算式を処理するだけではありません。ユーザーが定義したモデルを解きやすい形に変換し、最適なアルゴリズムを自動選択して実行します。

Step 1: 定式化

ユーザーは現実の問題を数式（決定変数、制約条件、目的関数）に落とし込みます。

• 決定変数 ($x$): 決めたい値（例：生産量）
• 目的関数 ($\max c^Tx$): 目指すゴール（例：利益最大化）
• 制約条件 ($Ax \le b$): 守るべきルール（例：工場の稼働時間上限）

Step 2: 前処理

ここがGurobiの速さの秘訣の一つです。本格的な計算を始める前に、モデルを分析し、冗長な制約や変数を削除・統合して問題を小さくします。

例: 「$x \le 5$ かつ $x \le 10$」という制約があれば、$x \le 10$ は不要なので削除します。

Step 3: 解を求める

前処理された問題に対して、最適なアルゴリズムを適用し、最適解を探索します。

Gurobiの導入とライセンスについて

Gurobiを利用するには、目的に応じて適切なライセンスを選択する必要があります。

• 無償版（機能制限なし・サイズ制限あり）
  • 概要: Pythonユーザー向け。ライセンス手続き不要ですぐに使えますが、解ける問題のサイズに制限があります。
  • 対象: 学習用、小規模なプロトタイプ作成
  • 制限: 変数・制約式が各2000個まで
  • 費用: 無償
• 評価版ライセンス（機能制限なし・期間限定）
  • 概要: 商用利用の検討用。フル機能を試せますが、使用期間が決まっています。
  • 制限: 30日間（サイズ制限なし）
  • 費用: 無償（要申請）
• アカデミックライセンス
  • 概要: 大学等の教育機関所属者向け。フル機能を無償で利用可能です。
  • 対象: 学生、教職員（学位授与機関に所属していること）
  • 制限: サイズ・期間の制限なし（1年ごとの更新が必要）
  • 費用: 無償
  • 取得方法: 学内ネットワーク（またはVPN）からGurobi公式サイトにアクセスして申請
    • アカデミックライセンスの取得方法について-Qiita
• 商用ライセンス
  • 概要: ビジネス利用向け。
  • 費用: 有償

2. インストール手順（Pythonの場合）

Pythonから利用する場合、現在はpipコマンドだけで簡単にインストールできます。

pip install gurobipy

※ アカデミック版や商用版のライセンスキーをお持ちの場合も、まずはこのコマンドでライセンス不要版としてインストールし、後述のライセンス設定を行うことで動作します。

3. ライセンスの設定（アカデミック・商用・評価版のみ）

サイズ制限版以外を利用する場合は、ライセンスファイルの適用が必要です。

1. ライセンスキーの取得: Gurobi公式サイト（User Portal）で発行されたライセンスキー文字列（grbgetkey xxxxx...）をコピーします。

2. ライセンスファイルの生成: ターミナル（またはコマンドプロンプト）で下記コマンドを実行します。

   grbgetkey xxxxx-xxxxx-xxxxx-xxxxx

3. ライセンスファイルの配置: 通常はデフォルトの場所（ホームディレクトリ等）に保存され、自動的に認識されます。- 補足: 任意の場所に置く場合のみ、環境変数 GRB_LICENSE_FILE にファイルパスを設定してください。

実装例

コード例として二次ナップサック問題をGurobiで扱った際のプログラムを以下に示します。

まず今回扱う二次ナップサック問題の定式化した式は以下になります。 扱っている問題はD-Wave neal(SA)の使い方と同じ定式化になります。

$$\begin{align*} \text{max}\quad & \sum_{i=0}^{n-1} p_{i} x_{i} + \sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1} Q_{i,j} x_{i} x_{j} \\ \text{s.t.}\quad & \sum_{i=0}^{n-1} w_{i} x_{i} \le C \end{align*}$$

この定式化をGurobiで実装すると以下のようになります。

import gurobipy as gp
from gurobipy import GRB

# アイテム数
n = 5

profits = [10, 8, 6, 4, 7]   # p_i
weights = [4, 3, 2, 1, 3]    # w_i
capacity = 7                 # C

# 二次相互作用 q_ij
Q = [
    [0, 2, 0, 0, 1],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 2, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
]

# モデル定義、"モデルの名称" をつけることができます。
m = gp.Model("quadratic_knapsack")

# バイナリ変数 を定義します。
x = m.addVars(n, vtype=GRB.BINARY, name="x")

# 目的関数（線形 + 二次のように記述できます。）
lin_part = gp.quicksum(profits[i] * x[i] for i in range(n))
quad_part = gp.quicksum(
    Q[i][j] * x[i] * x[j]
    for i in range(n)
    for j in range(i + 1, n)
)

# 今回は目的関数の最大化を考えます。
m.setObjective(lin_part + quad_part, GRB.MAXIMIZE)

# 容量制約を定義します。
m.addConstr(
    gp.quicksum(weights[i] * x[i] for i in range(n)) <= capacity,
    name="capacity"
)

# 目的関数＋制約のある問題を解きます。
m.optimize()

# 結果の表示
if m.status == GRB.OPTIMAL:
    print(f"最適目的値: {m.objVal:.2f}")
    selected = [i for i in range(n) if x[i].X > 0.5]
    print("選択されたアイテム:", selected)
    print("総重さ:", sum(weights[i] for i in selected))
else:
    print("最適解が見つかりませんでした。")

実行結果（例）

Optimize a model with 1 rows, 5 columns and 5 nonzeros (Max)
Model fingerprint: 0x67113661
Model has 5 linear objective coefficients
Model has 4 quadratic objective terms
Variable types: 0 continuous, 5 integer (5 binary)
Coefficient statistics:
  Matrix range     [1e+00, 4e+00]
  Objective range  [4e+00, 1e+01]
  QObjective range [2e+00, 4e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [7e+00, 7e+00]
Found heuristic solution: objective -0.0000000
Presolve time: 0.00s
Presolved: 5 rows, 9 columns, 17 nonzeros
Variable types: 0 continuous, 9 integer (9 binary)
Found heuristic solution: objective 19.0000000

Root relaxation: objective 2.400000e+01, 4 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0   24.00000    0    4   19.00000   24.00000  26.3%     -    0s
H    0     0                      21.0000000   24.00000  14.3%     -    0s
H    0     0                      22.0000000   24.00000  9.09%     -    0s
     0     0   24.00000    0    4   22.00000   24.00000  9.09%     -    0s

Explored 1 nodes (4 simplex iterations) in 0.03 seconds (0.00 work units)
Thread count was 2 (of 2 available processors)

Solution count 4: 22 21 19 -0

Optimal solution found (tolerance 1.00e-04)
Best objective 2.200000000000e+01, best bound 2.200000000000e+01, gap 0.0000%
最適目的値: 22.00
選択されたアイテム: [0, 2, 3]
総重さ: 7

実行結果の見方

Gurobiのログは情報量が多いですが、「正しく解けたか」「答えは何か」を確認するために見るべきポイントは実はごく一部です。

最低限チェックすべき2つのポイントに絞って解説します。

1. 終了ステータス（一番重要）

計算がどう終わったかを示します。

Optimal solution found (tolerance 1.00e-04)

• Optimal solution found:
  • 「最適解が見つかりました」という意味です。これが出ていれば成功です。
  • もし Time limit exceeded（時間切れ）や Infeasible（解なし）と出ていたら、設定やモデルを見直す必要があります。

2. 最終結果

Best objective 2.200000000000e+01, best bound 2.200000000000e+01, gap 0.0000%

• Best objective:
  • 最終的な「目的関数の値」です。（例：2.20...e+01 は $2.2 \times 10^1 = 22$ です）
• Gap 0.0000%:
  • 計算が完全に収束し、これ以上良い答えは存在しないことが数学的に証明されたことを意味します。

補足：最適なアルゴリズムをより知りたい人向け

Gurobi には、問題に対してさまざまなアルゴリズムが搭載されています。大きく分けて連続最適化と整数最適化のアプローチがあります。

A. 線形計画問題（LP）のアルゴリズム

変数が連続値の場合に使用されます。

1. 単体法（Simplex Method）: 多面体の頂点を移動しながら最適解を探す手法です。ある頂点から、より良い値を持つ隣の頂点へと移動を繰り返します。
2. 内点法（Interior Point / Barrier Method）: 多面体の内部を通り、最適解へと突き進む手法です。大規模な問題において、単体法よりも高速に動作する場合があります。Gurobiはこれらを自動で使い分け、あるいは並列で走らせます。

B. 混合整数計画問題（MIP）のアルゴリズム

変数が整数（0か1、個数など）に限定される場合、問題の難易度は跳ね上がり、NP困難となります。Gurobiはここで圧倒的な強さを発揮します。

1. 分枝限定法（Branch and Bound）: 探索空間を木構造のように分割（分枝）し、見込みのない枝を切り落としながら効率的に探索します。すべての可能性を試す全探索を回避するスマートな方法です。厳密解法としても非常に有名なアルゴリズムになっています。
2. 切除平面法（Cutting Planes）: 整数の条件を無視した緩和問題を解き、その解が整数でない場合、その解を切り落とすような新しい制約式（切除平面）を追加します。これにより、多面体を徐々に「整数の解」を含む形状へと削り込んでいきます。
3. ヒューリスティクス（Heuristics）: 数学的な厳密解法の合間に、経験則に基づいた探索を行い、良質な暫定解（Incumbent）を早期に見つけ出します。良い暫定解が早く見つかれば、分枝限定法で切り落とせる枝が増え、全体の計算時間が劇的に短縮されます。

ほかにも対応している問題があるので気になる方はサポートしている解法を覗いてみてください。

また、Gurobi内の利用された詳しいアルゴリズムについては公開されていません。そのため中身が何で解かれたかはブラックボックスになっています。

参考文献

[1] : Gurobi OPTIMIZATION HP, https://www.gurobi.com/jp/products/gurobi/, 閲覧日 2025/12/02

[2] : keisukesato-ac, 「数理最適化ソルバーGurobi Optimizer（アカデミックライセンス）インストール方法」, https://qiita.com/keisukesato-ac/items/b0425a879622b99a2610, 閲覧日 2025/12/02