今回は最適化問題を解くことが出来る
OR-Toolsについてです。

解説動画はこちら




OR-Toolsとは


Googleが開発している、組合せ最適化のためのライブラリ

様々な最適化問題を解くためのソルバーが充実していて
C++実装だが、Pythonなどいろいろな言語で使えます。


解ける最適化問題

次のような最適化問題を解くことができます。


1.配送ルート最適化
巡回セールスマン問題 : 1台の車両で最短経路を回る
配送計画問題 : 複数台の車両で分担して配送する

2.スケジューリングと制約プログラミング
決められた制約を全て満たしつつ、最適なスケジュールを組む
従業員のシフト作成
工場のライン計画

3.線形計画・整数計画(LP, MIP)
目的関数を最大化、または最小化する問題を数式で解く手法
生産計画 : 在庫と予算の範囲内で利益の最大化
リソース配分 : 予算内での広告効果最大化の割り当て

4.詰込み・割当問題
ナップサック問題 : 容量制限のあるバッグに価値が最大になるよう詰める
ビンピッキング問題 : サイズの異なる荷物を出来るだけ少ないトラックに詰める

5.ネットワークフロー
最大流問題 : パイプラインで一度に流せる最大量を求める
最小費用問題 : 指定量の輸送で、コストが最も安くなるルートと量の特定


インストール

Google Colab でも無いみたいなので、入れる必要あります。
pip install ortools


OR-Toolsの基本的な使い方

1.ライブラリの読み込み

解く問題に応じて、対応するライブラリを読み込みします
# CP-SATソルバー（制約プログラミング/MIP）
from ortools.sat.python import cp_model

# 線形計画法ソルバー（LP）
from ortools.linear_solver import pywraplp

# 配送計画（Routing）
from ortools.constraint_solver import pywrapcp, routing_enums_pb2

2. 最適化モデル構築

次に最適化モデルを作ります。
基本の「4ステップ」があります。

STEP 1: モデルのインスタンス作成
まず、問題を定義するための「箱」を作ります。

from ortools.sat.python import cp_model

model = cp_model.CpModel()


STEP 2: 変数の作成
「何を求めたいか」を変数として定義します。

整数変数: model.NewIntVar(下限, 上限, '変数名')
ブール変数: model.NewBoolVar('変数名')


STEP 3: 制約条件の追加
model.Add(...) を使って、守らなければならないルールを記述します。

等式・不等式: model.Add(x + y <= 10)
論理制約: 「Aの時だけBを適用する」といった
条件付き制約（OnlyEnforceIf）も可能


STEP 4: 目的関数の設定と実行
「何を最大化（または最小化）したいか」を決め
ソルバーを起動します。

# 最小化の場合
model.Minimize(目的の式)

# ソルバーの起動
solver = cp_model.CpSolver()
result = solver.Solve(model)

ここまでのコードを作れば
最適化問題が解ける様になっていると思います。


問題を解いてみる

簡単なつるかめ算をやって
あっているかを確認してみましょう。


問題1:
「つる」と「かめ」が合計で10匹、足の合計は28本です
それぞれ何匹ずついるでしょうか?

コードはこんな感じになります。
from ortools.sat.python import cp_model

def solve_tsurukame():
    # モデルの作成
    model = cp_model.CpModel()

    # 変数の定義 (0匹以上10匹以下)
    tsuru = model.NewIntVar(0, 10, 'tsuru')
    kame = model.NewIntVar(0, 10, 'kame')

    # 制約1: 合計が10匹
    model.Add(tsuru + kame == 10)

    # 制約2: 足の合計が28本
    model.Add(2 * tsuru + 4 * kame == 28)

    # ソルバーの準備と実行
    solver = cp_model.CpSolver()
    result = solver.Solve(model)

    if result == cp_model.OPTIMAL:
        print(f'つる: {solver.Value(tsuru)} 羽')
        print(f'かめ: {solver.Value(kame)} 匹')

solve_tsurukame()
つる: 6 羽
かめ: 4 匹


問題2：
50円切手と80円切手が計20枚、合計で1240円になるとき
それぞれ何枚ずつあるでしょうか?

from ortools.sat.python import cp_model

def solve_stamps():
    model = cp_model.CpModel()

    # 変数の定義 (0枚以上20枚以下)
    s50 = model.NewIntVar(0, 20, '50yen')
    s80 = model.NewIntVar(0, 20, '80yen')

    # 制約1: 合計20枚
    model.Add(s50 + s80 == 20)

    # 制約2: 合計金額が1240円
    model.Add(50 * s50 + 80 * s80 == 1240)

    solver = cp_model.CpSolver()
    result = solver.Solve(model)

    if result == cp_model.OPTIMAL:
        print(f'50円切手: {solver.Value(s50)} 枚')
        print(f'80円切手: {solver.Value(s80)} 枚')

solve_stamps()
50円切手: 12 枚
80円切手: 8 枚



問題3:

動画内ではすこし難しめの
入試問題なんかもやっています。

是非みてみてください。



まとめ


OR-Toolsは最適化問題を解くのに、かなり有効なライブラリです。

実社会の巨大な課題にも応用可能で
「Amazonのような配送ルート作成」や
「学校の複雑な時間割作成」など
他にもいろいろな最適化に応用できるものがあります。

だだし、使いこなすにはちょっとした
数学の知識が必要かもしれません。

使いこなせるとかなり問題を解ける幅が広がるので
実社会の問題解決にかなり有利かもしれません。

是非使ってみてください
それでは。



 
タグ ：
#プログラミング
#Python
#最適化問題
#ortools