ortools

Google OR-Tools - 組合せ最適化

OR-Tools は、難しい組合せ問題に特化したソルバーを提供します。その中核となるのが CP-SAT ソルバーです。制約プログラミングと充足可能性の技術を使い、標準的な線形ソルバーでは解けないスケジューリングやリソース割り当ての問題に対して、最適解を見つけます。

使用する場面

• 車両ルーティング（VRP）：車両群が商品を配送するための最適な経路を見つけます。
• スケジューリング：シフト表、プロジェクトのタイムライン、ジョブショップのスケジュールを作成します。
• ビンパッキング：サイズの異なる物体を、限られた数のビンに詰め込みます。
• ナップサック問題：重量制限内で価値を最大化するようにアイテムを選択します。
• 線形計画法（LP）：連続変数を使った標準的なリソース割り当てを行います。
• 整数計画法（MIP）：変数が整数でなければならない最適化問題を扱います（例：「購入する機械の台数」）。
• ネットワークフロー：グラフ内の最大フローまたは最小コストを計算します。

リファレンスドキュメント

公式ドキュメント：https://developers.google.com/optimization
GitHub：https://github.com/google/or-tools
検索パターン：cp_model.CpModel、pywraplp.Solver、routing_enums_pb2、AddConstraint

基本原則

モデリングと求解

OR-Tools では、問題の定義（変数、制約、目的関数）とソルバーエンジンが分離されています。モデルを構築してから、ソルバーインスタンスに渡します。

CP-SAT（制約プログラミング）

離散問題に最も適した、最新の推奨ソルバーです。重要な注意点：CP-SAT が扱えるのは整数のみです。浮動小数点数（0.5 など）がある場合は、スケーリングする必要があります（例：100 を掛けて整数として扱います）。

ステータスコード

求解後は、必ずステータスを確認してください。OPTIMAL（最適解）、FEASIBLE（解は見つかったものの、最適とは限らない）、INFEASIBLE（解けない）、LIMIT_REACHED のいずれかになります。

クイックリファレンス

インストール

pip install ortools

標準的なインポート

from ortools.sat.python import cp_model
from ortools.linear_solver import pywraplp
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

基本パターン - CP-SAT ソルバー（整数ロジック）

from ortools.sat.python import cp_model

# 1. Create the model
model = cp_model.CpModel()

# 2. Define variables: NewIntVar(lower_bound, upper_bound, name)
x = model.NewIntVar(0, 10, 'x')
y = model.NewIntVar(0, 10, 'y')

# 3. Add constraints
model.Add(x + y <= 8)
model.Add(x > 2)

# 4. Define Objective
model.Maximize(x + 2 * y)

# 5. Solve
solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL:
    print(f'x = {solver.Value(x)}, y = {solver.Value(y)}')

重要なルール

✅ 実施すること

• 離散タスクには CP-SAT を使用する - スケジューリングやロジックが複雑な問題では、MIP ソルバーより大幅に高速です。
• 浮動小数点数をスケーリングする - CP-SAT は整数ソルバーなので、1.25 を 125 に変換し、ロジックも調整します。
• 最初にステータスを確認する - ステータスが INFEASIBLE の場合は、変数の値にアクセスしないでください。
• インデックス指定には AddElement を使用する - 配列のインデックスとして変数を使う場合は、専用の制約 model.AddElement を使用します。
• 時間制限を設定する - 複雑な問題では、solver.parameters.max_time_in_seconds = 60.0 を使うと、1 分以内で得られる最善の解を取得できます。
• Value() で確認する - 結果には変数オブジェクト自体ではなく、solver.Value(var) を使ってアクセスします。

❌ 実施しないこと

• 制約内で Python の if を使わない - if x > 5: model.Add(...) のようには記述できません。ブール値の含意（OnlyEnforceIf）を使用します。
• 非線形演算を使わない - CP-SAT と LP ソルバーは、x * y（両方とも変数の場合）や sin(x) をサポートしていません。x * y には、専用の線形化または区分近似が必要です。
• 定義域を広くしすぎない - 変数の範囲を 0 から 1,000,000,000 にすると、ソルバーの処理が遅くなることがあります。境界は可能な限り狭くしてください。

アンチパターン（絶対に行わないこと）

from ortools.sat.python import cp_model

# ❌ BAD: Using standard Python logic inside the model
# if solver.Value(x) > 5: # ❌ Value() is not available during modeling!
#     model.Add(y == 1)

# ✅ GOOD: Conditional constraints (Logical Implication)
b = model.NewBoolVar('b')
model.Add(x > 5).OnlyEnforceIf(b)
model.Add(x <= 5).OnlyEnforceIf(b.Not())
model.Add(y == 1).OnlyEnforceIf(b)

# ❌ BAD: Floating point variables in CP-SAT
# x = model.NewIntVar(0, 1.5, 'x') # ❌ Error!

# ✅ GOOD: Scaling
# x_scaled = model.NewIntVar(0, 150, 'x_scaled') # 150 represents 1.50

線形計画法（pywraplp）

リソース割り当て（連続変数）

from ortools.linear_solver import pywraplp

# Create solver with GLOP backend (Google Linear Optimization Package)
solver = pywraplp.Solver.CreateSolver('GLOP')

# Define continuous variables
x = solver.NumVar(0, solver.infinity(), 'x')
y = solver.NumVar(0, solver.infinity(), 'y')

# Constraint: x + 2y <= 14
ct = solver.Constraint(-solver.infinity(), 14)
ct.SetCoefficient(x, 1)
ct.SetCoefficient(y, 2)

