GoogleのOR-Toolsでナップサック問題を解く - 組合せ最適化問題の基礎を実践 #Python

この記事の目的

組合せ最適化問題の代表的な問題の一つ、ナップサック問題について、簡単な例題を通してその定式化と解法を学びます。
また、定式化した後、実際に解を求めるツールとして、Python言語によるGoogle製のOR-Toolsを使用し、実際にプログラミングして解を求めます。

組合せ最適化問題とその定式化について

何かを決定する際に、物事を「選択する」「選択しない」を選んだり、対象の集合から条件の要素を取り出す、あるいは順序付けるなどその組み合わせのパターンを考える問題を組合せ最適化問題と言います。

今、以下のようにiまたはjを1から始まる整数として、問題により予めわかっている定数a,b,cと解を求める対象の変数xについて、

a_i　(i = 1,2,3,...,m)　…予めわかっている定数\\
b_i　(i = 1,2,3,...,m)　…予めわかっている定数\\
x_j　(j = 1,2,3,...,n)　…xは整数

上記の定数や変数による線形式(足し算や掛け算の多項式)で解を求める問題を整数計画問題と言い、一般的には以下のように定式化されます。

<定式化例>\hspace{250pt}\\
目的関数：　c_1x_1 + c_2x_2 + ... + c_nx_n\\
条件：　a_{i1}x_1 + a_{i2}x_2 + ... + a_{in}x_n ≦ b_i \\ただし、i = 1,2,...,m\\
x_jは整数で、j=1,2,...,n

目的関数とは、その値を最大化または最小化することで最適な解が見つかる値のことで、ソルバーが自動的に計算します。
ソルバーとは最適化問題で最適解を算出するためのツールで、冒頭に書いた通りここではOR-Toolsを使用します。プログラミングにはPythonを使用します。

ナップサック問題の例題

ナップサック問題とは、組合せ最適化問題の中の典型問題(または標準問題)の一つです。
典型問題とは、生産・物流や販売計画、勤務スケジュール、情報処理など社会の中に存在する様々な問題を抽象化しいくつかのパターンに分類した代表問題のことを言います。

ここでは、参考テキスト(出典に記載)から以下のナップサック問題を例題として引用し、実際に解を求めます。

問題

下表アイテム表のとおり5個のアイテムがあり、各アイテムA～Eのそれぞれの\\
体積a_jと価値c_jがわかっている。(jは0～4のインデックス番号)\\
また、ナップサックの容量を12とする。\\
これらのアイテムからナップサックに詰めるアイテムの組み合わせを決定したい。\\
但し、選択したアイテムの体積の総和がナップサックの容量を超えてはいけない。\\
価値の和を最大するようなアイテムの組み合わせを決定せよ。\\

アイテム表

アイテム	A	B	C	D	E
インデックス番号j	0	1	2	3	4
体積aj	3	4	6	1	5
価値ci	6	7	8	1	4

解答

