複数のナップサック処理をやってみた

複数のナップサックがある場合のナップサック問題でナップサックに入れるアイテム数脳上限を絞るにはどうしたらいいのかな、と調べたのでまとめます。

Google の OR-Tools を使っています。

基本的には OR-Tools 公式のサンプルコードとフォーラムでの内容を使っています。

GitHubはこちら、Colab はこちら

試用するテーブルデータについては、Google Colab 版は Google スプレッドシートからデータを取得する様にしていますので、適宜 Google スプレッドシートのURLを張り付けて xxx の部分を更新ください。

# 対象のGoogle SpreadSheetのURLを添付
# アドレスバーからそのままコピペ
ulr = "https://docs.google.com/spreadsheets/d/xxxxxxxx#gid=0"

GitHubには csv をアップしています。

また公式サンプルコードはprint() で処理結果を出力しますが、DataFrameにまとめるように修正しています。

変更点

各binごとのitem数の上限を配列に格納する

def create_data_model(df, num_bins, limit_item_capacity):

    data = {}
    weights = df["Weight"].values.tolist() # 重量

    (略)

    ### 変更点
    data['max_items'] = [limit_item_capacity] * len(weights)
    
    return data

(略)

### 制約条件
# max_items に設定した数以上の item 数を格納しない
for j in data['bins']:
    bin_count = 0
    for i in data['items']:
        bin_count += x[i, j]
    solver.Add(bin_count <= data['max_items'][j])

ナップサック処理結果をDataFrameにまとめる

df_knapsack = pd.DataFrame() # 集約するための空のDataFrame

if status == pywraplp.Solver.OPTIMAL:
    total_weight = 0
    for j in data['bins']:
        bin_weight = 0
        bin_value = 0
        for i in data['items']:
            if x[i, j].solution_value() > 0:
                bin_weight += data['weights'][i]
                bin_value += data['values'][i]

                # 必要な情報を 一時的な DataFrameに格納して df_knapsack に結合
                df_tmp = pd.DataFrame(
                    [
                        j, # Bin
                        i, # item
                        data['weights'][i], # weight
                        data['values'][i], # values
                    ]
                ).T
                df_tmp.columns=["bin", "item", "weight", "value"]
                df_knapsack = pd.concat([df_knapsack, df_tmp], axis=0)

        if bin_weight == 0: # 何も入らない bin が登場したら break で処理を終わらせる
            break
        total_weight += bin_weight
else:
    print('The problem does not have an optimal solution.')

df_knapsack = df_knapsack.reset_index(drop=True)

# 元データとナップサック処理後のデータで重量が一致するかテスト
assert df_knapsack["weight"].sum() == df["Weight"].sum()
display(df_knapsack)

処理結果

注：各binのアイテム上限を3に設定しています。
また、空のbinは出力しないようにしています。

以上になります、最後までお読みいただきありがとうございました。

コード全体(GitHub版)

### データ読み込み
import pandas as pd
df = pd.read_csv("sample_data.csv")

### ナップサック処理
from ortools.linear_solver import pywraplp

### ソルバー処理用に辞書に必要な情報を格納
def create_data_model(df, num_bins, limit_item_capacity):
    """サンプルデータの作成
    　df: 読み込むDataFrame、num_bins 設定する bin の数、
      limit_item_capacity: bin の中にいれられる item の数の上限
    """
    
    data = {}
    weights = df["Weight"].values.tolist() # 重量
    values = df["Value"].values.tolist() # 評価価値

    data['weights'] = weights
    data['values'] = values

    data['items'] = list(range(len(weights))) # item No
    data['num_items'] = len(weights)
    num_bins = num_bins
    data['bins'] = list(range(num_bins))
    data['bin_capacities'] = [1000] * num_bins
    data['max_items'] = [limit_item_capacity] * len(weights)
    return data

# SCIP でソルバーを作成 
solver = pywraplp.Solver.CreateSolver('SCIP')

data = create_data_model(df, 10, 3)


# 変数
# x[i, j] = 1 if item i is packed in bin j.
x = {}
for i in data['items']:
    for j in data['bins']:
        x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))


# 制約条件
# 全ての item は bin のどこかに 1つだけ入る
for i in data['items']:
    solver.Add(sum(x[i, j] for j in data['bins']) <= 1)

# bin_capacities で設定した重量以上の item を格納しない
for j in data['bins']:
    solver.Add(
        sum(x[(i, j)] * data['weights'][i]
            for i in data['items']) <= data['bin_capacities'][j])
    
# max_items に設定した数以上の item 数を格納しない
for j in data['bins']:
    bin_count = 0
    for i in data['items']:
        bin_count += x[i, j]
    solver.Add(bin_count <= data['max_items'][j])


# 目的変数の設定
objective = solver.Objective()

for i in data['items']:
    for j in data['bins']:
        objective.SetCoefficient(x[(i, j)], data['values'][i])
objective.SetMaximization()

status = solver.Solve()


### ナップサック処理結果の取得及び DataFrame 化
df_knapsack = pd.DataFrame() # 集約するための空のDataFrame

if status == pywraplp.Solver.OPTIMAL:
    total_weight = 0
    for j in data['bins']:
        bin_weight = 0
        bin_value = 0
        for i in data['items']:
            if x[i, j].solution_value() > 0:
                bin_weight += data['weights'][i]
                bin_value += data['values'][i]

                # 必要な情報を 一時的な DataFrameに格納して df_knapsack に結合
                df_tmp = pd.DataFrame(
                    [
                        j, # Bin
                        i, # item
                        data['weights'][i], # weight
                        data['values'][i], # values
                    ]
                ).T
                df_tmp.columns=["bin", "item", "weight", "value"]
                df_knapsack = pd.concat([df_knapsack, df_tmp], axis=0)

        if bin_weight == 0: # 何も入らない bin が登場したら break で処理を終わらせる
            break
        total_weight += bin_weight
else:
    print('The problem does not have an optimal solution.')


df_knapsack = df_knapsack.reset_index(drop=True) # indexのリセット

# 元データとナップサック処理後のデータで重量が一致するかテスト
assert df_knapsack["weight"].sum() == df["Weight"].sum()

display(df_knapsack)