Google OR-Tools

Google OR-Tools

Google OR-Toolsは、最適化の問題を解決するための強力なツールです。

OR-Toolsは、線形プログラミング、整数プログラミング、制約プログラミング、ルート最適化などの問題を解決するために使用されます。

以下に、OR-Toolsのいくつかの便利な使い方を紹介します。

1. インストール

まず、OR-Toolsをインストールします。

Pythonのパッケージマネージャーを使用してインストールできます。

1
pip install ortools

2. 線形プログラミング

線形プログラミングの問題を解決するための基本的な例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from ortools.linear_solver import pywraplp

def linear_programming_example():
    # Solverを作成
    solver = pywraplp.Solver.CreateSolver('GLOP')
    if not solver:
        return

    # 変数の作成
    x = solver.NumVar(0, 1, 'x')
    y = solver.NumVar(0, 2, 'y')

    # 制約の設定
    solver.Add(x + y <= 2)

    # 目的関数の設定
    solver.Maximize(x + y)

    # 解を求める
    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        print('解が見つかりました:')
        print('x =', x.solution_value())
        print('y =', y.solution_value())
        print('最適値 =', solver.Objective().Value())
    else:
        print('最適解が見つかりませんでした')

linear_programming_example()

[実行結果]

解が見つかりました:
x = 0.0
y = 2.0
最適値 = 2.0

3. 整数プログラミング

整数プログラミングの問題を解決するための基本的な例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from ortools.linear_solver import pywraplp

def integer_programming_example():
    # Solverを作成
    solver = pywraplp.Solver.CreateSolver('SCIP')
    if not solver:
        return

    # 変数の作成
    x = solver.IntVar(0, 10, 'x')
    y = solver.IntVar(0, 10, 'y')

    # 制約の設定
    solver.Add(x + y <= 5)

    # 目的関数の設定
    solver.Maximize(2 * x + 3 * y)

    # 解を求める
    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        print('解が見つかりました:')
        print('x =', x.solution_value())
        print('y =', y.solution_value())
        print('最適値 =', solver.Objective().Value())
    else:
        print('最適解が見つかりませんでした')

integer_programming_example()

[実行結果]

解が見つかりました:
x = 0.0
y = 5.0
最適値 = 15.0

4. ルート最適化

ルート最適化の基本的な例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def create_data_model():
    """データを作成"""
    data = {}
    data['distance_matrix'] = [
        [0, 9, 2, 7],
        [9, 0, 6, 3],
        [2, 6, 0, 4],
        [7, 3, 4, 0],
    ]
    data['num_vehicles'] = 1
    data['depot'] = 0
    return data

def print_solution(manager, routing, solution):
    """解を表示"""
    print('Objective: {} miles'.format(solution.ObjectiveValue()))
    index = routing.Start(0)
    plan_output = 'Route:\n'
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += ' {} ->'.format(manager.IndexToNode(index))
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += ' {}\n'.format(manager.IndexToNode(index))
    print(plan_output)
    print('Route distance: {} miles'.format(route_distance))

def main():
    """ルート最適化のメイン関数"""
    # データを作成
    data = create_data_model()

    # ルーティングインデックスマネージャーとルーティングモデルを作成
    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_vehicles'], data['depot'])
    routing = pywrapcp.RoutingModel(manager)

    def distance_callback(from_index, to_index):
        """距離のコールバック"""
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # コスト関数の設定
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # 検索パラメータの設定
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    # 解を求める
    solution = routing.SolveWithParameters(search_parameters)

    # 解を表示
    if solution:
        print_solution(manager, routing, solution)

if __name__ == '__main__':
    main()

[実行結果]

Objective: 18 miles
Route:
 0 -> 2 -> 3 -> 1 -> 0

Route distance: 18 miles

5. 制約プログラミング

制約プログラミングの基本的な例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from ortools.sat.python import cp_model

def constraint_programming_example():
    # モデルを作成
    model = cp_model.CpModel()

    # 変数の作成
    x = model.NewIntVar(0, 10, 'x')
    y = model.NewIntVar(0, 10, 'y')
    z = model.NewIntVar(0, 10, 'z')

    # 制約の設定
    model.Add(x + y + z == 15)
    model.Add(x > y)
    model.Add(z < x + 2)

    # 目的関数の設定
    model.Maximize(x + 2 * y + 3 * z)

    # ソルバーを作成して解を求める
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    if status == cp_model.OPTIMAL:
        print('解が見つかりました:')
        print('x =', solver.Value(x))
        print('y =', solver.Value(y))
        print('z =', solver.Value(z))
        print('最適値 =', solver.ObjectiveValue())
    else:
        print('最適解が見つかりませんでした')

constraint_programming_example()

[実行結果]

解が見つかりました:
x = 5
y = 4
z = 6
最適値 = 31.0

これらの例をもとに、$Google OR-Tools$を使用して様々な最適化問題を解決できます。

公式ドキュメントやチュートリアルも参考にして、さらに高度な問題に挑戦してみてください。