# Objective: Maximize 3x + 4y
objective = solver.Objective()
objective.SetCoefficient(x, 3)
objective.SetCoefficient(y, 4)
objective.SetMaximization()

solver.Solve()
print(f'Solution: x={x.solution_value()}, y={y.solution_value()}')

車両ルーティング（VRP）

物流エンジン

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def solve_vrp():
    # 1. Distance Matrix (distance between locations)
    data = {'distance_matrix': [[0, 10, 20], [10, 0, 15], [20, 15, 0]],
            'num_vehicles': 1, 'depot': 0}
    
    # 2. Setup Index Manager and Routing Model
    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                           data['num_vehicles'], data['depot'])
    routing = pywrapcp.RoutingModel(manager)
    
    # 3. Create Distance Callback
    def distance_callback(from_index, to_index):
        return data['distance_matrix'][manager.IndexToNode(from_index)][manager.IndexToNode(to_index)]
    
    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    
    # 4. Solve
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    
    solution = routing.SolveWithParameters(search_parameters)
    return solution

制約プログラミング：スケジューリング

ジョブショップの例（依存関係のあるタスク）

model = cp_model.CpModel()

# Define an Interval Variable (Start, Duration, End)
duration = 10
start_var = model.NewIntVar(0, 100, 'start')
end_var = model.NewIntVar(0, 100, 'end')
interval_var = model.NewIntervalVar(start_var, duration, end_var, 'interval')

# No-overlap constraint (Machines can only do one task at a time)
model.AddNoOverlap([interval_var1, interval_var2, interval_var3])

実践的なワークフロー

1. 従業員のシフトスケジューリング

def solve_shifts(num_employees, num_days, shifts_per_day):
    model = cp_model.CpModel()
    shifts = {}
    for e in range(num_employees):
        for d in range(num_days):
            for s in range(shifts_per_day):
                shifts[(e, d, s)] = model.NewBoolVar(f'shift_e{e}d{d}s{s}')
                
    # Constraint: Each shift is assigned to exactly one employee
    for d in range(num_days):
        for s in range(shifts_per_day):
            model.Add(sum(shifts[(e, d, s)] for e in range(num_employees)) == 1)
            
    # Constraint: Each employee works at most one shift per day
    for e in range(num_employees):
        for d in range(num_days):
            model.Add(sum(shifts[(e, d, s)] for s in range(shifts_per_day)) <= 1)
            
    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    return shifts, solver

2. 複数ナップサック（アイテムをビンに詰め込む）

def bin_packing(items, bin_capacities):
    model = cp_model.CpModel()
    # x[i, j] = 1 if item i is in bin j
    x = {}
    for i in range(len(items)):
        for j in range(len(bin_capacities)):
            x[i, j] = model.NewBoolVar(f'x_{i}_{j}')
            
    # Each item in exactly one bin
    for i in range(len(items)):
        model.Add(sum(x[i, j] for j in range(len(bin_capacities))) == 1)
        
    # Bin capacity constraint
    for j in range(len(bin_capacities)):
        model.Add(sum(x[i, j] * items[i] for i in range(len(items))) <= bin_capacities[j])

パフォーマンスの最適化

ヒント（ウォームスタート）

良い初期推定値がある場合は、探索を高速化するためにソルバーに渡してください。

model.AddHint(x, 5)
model.AddHint(y, 2)

並列求解

CP-SAT は、複数のスレッドを使って探索木の異なる部分を探索できます。

solver = cp_model.CpSolver()
solver.parameters.num_search_workers = 8 # Use 8 CPU cores

よくある落とし穴と解決策

浮動小数点演算のエラー

前述のとおり、OR-Tools CP-SAT は整数のみを厳密に扱います。

# ❌ Problem: model.Add(x * 0.1 <= 5)
# ✅ Solution: 
model.Add(x <= 50) # Multiply both sides by 10

実行不可能なモデル

solver.Solve(model) が INFEASIBLE を返す場合、制約に矛盾があることを意味します。

# ✅ Solution: Use 'Sufficient Assmptions' or 'Constraint Relaxation'
# to identify which constraint is causing the conflict.

対称性

項目 A と B が同一の場合、ソルバーは「A をビン 1 に、B をビン 2 に入れる」場合と「B をビン 1 に、A をビン 2 に入れる」場合の両方を確認するために時間を浪費します。

# ✅ Solution: Add symmetry-breaking constraints
# model.Add(x_A <= x_B) # Force an ordering

ベストプラクティス

1. 変数の値にアクセスする前に、必ずソルバーのステータスを確認する
2. CP-SAT を使用する場合は、浮動小数点値を整数にスケーリングする
3. 実行可能な解をすばやく得るため、複雑な問題には制限時間を設定する
4. 適切なソルバーを使用する ― 離散問題には CP-SAT、連続 LP には GLOP
5. 解を速く求めるため、同一の変数を含むモデルでは対称性を解消する
6. パフォーマンスを向上させるため、変数の定義域をできるだけ狭める
7. 良好な初期推定値がある場合は、ヒントを使用する
8. 大規模な問題では、利用可能な場合に並列ソルビングを有効にする
9. 制約が満たされていることを確認して、解を検証する
10. モデルをドキュメント化する ― 変数名と制約のロジック

Google OR-Tools は、最適化の世界を支える強力な機械です。世界規模の物流、航空会社のスケジュール管理、製造業を支える離散的なパズルを解き、不可能に思える「試行錯誤」を数学的な確実性へと変えます。