プログラムを検討します。
プログラムの記載内容については、基本的にGoogleのOR-Toolsのガイドに沿っています。(https://developers.google.com/optimization)

プログラムの冒頭におまじないを書きます。

knapsack.py

from __future__ import print_function
from ortools.linear_solver import pywraplp

混合整数計画ソルバーで解きますので、以下に宣言します。

knapsack.py

# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

次に、定数について定義します。

knapsack.py

# 定数定義 =================================================================

# アイテムの体積
a = [3,4,6,1,5]
# 価値
c = [6,7,8,1,4]
# ナップサックの容量
b = 12

上記、問題文に従い、アイテムの体積、価値、ナップサックの容量を定義します。
アイテムは5個あるので、配列で値を保持します。
アイテムの番号は配列のインデックスに合わせ、0から数えることとします。

変数xについて定義します。

knapsack.py

# 変数定義 =================================================================

# 1:選ぶ / 0:選ばない
x = {}
for j in range(5):
    x[j] = solver.BoolVar("x%i" % j)

上記、どのアイテムを選ぶかを決定する変数xを宣言します。
xは0または1の値を取り、アイテムを選ぶ場合は1、選ばない場合は0を取ります。
どの値を取るかはソルバーが計算して決定します。

いよいよ定式化に入ります。定式化では、条件式を設定していきます。当問題では、
　①選択したアイテムの体積の総和がナップサックの容量を超えてはいけない
　②価値の和を最大するようなアイテムの組み合わせを決定する
が条件となります。この条件を制約条件と呼び、式で表したものを制約式と呼びます。

以下、制約式を定義します。

knapsack.py

# 制約式 ===================================================================

# 選択したアイテムの体積の総和がナップサックの容量を超えてはいけない
solver.Add(solver.Sum([a[j] * x[j] for j in range(len(a))]) <= 12)

# 目的関数(最大化)
# 価値の和を最大するようなアイテムの組み合わせを決定する
solver.Maximize(solver.Sum([c[j] * x[j] for j in range(len(a))]))

冒頭の<定式化例>の通り、条件と目的関数を定義します。
最後に、解を算出する命令を書きます。

knapsack.py

# 求解実行
status = solver.Solve()

以上で最適化計算が行われ、ソルバーが最適解を算出します。
算出の結果、0～4のjにおいてxjが決定し、どのアイテムを選択するかが判明します。
算出結果を以下で確認します。

knapsack.py

if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())
    print("culculate Time = ", solver.WallTime(), " milliseconds")

    # 選択するアイテム
    print('select item')
    for j in range(len(a)):
        print(j,x[j].solution_value())

    # 価値
    print('total value')
    print(sum(c[j] * x[j].solution_value() for j in range(len(a))))

else:
    print('The problem does not have an optimal solution.')

以上でプログラミングは終了です。
実際の実行結果は以下となりました。

Solution:
ok
Objective value = 17.0
culculate Time = 158 milliseconds
select item
0 1.0
1 1.0
2 0.0
3 0.0
4 1.0
total value
17.0

最適化計算の結果、アイテムは0,1,4(A,B,E)を選択し、その価値は

\begin{eqnarray}

価値&=&c_0+c_1+c_4\\
&=&6+7+4\\
&=&17

\end{eqnarray}

であることが判明しました。
最適化計算は以上です。

以下、ソース全体です。

knapsack.py

from __future__ import print_function
from ortools.linear_solver import pywraplp

# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)


# 定数定義 =================================================================

# アイテムの体積
a = [3,4,6,1,5]
# 価値
c = [6,7,8,1,4]
# ナップサックの容量
b = 12

# 変数定義 =================================================================

# 1:選ぶ / 0:選ばない
x = {}
for j in range(5):
    x[j] = solver.BoolVar("x%i" % j)

# 制約式 ===================================================================

# 選択したアイテムの体積の総和がナップサックの容量を超えてはいけない
solver.Add(solver.Sum([a[j] * x[j] for j in range(len(a))]) <= 12)

# 目的関数(最大化)
# 価値の和を最大するようなアイテムの組み合わせを決定する
solver.Maximize(solver.Sum([c[j] * x[j] for j in range(len(a))]))

# 求解実行
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())
    print("culculate Time = ", solver.WallTime(), " milliseconds")

    # 選択するアイテム
    print('select item')
    for j in range(len(a)):
        print(j,x[j].solution_value())

    # 価値
    print('total value')
    print(sum(c[j] * x[j].solution_value() for j in range(len(a))))

else:
    print('The problem does not have an optimal solution.')

出展

本記事は、数理最適化について以下の参考テキストに記載の練習問題を参考にさせて頂いております。

■参考テキスト
「ITText 数理最適化」
　久野誉人・他[著]
　情報処理学会[編集]

ご意見など

ご意見、間違い訂正などございましたらお寄せ下さい。

GoogleのOR-Toolsでナップサック問題を解く - 組合せ最適化問題の基礎を実践

この記事の目的

組合せ最適化問題とその定式化について

ナップサック問題の例題

出展

関連情報

ご意見など